Fastest machine?

[Richard Russell]

My fastest machine is an 'Apple Silicon' M1 Mac Mini, on that the million-digit Fibonacci number F(4784969) is calculated in 43 seconds, using the code listed below (running natively, not under Rosetta 2 emulation). That compares with 77 seconds on my fastest Windows machine.

I wonder if anybody can beat that; I would expect a more modern M4 Mac Mini to be even faster. The program is compatible with BBC BASIC for SDL 2.0 or BBC BASIC for Windows, although in the latter case it would need the bigint.bbc library to be copied across.

In principle the program is compatible with the BBC BASIC Console Mode editions as well, but version 0.48 has a bug in the array slicing implementation which probably prevents it running. I hope to publish an update to fix this in the near future.

Code: Select all

      INSTALL @lib$ + "bigint"
      PROCbiginit

      fibo%% = FNbignew(1000000)

      start = TIME
      PROCfibo(4784969, fibo%%)
      finish = TIME
      PRINT (finish-start)/100 " seconds"
      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

[Phil_Thatcham]

I was happy with the speed of my PC.

This task of Richard's took it ~7 minutes.

Now I understand why my Minesweeper times are so poor.

PT

[Richard Russell]

This task of Richard's took it ~7 minutes.

Don't be too disheartened. It's rare for raw computing speed to be important, more often it's going to be display rendering, or file I/O, or some other form of input-output which is the limiting factor and determines the overall speed of a program.

And, to be honest, if raw computing power is your main concern you probably won't be using an interpreted language like BASIC, or JavaScript or Python, for the task. You'll be wanting something 'properly' compiled like C++ for that.

I could have written the 'arbitrary precision integer arithmetic' library in assembly language, but that won't work on an M1 Mac because Apple enforces the hardened runtime on that platform (it won't work in a browser either).

[Richard Russell]

One thing that is particularly interesting about that Fibonacci program (and programs using the bigint arbitrary-precision integer library in general) is that much more use is made of 64-bit operations than is typical for a BBC BASIC program.

This is apparent when comparing its speed when run in 32-bit BBCSDL and 64-bit BBCSDL on the same platform (e.g. Windows). Typically the 64-bit interpreter is significantly slower than the 32-bit interpreter, because it's written in C rather than assembly language.

But that Fibonacci program runs at almost exactly the same speed in 32-bits and 64-bits here, no doubt because the benefit of the 64-bit CPU registers outweighs the penalty from being compiled from C.

Feel free to have both 32-bit and 64-bit versions installed so you can compare them. The 64-bit version isn't available as a Windows Installer, but only as a Zip file that must be unpacked into its own directory.

[kirkkaf13@gmail.com]

For me 85.5 seconds. This is using BB4W on my work laptop with the follow specs.

Processor 11th Gen Intel(R) Core(TM) i7-11850H @ 2.50GHz 2.50 GHz
Installed RAM 32.0 GB (31.7 GB usable)
System type 64-bit operating system, x64-based processor

[Richard Russell]

Processor 11th Gen Intel(R) Core(TM) i7-11850H @ 2.50GHz 2.50 GHz

Mine is a 12th Gen Core i7-1260U which can go up to a clock frequency of about 4.7 GHz.

I wonder if anybody has a modern, fast, AMD Ryzen CPU because that might well be faster - although I doubt that it would beat the 'Apple Silicon' M1 CPU which is way ahead of this PC, despite not being the latest Apple chip.

Unfortunately because Apple enforce the hardened runtime (hence the assembler can't be used) neither the BBCSDL debugger nor profiler works - and nor does the timerlib.bbc library. This is why I still recommend running the x86 version in Rosetta 2 emulation.

[RNBW]

I've carried out a check on 2 machines
Asus Zenbook 14 UX425EA i5 running Windows 11 Home 148.89 secs
Macbook Air M3 69.01 secs.

[Richard Russell]

Macbook Air M3 69.01 secs.

Native ARM64 or Rosetta 2 x86 emulation? If the latter it's an impressive demonstration of just how good that emulator is.

[Richard Russell]

Native ARM64 or Rosetta 2 x86 emulation? If the latter it's an impressive demonstration of just how good that emulator is.

Native ARM64 on the M3 ought to beat (or at least match) the 43 seconds I get on my M1, theoretically. I've found figures of 4.05 GHz for the M3 clock versus 3.2 GHz for the M1, so my prediction would have been that the M3 might run the Fibonacci task in around 34 seconds.

[svein]

What do I need to do to get the correct Fibonacci sequence from your program ?
Just printing the content of fibo%% does not work.

Regards Svein

Code: Select all

      INSTALL @lib$ + "bigint"
      PROCbiginit

      fibo%% = FNbignew(1000000)

      start = TIME
      REM PROCfibo(4784969, fibo%%)
      FOR N%=1 TO 20
        PROCfibo(N%, fibo%%)
        PRINT FNbigustr(fibo%%)
      NEXT N%
      finish = TIME
      PRINT (finish-start)/100 " seconds"
      END

      REM Fibonacci calculation using the doubling algorithm:
      DEF PROCfibo(N%, f%%)
      LOCAL S%, a%%, b%%, c%%
      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 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=1 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