数学研发网设为首页收藏本站

数学研发论坛

 找回密码
 欢迎注册
查看: 9892|回复: 28

[擂台] 快速求(sqrt(2)-1)的幂展开形式

[复制链接]
发表于 2008-1-23 23:59:45 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
精华
将(sqrt(2)-1)^r 转换为sqrt(k)-sqrt(k-1)的形式,比如r=10000

举例如下:
r=1,k=2
r=2,k=9
r=3,k=50
r=4,k=289
r=5,k=1682
r=6,k=9801
r=7,k=57122
r=8,k=332929
r=9,k=1940450
r=10,k=11309769
r=11,k=65918162
r=12,k=384199201
r=13,k=2239277042
r=14,k=13051463049
r=15,k=76069501250
r=16,k=443365544449
r=17,k=2584123765442
r=18,k=15061377048201
r=19,k=87784138523762
r=20,k=511643454094369
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-1-24 08:43:38 | 显示全部楼层
呵呵,用perl来解决这个问题,慢是慢了些,不过代码写起来简单:
\$ time ./sqrt2.pl 10000
81591847289355445378979635139673450288728721776828655948135615056686406502435121658131693073300930517938115127003425273013912500991772948349018049534693488674330317169009272206626571632965230206537577769975985558528203259522120276455665092388752741711769705867662361768421201042471990975041133126884975225003385782755323633532826406830766596925143654939381315369508590513234585650549328781053846414937702354568523462837381410825692496016277251062612701136384164163964252518679616965805916333810854978301734392926170895307746309948785167701459231770883149420434273296943976648177995110906037948737369400990719966000336015020937553249718762389484382604743168604573315671872763516189433412086776067745457759275335674538107740890729226393692036732230126609892234123183991598697106526412006563514818870842854731026817347685941198861620341947535125424488959206817175423600718306661938660707803380515318821051405600690349677280707204495009521787815983126274064882180008869625538382295087701241445182968965901792427610416584734301128053083431833743897760102513477860834196613216962974400279658342113062025681478978672035680013050162469069400182268921895060264372309793079118633441947868201091085391285596755272900207301041091226206105112211313567237517253763090312610979502614148211385023107437338827727373150087696870484304868260746796016484811775112215950042559340788216525693462713987374862701722837338685370832442701366882418716368464124870585577544754443851679016205527035864638115771734622786584635066886695496899495406251624369666739938751218850385739963489271156117650160163600549855801428462368378415873561563347460665810729066811119056180763501240913769609367954126982580365081436501617330469901878403169792756218390104870798398382392494547276853375603333496438551202186419885240424998350527903819095314765528542977391450655407840174430701514742596573029258067977416296989924977665554073190899125294715018460264308701048402310176227301917175585272325790933829839028747901468289566176930586385630968065977136333845769470277648031239596988548886420147624668872440864566724921837636528988971046606898943292097136835972468836363393710221631400736553443503254387697531221518584827257418448329096698722821078402765854472650399541359583989508818896274627919405567690289903734562445404224872755237165707508502356124566146678008802464139576669304059487709284753540843139544283887490836052638490541603373974376968374652326191672087017204339740614324176581880627575053040420337619637031547653036148680634611824272100637659584964328859365277622146077225384614031431210527046269381208073027915996366890071751415154438574972593248338496415079123095250615485544749893252460325360254353596858068592146401787588680704258128339119371687968615670158181935125141604439535489247646664195533845904649158779738739751700737707555830817955465088991744608251877213106656446581439731018171346172397331502532271761190377645903193587383718496272134050985948363305425264584572333239736534263144415689700194823576569328770492927187203075001955157092849599552657650007732649468899430675976761870929243817948590138934753355745650971929355121882573306961769980914778893182001397450538286830074716354789837503605714977332118955319381592384930276493417188616858589281288010037046053820564333395894578015973714545347888487915249598552151898029911465505530892419044682877425843321587224659401843603923588047417130959453544413344473603940979859718098162280054824171663204509099217980034256809685398071380209248433944995836823105556773138254770904864530553847332215800009232716921282031334638035421674616184229653412793363600431341420241566626121338887361907614288246096987678592977438354010590460960524588864831332532557166500287697832761212103560216546951111952935792981013759550804778769012200832119989050463902069212286335659816636731037297554866140279151056507351063940073726961091609111102353620358375239220204727884797808324635994425519742214217485347894598131224506138403742129731092989874312641275149825813839903518732695419204303477563162232033685747290952234087014871481911710259281476552083172073643609991602686997150851262661366275177503793412673013513844475523089165179126536257991312423250934658785862583474464828070607699901361738508173418751206645904713930725679332792299112797208337418442995323784736588590057635134500456034098043482906524979107852135231864777342387470797219806717083295451186056405924125711561009213831615563348571176766358394039856358782528202873073973027258813104328482933352734833526489078794816452734996532395175123143836854689055439646222030027094962683716683927762370219017681557773208164916212667286716441272413118600854986890050473843775699528349989588528153042538299523272515433791569716255604516315484936810845610406208912208106128127885338490041123091768250521143286962909830203815250747693270851109429550186225640693836274966668250359765248283126455078051907032327971403968390162449464469884957124325626433305889524488729849695363094484233690991318037570148422410393899743875663354582470249493221847603724392911728930468108856861087652255680004737167904268094176502812561760711959562909134051874017774290266398375784579380706047407050226344145259855195773824256947905746923970721960080815119547312221667179762120525022399052382964866515376151867342179268642553931054132233450716846544299850834893436881762701677698567918377082849822497498717921780236015640438125719435943076659598965547226022898778336628175423797267981598228274059090875648004209969743884609209524816711621974411873188459447057467434958480228287483840155784800038783895248061076740459396334904339474663126029353270902711546423766159053625832270088327174501530971454177754140454473564280344251714968008519345150392643483151496150765421503813693044358196354926717286621785170748116717121303666497344206691401154219870834392472363324296138289601496972920279041458251507829034836314164412642700738385980587741941674702733732525015961948741474525847894858774163733647302392266446651087214107707526379533204315240311301426407954551226248035164666295708188056131595776404759669275893214302926482517408132235844003120448248057463794282904546234171953918356005099504150803299030298555329910917141510057755158561225793002711320247715121219099743082312601497261803050100506382753363383063842234692612301166461967198417768933401819673833488532710597561373451707194476699896103714538981441957136148932797113284670068601625584252973514691733704812861124456739761720531939276927150155728924926322279216451877509130525339689110359330002509259753894973772097843465499781539973807896370454471930389654665544261418883608550869419169801837326215470524396891169345570134645763723139338592773380885381229939928825082156930133377551282437270280311645737122634069160562509141262801928429786472574738636852359902007542604291622366041621072892093000858946535813892918278218097789072322837970524287935160654645996040692377849257177092515743533591450955001147855403588818047853737869356710561804878323478647701372136774059342790657073762907215582316570751581514334222109668231938039424431403474671184681369743277012092787944921198254824897602623290926195642344253961459044801230698412107152197491586020881769306300914353075688696621923135427900569595112904843142894751367949122828931861300723564309947912018367160491417763542996248524074728408799665165840541101784647687127697903468490515525550340953194352702482606740798161056995277968273925866348316432244561687422915764663256786937531565845095532133772335140089496922577424141834364100118690027904725171374182877955054715706967609492597482267871191217593911820499361770303394243140267446280592097356849004572949454112094176231091753976919797377016467968
81591847289355445378979635139673450288728721776828655948135615056686406502435121658131693073300930517938115127003425273013912500991772948349018049534693488674330317169009272206626571632965230206537577769975985558528203259522120276455665092388752741711769705867662361768421201042471990975041133126884975225003385782755323633532826406830766596925143654939381315369508590513234585650549328781053846414937702354568523462837381410825692496016277251062612701136384164163964252518679616965805916333810854978301734392926170895307746309948785167701459231770883149420434273296943976648177995110906037948737369400990719966000336015020937553249718762389484382604743168604573315671872763516189433412086776067745457759275335674538107740890729226393692036732230126609892234123183991598697106526412006563514818870842854731026817347685941198861620341947535125424488959206817175423600718306661938660707803380515318821051405600690349677280707204495009521787815983126274064882180008869625538382295087701241445182968965901792427610416584734301128053083431833743897760102513477860834196613216962974400279658342113062025681478978672035680013050162469069400182268921895060264372309793079118633441947868201091085391285596755272900207301041091226206105112211313567237517253763090312610979502614148211385023107437338827727373150087696870484304868260746796016484811775112215950042559340788216525693462713987374862701722837338685370832442701366882418716368464124870585577544754443851679016205527035864638115771734622786584635066886695496899495406251624369666739938751218850385739963489271156117650160163600549855801428462368378415873561563347460665810729066811119056180763501240913769609367954126982580365081436501617330469901878403169792756218390104870798398382392494547276853375603333496438551202186419885240424998350527903819095314765528542977391450655407840174430701514742596573029258067977416296989924977665554073190899125294715018460264308701048402310176227301917175585272325790933829839028747901468289566176930586385630968065977136333845769470277648031239596988548886420147624668872440864566724921837636528988971046606898943292097136835972468836363393710221631400736553443503254387697531221518584827257418448329096698722821078402765854472650399541359583989508818896274627919405567690289903734562445404224872755237165707508502356124566146678008802464139576669304059487709284753540843139544283887490836052638490541603373974376968374652326191672087017204339740614324176581880627575053040420337619637031547653036148680634611824272100637659584964328859365277622146077225384614031431210527046269381208073027915996366890071751415154438574972593248338496415079123095250615485544749893252460325360254353596858068592146401787588680704258128339119371687968615670158181935125141604439535489247646664195533845904649158779738739751700737707555830817955465088991744608251877213106656446581439731018171346172397331502532271761190377645903193587383718496272134050985948363305425264584572333239736534263144415689700194823576569328770492927187203075001955157092849599552657650007732649468899430675976761870929243817948590138934753355745650971929355121882573306961769980914778893182001397450538286830074716354789837503605714977332118955319381592384930276493417188616858589281288010037046053820564333395894578015973714545347888487915249598552151898029911465505530892419044682877425843321587224659401843603923588047417130959453544413344473603940979859718098162280054824171663204509099217980034256809685398071380209248433944995836823105556773138254770904864530553847332215800009232716921282031334638035421674616184229653412793363600431341420241566626121338887361907614288246096987678592977438354010590460960524588864831332532557166500287697832761212103560216546951111952935792981013759550804778769012200832119989050463902069212286335659816636731037297554866140279151056507351063940073726961091609111102353620358375239220204727884797808324635994425519742214217485347894598131224506138403742129731092989874312641275149825813839903518732695419204303477563162232033685747290952234087014871481911710259281476552083172073643609991602686997150851262661366275177503793412673013513844475523089165179126536257991312423250934658785862583474464828070607699901361738508173418751206645904713930725679332792299112797208337418442995323784736588590057635134500456034098043482906524979107852135231864777342387470797219806717083295451186056405924125711561009213831615563348571176766358394039856358782528202873073973027258813104328482933352734833526489078794816452734996532395175123143836854689055439646222030027094962683716683927762370219017681557773208164916212667286716441272413118600854986890050473843775699528349989588528153042538299523272515433791569716255604516315484936810845610406208912208106128127885338490041123091768250521143286962909830203815250747693270851109429550186225640693836274966668250359765248283126455078051907032327971403968390162449464469884957124325626433305889524488729849695363094484233690991318037570148422410393899743875663354582470249493221847603724392911728930468108856861087652255680004737167904268094176502812561760711959562909134051874017774290266398375784579380706047407050226344145259855195773824256947905746923970721960080815119547312221667179762120525022399052382964866515376151867342179268642553931054132233450716846544299850834893436881762701677698567918377082849822497498717921780236015640438125719435943076659598965547226022898778336628175423797267981598228274059090875648004209969743884609209524816711621974411873188459447057467434958480228287483840155784800038783895248061076740459396334904339474663126029353270902711546423766159053625832270088327174501530971454177754140454473564280344251714968008519345150392643483151496150765421503813693044358196354926717286621785170748116717121303666497344206691401154219870834392472363324296138289601496972920279041458251507829034836314164412642700738385980587741941674702733732525015961948741474525847894858774163733647302392266446651087214107707526379533204315240311301426407954551226248035164666295708188056131595776404759669275893214302926482517408132235844003120448248057463794282904546234171953918356005099504150803299030298555329910917141510057755158561225793002711320247715121219099743082312601497261803050100506382753363383063842234692612301166461967198417768933401819673833488532710597561373451707194476699896103714538981441957136148932797113284670068601625584252973514691733704812861124456739761720531939276927150155728924926322279216451877509130525339689110359330002509259753894973772097843465499781539973807896370454471930389654665544261418883608550869419169801837326215470524396891169345570134645763723139338592773380885381229939928825082156930133377551282437270280311645737122634069160562509141262801928429786472574738636852359902007542604291622366041621072892093000858946535813892918278218097789072322837970524287935160654645996040692377849257177092515743533591450955001147855403588818047853737869356710561804878323478647701372136774059342790657073762907215582316570751581514334222109668231938039424431403474671184681369743277012092787944921198254824897602623290926195642344253961459044801230698412107152197491586020881769306300914353075688696621923135427900569595112904843142894751367949122828931861300723564309947912018367160491417763542996248524074728408799665165840541101784647687127697903468490515525550340953194352702482606740798161056995277968273925866348316432244561687422915764663256786937531565845095532133772335140089496922577424141834364100118690027904725171374182877955054715706967609492597482267871191217593911820499361770303394243140267446280592097356849004572949454112094176231091753976919797377016467969

real    0m11.398s
user    0m11.380s
sys     0m0.000s
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-1-24 08:44:20 | 显示全部楼层
#!/usr/bin/perl
use bigint;

\$N=\$ARGV[0];
\$a=1;
\$b=-1;
for(\$i=2;\$i<=\$N;\$i=\$i+1){
    \$na=\$b-\$a;
    \$nb=2*\$a-\$b;
    \$a=\$na;
    \$b=\$nb;
}

\$a=\$a*\$a*2;
\$b=\$b*\$b;
print "\$a\n\$b\n";

评分

参与人数 1威望 +1 贡献 +1 鲜花 +1 收起 理由
northwolves + 1 + 1 + 1 好简练!!!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-1-24 09:29:53 | 显示全部楼层
我觉得可利用如下共轭等式:
${((sqrt{2}+1)^r+(sqrt{2}-1)^r=2sqrt{k}), ((sqrt{2}+1)^r-(sqrt{2}-1)^r=2sqrt{k-1}) :}$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-1-24 11:20:37 | 显示全部楼层
新安装了PERL,准备好好学习
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-1-24 11:40:29 | 显示全部楼层
可以假设
(sqrt(2)-1)^r  = a(r)*sqrt(2)+b(r)
其中,a(r),b(r)都是整数
那么我们可以用
a(2r)*sqrt(2)+b(2r)=2a(r)b(r)*sqrt(2)+2a(r)*a(r)+b(r)*b(r)
来得出a(2r),b(2r)和a(r)和b(r)的关系。
从而可以有更快的速度。
不过perl我也不是很熟悉,写代码挺费劲,所以就没有实现上面算法了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-1-24 13:16:44 | 显示全部楼层

用 HugeCalc 获得更快的速度

我完全照搬 mathe 3#的算法,只不过调用的是 HugeCalc 大数算法库,速度提升了好几个数量级!

(sqrt(2)-1)^r =sqrt(k) - sqrt(k-1)

(sqrt(2)-1)^r =sqrt(k) - sqrt(k-1)

代码如下:
  1. #include < iostream.h >

  2. #include < HugeCalc.h > // 公共接口
  3. #include < HugeInt.h >  // 10进制系统
  4. #include < HugeIntX.h > // 16进制系统

  5. #pragma message( "automatic link to .../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
  6. #pragma comment( lib, "HugeCalc.lib" )

  7. int main(int argc, char* argv[])
  8. {
  9.     cout << "Call " << HugeCalc::GetVer() << endl;

  10.     if ( HC_LICENSE_NONE == HugeCalc::GetLicenseLevel() )
  11.     {
  12.         cout << "\r\n警告:您未通过 HugeCalc.dll 的许可认证!\r\n" \
  13.             << "\r\n解决方案可选下列方案之一:" \
  14.             << "\r\n    一、请将本程序移动到“/CopyrightByGuoXianqiang/[../]”目录下运行;" \
  15.             << "\r\n    二、或请在 HugeCalc.chm 中进行注册(一劳永逸)。" \
  16.             << endl;
  17.     }
  18.     else
  19.     {
  20.         CHugeInt a, b, k;
  21.         UINT32 i, r;

  22.         cout << "*** [sqrt(2)-1]^r = sqrt(k) - sqrt(k-1) ***"  << endl;
  23.         cout << "input r, output k ...(if r==0, then exit)" << endl;

  24.         for ( ; ; )
  25.         {
  26.             cout << endl << "r = ";
  27.             cin >> r;

  28.             if ( 0 == r ) break;

  29.             HugeCalc::EnableTimer();
  30.             HugeCalc::ResetTimer();

  31.             a = 1;
  32.             b = -1;

  33.             for( i=2; i<=r; ++i )
  34.             {
  35.                 k = a;
  36.                 a.Swap(b) -= b;
  37.                 b.Swap(k) -= a;
  38.             }

  39.             if ( 0 == (1 & r) )
  40.             {
  41.                 k.Swap(b).Pow(2);
  42.             }
  43.             else
  44.             {
  45.                 k.Swap(a).Pow(2) *= 2;
  46.             }

  47.             HugeCalc::EnableTimer( FALSE );

  48.             cout << "k = " << k.GetStr(FS_NORMAL) << endl;
  49.             cout << "computation took " << HugeCalc::GetTimerStr() << endl;
  50.         }
  51.     }

  52.     cout << endl;
  53.     system( "pause" );

  54.     return 0;
  55. }
复制代码
编译好的程序压缩包: (sqrt(2)-1)^r.zip (318.18 KB, 下载次数: 311)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-1-24 13:31:31 | 显示全部楼层
呵呵,这个算法到100,000就比较慢了,上1000,000.
能否用6#的算法写一个呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-1-24 13:36:43 | 显示全部楼层
可以用递归函数:
  1. void GetAB(int r, CHugeInt& a, CHugeInt& b)
  2. {
  3.     if(r==1){
  4.        a=1;
  5.        b=-1;
  6.        return;
  7.     }
  8.     CHugeInt na, nb
  9.     GetAB(r/2, na, nb);
  10.     a=2*na*nb;
  11.     b=2*na*na+nb*nb;
  12.     if(r&1){
  13.        na=a;nb=b;
  14.        a=nb-na;
  15.        b=2*na-nb;
  16.     }
  17. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-1-24 14:53:32 | 显示全部楼层
试着用gmp写了一个上面递归过程的代码,
对于r=1000,000,在我的Linux上需要花费1.2秒(输出重定向)。
产生的数据有765K(一个数字 )
计算r=10,000,000时内存就不够了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|Archiver|数学研发网 ( 苏ICP备07505100号  

GMT+8, 2017-5-1 10:44 , Processed in 0.197935 second(s), 29 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表