Fastest machine?

[Richard Russell]

What do I need to do to get the correct Fibonacci sequence from your program ?

When you say "the Fibonacci sequence", do you mean consecutive Fibonacci numbers over a given range? For example, this program will list the Fibonacci numbers from F(300) to F(320) inclusive:

Code: Select all

      INSTALL @lib$ + "bigint"
      PROCbiginit

      fibo%% = FNbignew(100)

      FOR F% = 300 TO 320
        PROCfibo(F%, fibo%%)
        PRINT "F(" ;F% ") = " FNbigstr(fibo%%)
      NEXT
      END

      REM Fibonacci calculation using the doubling algorithm:
      DEF PROCfibo(N%, f%%)
      LOCAL S%, a%%, b%%, c%%
      IF N% N% -= 1 ELSE PROCbigval(f%%, "0") : ENDPROC

      S% = N% * LOG((SQR(5) + 1) / 2) + 1
      a%% = FNbignew(S%) : b%% = FNbignew(S%)
      PROCfibo2(N% DIV 2, a%%, b%%)
      c%% = FNbignew(S%)

      IF (N% AND 1) = 0 THEN
        REM f = b*(2*b-a)-(-1)^k
        PROCbiguadd(f%%, b%%, b%%)
        PROCbigusub(c%%, f%%, a%%)
        PROCbigumul(f%%, b%%, c%%)
        IF N% MOD 4=0 THEN PROCbigudec(f%%) ELSE PROCbiguinc(f%%)
      ELSE
        REM f = b*(2*a+b)
        PROCbiguadd(f%%, a%%, a%%)
        PROCbiguadd(c%%, f%%, b%%)
        PROCbigumul(f%%, b%%, c%%)
      ENDIF
      ENDPROC

      DEF PROCfibo2(N%, f%%, g%%)
      LOCAL S%, a%%, b%%, c%%, d%%
      S% = N% * LOG((SQR(5) + 1) / 2) + 1
      IF N% = 0 THEN
        PROCbigval(f%%, "0") : REM f = 0
        PROCbigval(g%%, "1") : REM g = 1
        ENDPROC
      ENDIF
      a%% = FNbignew(S%) : b%% = FNbignew(S%)
      PROCfibo2(N% DIV 2, a%%, b%%)
      c%% = FNbignew(S%) : d%% = FNbignew(S%)

      IF N% AND 1 THEN
        REM f = a*(2*a+b)+(-1)^k
        REM g = b*(2*a+b)
        PROCbiguadd(c%%, a%%, a%%)
        PROCbiguadd(d%%, c%%, b%%)
        PROCbigumul(g%%, b%%, d%%)
        PROCbigumul(f%%, a%%, d%%)
        IF N% MOD 4 = 1 THEN PROCbiguinc(f%%) ELSE PROCbigudec(f%%)
      ELSE
        REM f = a*(2*b-a)
        REM g = b*(2*b-a)-(-1)^k
        PROCbiguadd(c%%, b%%, b%%)
        PROCbigusub(d%%, c%%, a%%)
        PROCbigumul(f%%, a%%, d%%)
        PROCbigumul(g%%, b%%, d%%)
        IF N% MOD 4 = 0 THEN PROCbigudec(g%%) ELSE PROCbiguinc(g%%)
      ENDIF
      ENDPROC

This outputs:

Code: Select all

F(300) = 222232244629420445529739893461909967206666939096499764990979600
F(301) = 359579325206583560961765665172189099052367214309267232255589801
F(302) = 581811569836004006491505558634099066259034153405766997246569401
F(303) = 941390895042587567453271223806288165311401367715034229502159202
F(304) = 1523202464878591573944776782440387231570435521120801226748728603
F(305) = 2464593359921179141398048006246675396881836888835835456250887805
F(306) = 3987795824799770715342824788687062628452272409956636682999616408
F(307) = 6452389184720949856740872794933738025334109298792472139250504213
F(308) = 10440185009520720572083697583620800653786381708749108822250120621
F(309) = 16892574194241670428824570378554538679120491007541580961500624834
F(310) = 27332759203762391000908267962175339332906872716290689783750745455
F(311) = 44225333398004061429732838340729878012027363723832270745251370289
F(312) = 71558092601766452430641106302905217344934236440122960529002115744
F(313) = 115783425999770513860373944643635095356961600163955231274253486033
F(314) = 187341518601536966291015050946540312701895836604078191803255601777
F(315) = 303124944601307480151388995590175408058857436768033423077509087810
F(316) = 490466463202844446442404046536715720760753273372111614880764689587
F(317) = 793591407804151926593793042126891128819610710140145037958273777397
F(318) = 1284057871006996373036197088663606849580363983512256652839038466984
F(319) = 2077649278811148299629990130790497978399974693652401690797312244381
F(320) = 3361707149818144672666187219454104827980338677164658343636350711365

You can check these against this website.

[svein]

Yes, now it is working, thx.

Regards Svein

[jinx100]

I tried another way to obtain the fibonacci numbers F(n) but get storage errors for large n. Am I abusing the bigint library by assigning too many large integers? If A = [[2 1][1 0]] Then A^n = [[F(n+1) F(n)][F(n) F(n-1)]].

Code: Select all

       REM Now working right but slow!
      REM Set goal%% for desired Fb(goal%%)
      REM Speed tweaks but still 7 times slower than RR

      INSTALL @lib$ + "bigint"
      PROCbiginit

      size%% = 1000000 : REM max decimal digits
      REM initial fibonacci matrix
      fibo02%% = FNbignew(size%%) : PROCbiguval(fibo02%%,"1")
      fibo01%% = FNbignew(size%%) : PROCbiguval(fibo01%%,"1")
      fibo00%% = FNbignew(size%%) : PROCbigval(fibo00%%,"0")

      REM initial result matrix indentity
      res2%% = FNbignew(size%%) : PROCbiguval(res2%%,"1")
      res1%% = FNbignew(size%%) : PROCbiguval(res1%%,"0")
      res0%% = FNbignew(size%%) : PROCbiguval(res0%%,"1")

      REM temporary products
      tf04%% = FNbignew(size%%)
      tf03%% = FNbignew(size%%)
      tf02%% = FNbignew(size%%)
      tf01%% = FNbignew(size%%)
      tf00%% = FNbignew(size%%)

      REM Finds Fb(goal%%) use 4784969 for 10^6 digits
      goal%%=249998

      REM Stop matrix squaring at half goal
      IF goal%% MOD 2 THEN
        test%%=(goal%%-1)/2
        odd_up%=1
      ELSE
        test%%=goal%%/2
        odd_up%=0
      ENDIF

      Time1=TIME
      start%=LOG(test%%)/LOG(2)
      a1%% = test%%
      DIM mrk%(start%)

      FOR I=start% TO 0 STEP -1
        IF a1%% >= 2^I THEN
          mrk%(I)=1
          a1%% = a1%%-2^I
        ELSE
          mrk%(I)=0
        ENDIF
      NEXT I

      FOR I=0 TO start%
        IF mrk%(I)=1 PROCmatup
        IF I < start% PROCmatsqr
        PRINT "  "+STR$(I);
      NEXT I
      PRINT

      REM Boost to goal
      IF odd_up% THEN
        REM finds Fb(2n+1)
        PROCbigumul(tf04%%,res1%%,res1%%)
        PROCbigumul(tf03%%,res2%%,res2%%)
        PROCbiguadd(tf00%%,tf03%%,tf04%%)
      ELSE
        REM find Fb(2n)
        PROCbiguadd(tf04%%,res2%%,res0%%)
        PROCbigumul(tf00%%,tf04%%,res1%%)
      ENDIF

      Time2=TIME
      PRINT " F("+STR$(goal%%)+") = "+FNbigustr(tf00%%)
      PRINT " F("+STR$(goal%%)+")   "+"Elapsed = "+STR$((Time2-Time1)/100)+" sec"

      END


      DEF PROCmatsqr
      PROCbigumul(tf04%%,fibo02%%,fibo02%%)
      PROCbigumul(tf02%%,fibo01%%,fibo01%%)
      PROCbigumul(tf00%%,fibo00%%,fibo00%%)
      PROCbiguadd(fibo02%%,tf04%%,tf02%%)
      PROCbiguadd(fibo00%%,tf02%%,tf00%%)
      PROCbigusub(fibo01%%,fibo02%%,fibo00%%)
      ENDPROC


      DEF PROCmatup
      PROCbigumul(tf04%%,res2%%,fibo02%%)
      PROCbigumul(tf02%%,res1%%,fibo01%%)
      PROCbigumul(tf00%%,res0%%,fibo00%%)
      PROCbiguadd(res2%%,tf04%%,tf02%%)
      PROCbiguadd(res0%%,tf02%%,tf00%%)
      PROCbigusub(res1%%,res2%%,res0%%)
      ENDPROC

See https://cp-algorithms.com/algebra/fibon ... mbers.html for reference. Any ideas?

EDIT: Now works but very slowly. Fixed one error in program and added timer.
EDIT2: Some speed tweaks but still slow

[Richard Russell]

I tried another way to obtain the fibonacci numbers F(n) but get storage errors for large n.

The code you listed does not result in any errors when run here. Are you sure you are using the latest version of bigint.bbc (with the fix for multiplying two numbers with hugely different magnitudes) as discussed in this post?

[jinx100]

I am using BBC Basic 1.41b. The error is "DIM space in module C:\Program Files (x86)\BBC BASIC for SDL 2.0\lib\bigint" for the 32 bit version and Windows error "No room" for the 64 bit version.

I'll try some different machines.

[Richard Russell]

I am using BBC Basic 1.41b.

Yes, but my question was "are you using the latest version of bigint.bbc"? As discussed in the post to which I linked, the version of the library supplied with v1.41b is not the latest version and it will fail if you try to multiply two numbers which differ in magnitude by more than 10^900. Although that's not very likely, and fibo.bbc doesn't do so, maybe your program does.

To be on the safe side update the library anyway.

[jinx100]

That was it! Here's the output for F(4784969).

Code: Select all

27713384595810894156656807388842727402625408575473171452579300266169468247611373
19191226030554596449671168428709778862907071057547615642588887534827024965619670
43826203905060748538661441257852165419183043707033206741220476815151186056137686
27931758799167689604764499610957597174078314132600918169399235819575106779109458
78563454609331516481608111182548176550103536879473595185375904922028495432830899
66634319665424182216202887941412570630291526932807797368672737335530305968771259
18695149113624087335966478379109692781417376358669437245726593051968211418160327
27724745091442261099651608320382327660427549338960023693097715002894828172001803
99740774538186276118605730524507859843844199794266669828181122817209360961086984
51371479732429045587798735593374163891719733377456723495989000720333689828064931
00322454055083153503449435598974836491286057109036614296284491445681052193562376
25658415014101293140337565015430256763888266288709266971470153673143448028447212
08085624691894208584470849352534213431952051432568384297049458344968460426454831
85219974831155081001371567033702142331064285603681277154135969609290352753075056
21865719644193239346433482629593365816660847028469222537372537389759635213274675
49170969332490413427161326483513063589602769123797795483596621239746731789613703
80669138017064573175529579344050069967214425788878450757018865691080604649238041
66066897229784189944141095595219909323066251522840105111481232102953120783287687
00874545409278984898908060670341969316222528930570359209301305520382399319746157
15617623206204585291487968755147324883784916338945806361951766313865956891695455
56380146224997856735343654066674058071716776321698821664433007403071989146318014
97368536850012751520768753799363309303918159648648853534071674748565392115006997
06378405156269
 Elapsed = 4271.27 sec
>

Your method takes 106.21 seconds and mine is a bit slower at 4271.27 seconds!

[Richard Russell]

Your method takes 106.21 seconds and mine is a bit slower at 4271.27 seconds!

I can't take any credit for the method! Your result is correct, judging by the last few digits, which is good.