快速求(sqrt(2)-1)的幂展开形式

northwolves

将(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

mathe

呵呵，用perl来解决这个问题，慢是慢了些，不过代码写起来简单:
\$ time ./sqrt2.pl 10000
81591847289355445378979635139673450288728721776828655948135615056686406502435121658131693073300930517938115127003425273013912500991772948349018049534693488674330317169009272206626571632965230206537577769975985558528203259522120276455665092388752741711769705867662361768421201042471990975041133126884975225003385782755323633532826406830766596925143654939381315369508590513234585650549328781053846414937702354568523462837381410825692496016277251062612701136384164163964252518679616965805916333810854978301734392926170895307746309948785167701459231770883149420434273296943976648177995110906037948737369400990719966000336015020937553249718762389484382604743168604573315671872763516189433412086776067745457759275335674538107740890729226393692036732230126609892234123183991598697106526412006563514818870842854731026817347685941198861620341947535125424488959206817175423600718306661938660707803380515318821051405600690349677280707204495009521787815983126274064882180008869625538382295087701241445182968965901792427610416584734301128053083431833743897760102513477860834196613216962974400279658342113062025681478978672035680013050162469069400182268921895060264372309793079118633441947868201091085391285596755272900207301041091226206105112211313567237517253763090312610979502614148211385023107437338827727373150087696870484304868260746796016484811775112215950042559340788216525693462713987374862701722837338685370832442701366882418716368464124870585577544754443851679016205527035864638115771734622786584635066886695496899495406251624369666739938751218850385739963489271156117650160163600549855801428462368378415873561563347460665810729066811119056180763501240913769609367954126982580365081436501617330469901878403169792756218390104870798398382392494547276853375603333496438551202186419885240424998350527903819095314765528542977391450655407840174430701514742596573029258067977416296989924977665554073190899125294715018460264308701048402310176227301917175585272325790933829839028747901468289566176930586385630968065977136333845769470277648031239596988548886420147624668872440864566724921837636528988971046606898943292097136835972468836363393710221631400736553443503254387697531221518584827257418448329096698722821078402765854472650399541359583989508818896274627919405567690289903734562445404224872755237165707508502356124566146678008802464139576669304059487709284753540843139544283887490836052638490541603373974376968374652326191672087017204339740614324176581880627575053040420337619637031547653036148680634611824272100637659584964328859365277622146077225384614031431210527046269381208073027915996366890071751415154438574972593248338496415079123095250615485544749893252460325360254353596858068592146401787588680704258128339119371687968615670158181935125141604439535489247646664195533845904649158779738739751700737707555830817955465088991744608251877213106656446581439731018171346172397331502532271761190377645903193587383718496272134050985948363305425264584572333239736534263144415689700194823576569328770492927187203075001955157092849599552657650007732649468899430675976761870929243817948590138934753355745650971929355121882573306961769980914778893182001397450538286830074716354789837503605714977332118955319381592384930276493417188616858589281288010037046053820564333395894578015973714545347888487915249598552151898029911465505530892419044682877425843321587224659401843603923588047417130959453544413344473603940979859718098162280054824171663204509099217980034256809685398071380209248433944995836823105556773138254770904864530553847332215800009232716921282031334638035421674616184229653412793363600431341420241566626121338887361907614288246096987678592977438354010590460960524588864831332532557166500287697832761212103560216546951111952935792981013759550804778769012200832119989050463902069212286335659816636731037297554866140279151056507351063940073726961091609111102353620358375239220204727884797808324635994425519742214217485347894598131224506138403742129731092989874312641275149825813839903518732695419204303477563162232033685747290952234087014871481911710259281476552083172073643609991602686997150851262661366275177503793412673013513844475523089165179126536257991312423250934658785862583474464828070607699901361738508173418751206645904713930725679332792299112797208337418442995323784736588590057635134500456034098043482906524979107852135231864777342387470797219806717083295451186056405924125711561009213831615563348571176766358394039856358782528202873073973027258813104328482933352734833526489078794816452734996532395175123143836854689055439646222030027094962683716683927762370219017681557773208164916212667286716441272413118600854986890050473843775699528349989588528153042538299523272515433791569716255604516315484936810845610406208912208106128127885338490041123091768250521143286962909830203815250747693270851109429550186225640693836274966668250359765248283126455078051907032327971403968390162449464469884957124325626433305889524488729849695363094484233690991318037570148422410393899743875663354582470249493221847603724392911728930468108856861087652255680004737167904268094176502812561760711959562909134051874017774290266398375784579380706047407050226344145259855195773824256947905746923970721960080815119547312221667179762120525022399052382964866515376151867342179268642553931054132233450716846544299850834893436881762701677698567918377082849822497498717921780236015640438125719435943076659598965547226022898778336628175423797267981598228274059090875648004209969743884609209524816711621974411873188459447057467434958480228287483840155784800038783895248061076740459396334904339474663126029353270902711546423766159053625832270088327174501530971454177754140454473564280344251714968008519345150392643483151496150765421503813693044358196354926717286621785170748116717121303666497344206691401154219870834392472363324296138289601496972920279041458251507829034836314164412642700738385980587741941674702733732525015961948741474525847894858774163733647302392266446651087214107707526379533204315240311301426407954551226248035164666295708188056131595776404759669275893214302926482517408132235844003120448248057463794282904546234171953918356005099504150803299030298555329910917141510057755158561225793002711320247715121219099743082312601497261803050100506382753363383063842234692612301166461967198417768933401819673833488532710597561373451707194476699896103714538981441957136148932797113284670068601625584252973514691733704812861124456739761720531939276927150155728924926322279216451877509130525339689110359330002509259753894973772097843465499781539973807896370454471930389654665544261418883608550869419169801837326215470524396891169345570134645763723139338592773380885381229939928825082156930133377551282437270280311645737122634069160562509141262801928429786472574738636852359902007542604291622366041621072892093000858946535813892918278218097789072322837970524287935160654645996040692377849257177092515743533591450955001147855403588818047853737869356710561804878323478647701372136774059342790657073762907215582316570751581514334222109668231938039424431403474671184681369743277012092787944921198254824897602623290926195642344253961459044801230698412107152197491586020881769306300914353075688696621923135427900569595112904843142894751367949122828931861300723564309947912018367160491417763542996248524074728408799665165840541101784647687127697903468490515525550340953194352702482606740798161056995277968273925866348316432244561687422915764663256786937531565845095532133772335140089496922577424141834364100118690027904725171374182877955054715706967609492597482267871191217593911820499361770303394243140267446280592097356849004572949454112094176231091753976919797377016467968
81591847289355445378979635139673450288728721776828655948135615056686406502435121658131693073300930517938115127003425273013912500991772948349018049534693488674330317169009272206626571632965230206537577769975985558528203259522120276455665092388752741711769705867662361768421201042471990975041133126884975225003385782755323633532826406830766596925143654939381315369508590513234585650549328781053846414937702354568523462837381410825692496016277251062612701136384164163964252518679616965805916333810854978301734392926170895307746309948785167701459231770883149420434273296943976648177995110906037948737369400990719966000336015020937553249718762389484382604743168604573315671872763516189433412086776067745457759275335674538107740890729226393692036732230126609892234123183991598697106526412006563514818870842854731026817347685941198861620341947535125424488959206817175423600718306661938660707803380515318821051405600690349677280707204495009521787815983126274064882180008869625538382295087701241445182968965901792427610416584734301128053083431833743897760102513477860834196613216962974400279658342113062025681478978672035680013050162469069400182268921895060264372309793079118633441947868201091085391285596755272900207301041091226206105112211313567237517253763090312610979502614148211385023107437338827727373150087696870484304868260746796016484811775112215950042559340788216525693462713987374862701722837338685370832442701366882418716368464124870585577544754443851679016205527035864638115771734622786584635066886695496899495406251624369666739938751218850385739963489271156117650160163600549855801428462368378415873561563347460665810729066811119056180763501240913769609367954126982580365081436501617330469901878403169792756218390104870798398382392494547276853375603333496438551202186419885240424998350527903819095314765528542977391450655407840174430701514742596573029258067977416296989924977665554073190899125294715018460264308701048402310176227301917175585272325790933829839028747901468289566176930586385630968065977136333845769470277648031239596988548886420147624668872440864566724921837636528988971046606898943292097136835972468836363393710221631400736553443503254387697531221518584827257418448329096698722821078402765854472650399541359583989508818896274627919405567690289903734562445404224872755237165707508502356124566146678008802464139576669304059487709284753540843139544283887490836052638490541603373974376968374652326191672087017204339740614324176581880627575053040420337619637031547653036148680634611824272100637659584964328859365277622146077225384614031431210527046269381208073027915996366890071751415154438574972593248338496415079123095250615485544749893252460325360254353596858068592146401787588680704258128339119371687968615670158181935125141604439535489247646664195533845904649158779738739751700737707555830817955465088991744608251877213106656446581439731018171346172397331502532271761190377645903193587383718496272134050985948363305425264584572333239736534263144415689700194823576569328770492927187203075001955157092849599552657650007732649468899430675976761870929243817948590138934753355745650971929355121882573306961769980914778893182001397450538286830074716354789837503605714977332118955319381592384930276493417188616858589281288010037046053820564333395894578015973714545347888487915249598552151898029911465505530892419044682877425843321587224659401843603923588047417130959453544413344473603940979859718098162280054824171663204509099217980034256809685398071380209248433944995836823105556773138254770904864530553847332215800009232716921282031334638035421674616184229653412793363600431341420241566626121338887361907614288246096987678592977438354010590460960524588864831332532557166500287697832761212103560216546951111952935792981013759550804778769012200832119989050463902069212286335659816636731037297554866140279151056507351063940073726961091609111102353620358375239220204727884797808324635994425519742214217485347894598131224506138403742129731092989874312641275149825813839903518732695419204303477563162232033685747290952234087014871481911710259281476552083172073643609991602686997150851262661366275177503793412673013513844475523089165179126536257991312423250934658785862583474464828070607699901361738508173418751206645904713930725679332792299112797208337418442995323784736588590057635134500456034098043482906524979107852135231864777342387470797219806717083295451186056405924125711561009213831615563348571176766358394039856358782528202873073973027258813104328482933352734833526489078794816452734996532395175123143836854689055439646222030027094962683716683927762370219017681557773208164916212667286716441272413118600854986890050473843775699528349989588528153042538299523272515433791569716255604516315484936810845610406208912208106128127885338490041123091768250521143286962909830203815250747693270851109429550186225640693836274966668250359765248283126455078051907032327971403968390162449464469884957124325626433305889524488729849695363094484233690991318037570148422410393899743875663354582470249493221847603724392911728930468108856861087652255680004737167904268094176502812561760711959562909134051874017774290266398375784579380706047407050226344145259855195773824256947905746923970721960080815119547312221667179762120525022399052382964866515376151867342179268642553931054132233450716846544299850834893436881762701677698567918377082849822497498717921780236015640438125719435943076659598965547226022898778336628175423797267981598228274059090875648004209969743884609209524816711621974411873188459447057467434958480228287483840155784800038783895248061076740459396334904339474663126029353270902711546423766159053625832270088327174501530971454177754140454473564280344251714968008519345150392643483151496150765421503813693044358196354926717286621785170748116717121303666497344206691401154219870834392472363324296138289601496972920279041458251507829034836314164412642700738385980587741941674702733732525015961948741474525847894858774163733647302392266446651087214107707526379533204315240311301426407954551226248035164666295708188056131595776404759669275893214302926482517408132235844003120448248057463794282904546234171953918356005099504150803299030298555329910917141510057755158561225793002711320247715121219099743082312601497261803050100506382753363383063842234692612301166461967198417768933401819673833488532710597561373451707194476699896103714538981441957136148932797113284670068601625584252973514691733704812861124456739761720531939276927150155728924926322279216451877509130525339689110359330002509259753894973772097843465499781539973807896370454471930389654665544261418883608550869419169801837326215470524396891169345570134645763723139338592773380885381229939928825082156930133377551282437270280311645737122634069160562509141262801928429786472574738636852359902007542604291622366041621072892093000858946535813892918278218097789072322837970524287935160654645996040692377849257177092515743533591450955001147855403588818047853737869356710561804878323478647701372136774059342790657073762907215582316570751581514334222109668231938039424431403474671184681369743277012092787944921198254824897602623290926195642344253961459044801230698412107152197491586020881769306300914353075688696621923135427900569595112904843142894751367949122828931861300723564309947912018367160491417763542996248524074728408799665165840541101784647687127697903468490515525550340953194352702482606740798161056995277968273925866348316432244561687422915764663256786937531565845095532133772335140089496922577424141834364100118690027904725171374182877955054715706967609492597482267871191217593911820499361770303394243140267446280592097356849004572949454112094176231091753976919797377016467969

real    0m11.398s
user    0m11.380s
sys     0m0.000s

mathe

#!/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";

gxqcn

我觉得可利用如下共轭等式：
${((sqrt{2}+1)^r+(sqrt{2}-1)^r=2sqrt{k}), ((sqrt{2}+1)^r-(sqrt{2}-1)^r=2sqrt{k-1}) :}$

northwolves

新安装了PERL,准备好好学习

mathe

可以假设
（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我也不是很熟悉，写代码挺费劲，所以就没有实现上面算法了。

gxqcn

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

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

代码如下：

1. #include < iostream.h >
   
2. 
   
3. #include < HugeCalc.h > // 公共接口
   
4. #include < HugeInt.h >  // 10进制系统
   
5. #include < HugeIntX.h > // 16进制系统
   
6. 
   
7. #pragma message( "automatic link to .../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
   
8. #pragma comment( lib, "HugeCalc.lib" )
   
9. 
   
10. int main(int argc, char* argv[])
    
11. {
    
12.     cout << "Call " << HugeCalc::GetVer() << endl;
    
13. 
    
14.     if ( HC_LICENSE_NONE == HugeCalc::GetLicenseLevel() )
    
15.     {
    
16.         cout << "\r\n警告：您未通过 HugeCalc.dll 的许可认证！\r\n" \
    
17.             << "\r\n解决方案可选下列方案之一：" \
    
18.             << "\r\n    一、请将本程序移动到“/CopyrightByGuoXianqiang/[../]”目录下运行；" \
    
19.             << "\r\n    二、或请在 HugeCalc.chm 中进行注册（一劳永逸）。" \
    
20.             << endl;
    
21.     }
    
22.     else
    
23.     {
    
24.         CHugeInt a, b, k;
    
25.         UINT32 i, r;
    
26. 
    
27.         cout << "*** [sqrt(2)-1]^r = sqrt(k) - sqrt(k-1) ***"  << endl;
    
28.         cout << "input r, output k ...(if r==0, then exit)" << endl;
    
29. 
    
30.         for ( ; ; )
    
31.         {
    
32.             cout << endl << "r = ";
    
33.             cin >> r;
    
34. 
    
35.             if ( 0 == r ) break;
    
36. 
    
37.             HugeCalc::EnableTimer();
    
38.             HugeCalc::ResetTimer();
    
39. 
    
40.             a = 1;
    
41.             b = -1;
    
42. 
    
43.             for( i=2; i<=r; ++i )
    
44.             {
    
45.                 k = a;
    
46.                 a.Swap(b) -= b;
    
47.                 b.Swap(k) -= a;
    
48.             }
    
49. 
    
50.             if ( 0 == (1 & r) )
    
51.             {
    
52.                 k.Swap(b).Pow(2);
    
53.             }
    
54.             else
    
55.             {
    
56.                 k.Swap(a).Pow(2) *= 2;
    
57.             }
    
58. 
    
59.             HugeCalc::EnableTimer( FALSE );
    
60. 
    
61.             cout << "k = " << k.GetStr(FS_NORMAL) << endl;
    
62.             cout << "computation took " << HugeCalc::GetTimerStr() << endl;
    
63.         }
    
64.     }
    
65. 
    
66.     cout << endl;
    
67.     system( "pause" );
    
68. 
    
69.     return 0;
    
70. }

复制代码

编译好的程序压缩包： (sqrt(2)-1)^r.zip (318.18 KB, 下载次数: 311)

2008-1-24 13:37 上传

点击文件名下载附件
(sqrt(2)-1)^r =sqrt(k) - sqrt(k-1) （注：非 HugeCalc 注册用户也可正常运行）

mathe

呵呵，这个算法到100,000就比较慢了，上1000,000.
能否用6#的算法写一个呢？

mathe

可以用递归函数：

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. }

复制代码

mathe

试着用gmp写了一个上面递归过程的代码，
对于r=1000,000,在我的Linux上需要花费1.2秒（输出重定向）。
产生的数据有765K(一个数字 )
计算r=10,000,000时内存就不够了。