Pi 4 and the Million Digit Fibonacci Challenge.

[Heater]

It's going to to take me a while to get hold of a Pi 4 but I'm itching to know how well it performs the Million Digit Fibonacci Challenge as a kind of relative benchmark.

As you may have noticed there has been a little challenge going on to write code, in the language of your choice, that can calculate the first Fibonacci number with one million decimal digits. That is to say the 4784969th Fibonacci number.

There are a few requirements for the challenge:

1) To output the one million digit result as a string of decimal digits.

2) The use of libraries, modules, extensions that are not supplied as a standard part of the language is not allowed.

3) Whilst solutions written in languages that only have closed source, proprietary implementations are welcome they will not be added to my Million Digit Challenge Github repository.

4) Must run on the Raspberry Pi.

5) Perhaps some other rules I have forgotten!

Note that the challenge was not intended as a benchmark and performance is not the most significant criteria. The intention was simply to demonstrate how easy it is to create a solution in various languages, how elegant and readable the solutions are for others. But of course, now the Pi 4 is out I'm curious as to how it compares performance wise.

Since the challenge was thrown down at the beginning of the year solutions have been presented in 18 different languages. Sometimes multiple solutions in the same language, sometimes multiple dialects of the same language.

ALGOL60
BASIC
Haskell
bc
c++
c
go
java
javascript
julia
maxima
pari-gp
prolog
python
rexx
scala
scheme
smalltalk

The challenge forum thread has been continuing here: https://www.raspberrypi.org/forums/view ... &start=600

The Challenge github repository is here: https://github.com/ZiCog/fibo_4784969

I put up an online Fibonacci number calculator here: https://otaniemi.conveqs.fi:3000/public/fibo.html As far as I know it is the only such calculator online that can produce a million digit result. I'm still in two minds as to whether it qualifies for the challenge because whilst the fibo algorithm is written in JS the big number arithmetic is my C++ big integer class compiled to Web Assembly. Still, it's pretty impressive to be able to do that in the browser itself.

So how about it, any kind and curious souls up to running any of those codes on a Pi 4 and letting us know the timings?

We simply use the "time" command to do that. For example (on my PC):

Code: Select all

$ time node hfibo.js | head -c 32; time node hfibo.js | tail -c 32
10727395641800477229364813596225
real    1m16.210s
user    1m15.141s
sys     0m0.156s
4856539211500699706378405156269

real    1m15.948s
user    1m15.219s
sys     0m0.156s

Of course now solutions in languages we don't have yet would also be interesting....

Oh, and results from anyone with a 64 bit OS on the Pi 4 would be interesting as well.

[jahboater]

This is the Pi4 4GB result for the plain C code (fibonacci.c)
GCC 9.1

Code: Select all

$ gcc -O3 -s fibo.c -o fibo
$ time ./fibo | head -c 32; time ./fibo | tail -c 32
10727395641800477229364813596225
real	0m8.500s
user	0m8.468s
sys	0m0.039s
4856539211500699706378405156269

real	0m8.480s
user	0m8.463s
sys	0m0.021s

This is the time for my old Pi3B+ (same compiler)

Code: Select all

$ gcc -O3 -s fibo.c -o fibo
$ time ./fibo | head -c 32; time ./fibo | tail -c 32
10727395641800477229364813596225
real	0m16.804s
user	0m16.797s
sys	0m0.010s
4856539211500699706378405156269

real	0m16.864s
user	0m16.849s
sys	0m0.016s

[jahboater]

Incidentally I think the JS output may be slightly out.
The "tail" output is missing the first digit and there is a spurious "n" at the end.

[Heater]

That "n" is Javascript's way of indicating it is displaying a BigInt in console.log(). That "n" then displaces a digit in the display.

According to the rules I should fix it by adding .toString() when printing the result. That costs me another 5 seconds.

Which is really annoying, the calculation takes 14.1 seconds here. Displaying the result takes one minute!

See fixed results in the first post.

[jamesh]

This is the Pi4 4GB result for the plain C code (fibonacci.c)
GCC 9.1

Code: Select all

$ gcc -O3 -s fibo.c -o fibo
$ time ./fibo | head -c 32; time ./fibo | tail -c 32
10727395641800477229364813596225
real	0m8.500s
user	0m8.468s
sys	0m0.039s
4856539211500699706378405156269

real	0m8.480s
user	0m8.463s
sys	0m0.021s

This is the time for my old Pi3B+ (same compiler)

Code: Select all

$ gcc -O3 -s fibo.c -o fibo
$ time ./fibo | head -c 32; time ./fibo | tail -c 32
10727395641800477229364813596225
real	0m16.804s
user	0m16.797s
sys	0m0.010s
4856539211500699706378405156269

real	0m16.864s
user	0m16.849s
sys	0m0.016s

That's a pretty good improvement!

[ejolson]

This is the Pi4 4GB result for the plain C code (fibonacci.c)
GCC 9.1

Code: Select all

$ gcc -O3 -s fibo.c -o fibo
$ time ./fibo | head -c 32; time ./fibo | tail -c 32
10727395641800477229364813596225
real	0m8.500s
user	0m8.468s
sys	0m0.039s
4856539211500699706378405156269

real	0m8.480s
user	0m8.463s
sys	0m0.021s

This is the time for my old Pi3B+ (same compiler)

Code: Select all

$ gcc -O3 -s fibo.c -o fibo
$ time ./fibo | head -c 32; time ./fibo | tail -c 32
10727395641800477229364813596225
real	0m16.804s
user	0m16.797s
sys	0m0.010s
4856539211500699706378405156269

real	0m16.864s
user	0m16.849s
sys	0m0.016s

Would you mind compiling the pichart program downloadable from a link on the first post of this thread and reporting the output (both OpenMP and serial) running on the Pi 4B with the new 9.1 compiler?

[jahboater]

JamesH,

That's a pretty good improvement!

Well what do you think about this?
Compiling the same program with the same compiler on the Pi4 and the Odroid N2
The Pi is quicker by a good margin. Unscientific comparison of course, but hey!

Code: Select all

$ wc try.c
 12798  58246 347137 try.c

N2
$ time gcc -O3 -s try.c -funsigned-char -o /dev/null -lm -lreadline -lcurses

real	0m23.375s
user	0m22.852s
sys	0m0.484s

Pi4
$ time gcc -O3 -s try.c -funsigned-char -o /dev/null -lm -lreadline -lcurses

real	0m14.931s
user	0m14.530s
sys	0m0.399s

[Heater]

What about the fibo speed on the Odroid N2 then?

[jahboater]

Would you mind compiling the pichart program downloadable from a link on the first post of this thread and reporting the output (both OpenMP and serial) running on the Pi 4B with the new 9.1 compiler?

Here it is (4GB version if it makes any difference).

Code: Select all

[email protected]:~/pichart-30 $ ./pichart-openmp 
pichart -- Raspberry Pi Performance OPENMP version 30

Prime Sieve          P=14630843 Workers=4 Sec=0.514499 Mops=1815.99
Merge Sort           N=16777216 Workers=8 Sec=1.07414 Mops=374.861
Fourier Transform    N=4194304 Workers=8 Sec=1.77694 Mflops=259.645
Lorenz 96            N=32768 K=16384 Workers=4 Sec=0.598412 Mflops=5382.96

My Computer has Raspberry Pi ratio=27.7325
Making pie charts...done.
[email protected]:~/pichart-30 $ ./pichart-serial 
pichart -- Raspberry Pi Performance Serial version 30

Prime Sieve          P=14630843 Workers=2 Sec=2.0762 Mops=450.018
Merge Sort           N=16777216 Workers=2 Sec=3.94588 Mops=102.044
Fourier Transform    N=4194304 Workers=2 Sec=2.95565 Mflops=156.099
Lorenz 96            N=32768 K=16384 Workers=1 Sec=2.1619 Mflops=1490

My Computer has Raspberry Pi ratio=9.027
Making pie charts...done.
[email protected]:~/pichart-30 $ 
[email protected]:~/pichart-30 $ gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/local/libexec/gcc/arm-linux-gnueabihf/9.1.0/lto-wrapper
Target: arm-linux-gnueabihf
Configured with: ../configure --enable-languages=c,d,c++,fortran --with-cpu=cortex-a72 --with-fpu=neon-fp-armv8 --with-float=hard --build=arm-linux-gnueabihf --host=arm-linux-gnueabihf --target=arm-linux-gnueabihf
Thread model: posix
gcc version 9.1.0 (GCC) 
[email protected]:~/pichart-30 $ 

[jahboater]

What about the fibo speed on the Odroid N2 then?

Code: Select all

$ gcc -O3 -s fibo.c -o fibo
$ time ./fibo | head -c 32; time ./fibo | tail -c 32
10727395641800477229364813596225
real	0m5.588s
user	0m5.488s
sys	0m0.100s
4856539211500699706378405156269

real	0m5.257s
user	0m5.208s
sys	0m0.052s 

OK it beats the Pi4, but then it costs a lot more.

[Heater]

Are they both using a 32 bit OS?

[jahboater]

Are they both using a 32 bit OS?

No, the N2 is 64-bit Ubuntu (the official OS).

[Heater]

There we go then. 64 bits will surely be it's advantage there.

[bensimmo]

Using the two Python3 example (edited to remove timit or the args)
and well on my PC I remember it just printing the full solution out no problem on 3.5/3.7

On the Pi4-4GB which is now 3.7.3 it just seems to 'hang'.

I'll try your head & tail thing.

or maybe there was another version I used ?

ok the first finished but with a Broken Pipe error.
So just going to let it run. It's under 3 mins, using all the 1st core and RSS 9.2MB under task manager

I'm at the desktop and a bit of browsing, typing on here etc doesn't seem to bother the calculation timing over various runs
Only have 1000 lines to scroll back to sorry and apparently 157000 odd character is past the posting limit

Code: Select all

...0927898489890806067034196931622252893057035920930130552038239931974615715617623206204585291487968755147324883784916338945806361951766313865956891695455563801462249978567353436540666740580717167763216988216644330074030719891463180149736853685001275152076875379936330930391815964864885353407167474856539211500699706378405156269

real	2m51.166s
user 	2m50.784s
sys	0m0.051s

[Heater]

Ah yes, Python and other language interpreters throw a broken pipe exception when head closes the input pipe.

Try redirecting the error messages.Something like (on my PC):

Code: Select all

$ time python3 fibo.py 2> /dev/null | head -c 32 ; time python3 fibo.py | tail -c 100
10727395641800477229364813596225
real    0m18.692s
user    0m18.531s
sys     0m0.047s
379936330930391815964864885353407167474856539211500699706378405156269
Run time = 0.7916809999733232

real    0m18.880s
user    0m18.516s
sys     0m0.125s

[bensimmo]

It has no problem just printing everything to the terminal window as above.


fibo_phy on the other hand was still doing something on teh one core at 14-16MB after I terminated it at over 11mins
I removed all the command line arguments, as other just set the variable inside.

back to fibo.py with the print part removed

Code: Select all

[email protected]:~ $ time python3 fibo.py

real	0m3.971s
user	0m3.940s
sys	0m0.030s
[email protected]:~ $ time python3 fibo.py

real	0m3.965s
user	0m3.891s
sys	0m0.072s
[email protected]:~ $ time python3 fibo.py

real	0m3.946s
user	0m3.874s
sys	0m0.072s
[email protected]:~ $ time python3 fibo.py

real	0m3.953s
user	0m3.909s
sys	0m0.031s
[email protected]:~ $ time python3 fibo.py

real	0m3.964s
user	0m3.891s
sys	0m0.071s
[email protected]:~ $ 

so 2m50s - 4s is the printing of it.

(for the record Python2.7.whatever is about 4.5 second give or take fluctuations
2mins 53s total for calculating and printing the lot to the terminal)

[ejolson]

Would you mind compiling the pichart program downloadable from a link on the first post of this thread and reporting the output (both OpenMP and serial) running on the Pi 4B with the new 9.1 compiler?

Here it is (4GB version if it makes any difference).

Code: Select all

[email protected]:~/pichart-30 $ ./pichart-openmp 
pichart -- Raspberry Pi Performance OPENMP version 30

Prime Sieve          P=14630843 Workers=4 Sec=0.514499 Mops=1815.99
Merge Sort           N=16777216 Workers=8 Sec=1.07414 Mops=374.861
Fourier Transform    N=4194304 Workers=8 Sec=1.77694 Mflops=259.645
Lorenz 96            N=32768 K=16384 Workers=4 Sec=0.598412 Mflops=5382.96

My Computer has Raspberry Pi ratio=27.7325
Making pie charts...done.
[email protected]:~/pichart-30 $ ./pichart-serial 
pichart -- Raspberry Pi Performance Serial version 30

Prime Sieve          P=14630843 Workers=2 Sec=2.0762 Mops=450.018
Merge Sort           N=16777216 Workers=2 Sec=3.94588 Mops=102.044
Fourier Transform    N=4194304 Workers=2 Sec=2.95565 Mflops=156.099
Lorenz 96            N=32768 K=16384 Workers=1 Sec=2.1619 Mflops=1490

My Computer has Raspberry Pi ratio=9.027
Making pie charts...done.
[email protected]:~/pichart-30 $ 
[email protected]:~/pichart-30 $ gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/local/libexec/gcc/arm-linux-gnueabihf/9.1.0/lto-wrapper
Target: arm-linux-gnueabihf
Configured with: ../configure --enable-languages=c,d,c++,fortran --with-cpu=cortex-a72 --with-fpu=neon-fp-armv8 --with-float=hard --build=arm-linux-gnueabihf --host=arm-linux-gnueabihf --target=arm-linux-gnueabihf
Thread model: posix
gcc version 9.1.0 (GCC) 
[email protected]:~/pichart-30 $ 

I've included your results in an ongoing discussion of the surprising speed of merge sort on the Pi 4B here on the Pi Pie Chart thread.

[gkreidl]

It has no problem just printing everything to the terminal window as above.


fibo_phy on the other hand was still doing something on teh one core at 14-16MB after I terminated it at over 11mins
I removed all the command line arguments, as other just set the variable inside.

back to fibo.py with the print part removed

Code: Select all

[email protected]:~ $ time python3 fibo.py

real	0m3.971s
user	0m3.940s
sys	0m0.030s
[email protected]:~ $ time python3 fibo.py

real	0m3.965s
user	0m3.891s
sys	0m0.072s
[email protected]:~ $ time python3 fibo.py

real	0m3.946s
user	0m3.874s
sys	0m0.072s
[email protected]:~ $ time python3 fibo.py

real	0m3.953s
user	0m3.909s
sys	0m0.031s
[email protected]:~ $ time python3 fibo.py

real	0m3.964s
user	0m3.891s
sys	0m0.071s
[email protected]:~ $ 

so 2m50s - 4s is the printing of it.

That looks like a great improvement for the algorithm and a small improvement for the string conversion (needed for printing). Using the same algorithm on a RPi B+ I get:

Code: Select all

./fibo_rd.py -t -i
Fibonacci(4784969) calculation took 10.678572177886963 seconds
String conversion took 306.680104970932 seconds
Fibonacci number has 1000000 digits

Compare this with the same algorithm using gmpy2 (a Python wrapper for GMP).

Code: Select all

./fibo_rd.py -t
Fibonacci(4784969) calculation took 0.42725133895874023 seconds
String conversion took 1.3055329322814941 seconds
Fibonacci number has 1000000 digits