 John_Spikowski
 Posts: 1614
 Joined: Wed Apr 03, 2019 5:53 pm
 Location: Anacortes, WA USA
 Contact: Website Twitter
Re: A Final Fibonacci Challenge
The answer may be looking at the GMP extension module for Python.
Re: A Final Fibonacci Challenge
ScriptBasic,
Sometimes I wonder if you ever read what I write for you. In the bug report on the ScriptBasic page here: https://www.raspberrypi.org/forums/view ... 5#p1483988 I presented fibo_strings.c which uses GMP from C via an interface that passes only decimal strings (as required for the GMP extension). It runs the fibo in a loop forever and does not leak memory. Verified by using valgrind and also by simply running it for a long time. Please do try it out for yourself.
As I said before you only need to ensure that ScriptBasic and it's GMP extension perform all the same clears and frees as that example C code. Then it will not leak. Where are those strings returned by the GMP extension functions finally get freed?
Out of curiousity.... The GMP extension makes heavy use of weird macros to interface with ScriptBasic. How would one see what the extensions C source looks likes after those macros have been expanded by the preprocessor. There may be some clues in looking at the actual C code we are compiling.
If it is then your understanding is wrong. Where would you get that idea from? I know of no languages that use GMP that have memory leaks apart from ScriptBaisc and it's GMP extension.Is it my understanding all fibos using GMP leak?
Sometimes I wonder if you ever read what I write for you. In the bug report on the ScriptBasic page here: https://www.raspberrypi.org/forums/view ... 5#p1483988 I presented fibo_strings.c which uses GMP from C via an interface that passes only decimal strings (as required for the GMP extension). It runs the fibo in a loop forever and does not leak memory. Verified by using valgrind and also by simply running it for a long time. Please do try it out for yourself.
As I said before you only need to ensure that ScriptBasic and it's GMP extension perform all the same clears and frees as that example C code. Then it will not leak. Where are those strings returned by the GMP extension functions finally get freed?
I doubt it. It's probably done very differently in Python. For example simply maintaining big numbers as normal GMP objects rather than endlessly converting to and from strings which is very inefficient.The answer may be looking at the GMP extension module for Python.
Out of curiousity.... The GMP extension makes heavy use of weird macros to interface with ScriptBasic. How would one see what the extensions C source looks likes after those macros have been expanded by the preprocessor. There may be some clues in looking at the actual C code we are compiling.
Memory in C++ is a leaky abstraction .
 John_Spikowski
 Posts: 1614
 Joined: Wed Apr 03, 2019 5:53 pm
 Location: Anacortes, WA USA
 Contact: Website Twitter
Re: A Final Fibonacci Challenge
Heater wrote: If it is then your understanding is wrong. Where would you get that idea from? I know of no languages that use GMP that have memory leaks apart from ScriptBaisc and it's GMP extension.
Dr. Jekyll / Hyde,Heater wrote: As it turns out I'm having the same issue with using my big integer functions in C++ from Javascript. Works fine but does not seem to clean up memory.
You said your JavaScript GMP fibo leaked. This isn't a ScriptBasic issue only. Stop trashing SB for your enjoyment.
When someone figures it out, let me know.
Re: A Final Fibonacci Challenge
ScriptBasic,
That is my Bint C++ class, compiled to Javascript or web assembly (WASM) with Emscripten and run in the browser or under node.js. A bug none the less, I'll track it down eventually.
No, I did not. I said I have a memory problem with my home made big integer class in Javascript. I don't have anything that uses GMP from Javascript.You said your JavaScript GMP fibo leaked.
That is my Bint C++ class, compiled to Javascript or web assembly (WASM) with Emscripten and run in the browser or under node.js. A bug none the less, I'll track it down eventually.
Yes it is. What else could a problem in ScriptBasic's use of the GMP library be?This isn't a ScriptBasic issue only.
Since when is reporting bugs considered "trashing"?Stop trashing SB for your enjoyment.
Memory in C++ is a leaky abstraction .
 John_Spikowski
 Posts: 1614
 Joined: Wed Apr 03, 2019 5:53 pm
 Location: Anacortes, WA USA
 Contact: Website Twitter
Re: A Final Fibonacci Challenge
The problem is on the table if anyone has time to solve it. Being a Fibonacci BASIC isn't ScriptBasic's main goal.
My testing has shown ScriptBasic leaks no memory until GMP is used. This is an interface issue and not a reason to call ScriptBasic or GMP buggy.
My testing has shown ScriptBasic leaks no memory until GMP is used. This is an interface issue and not a reason to call ScriptBasic or GMP buggy.
Re: A Final Fibonacci Challenge
Yes it's an interface issue.
An issue in an internal interface between core ScriptBasic and what is intended to be a standard ScriptBasic extension for big number arithmetic.
An issue with code in the ScriptBasic development source code repository.
What would you like me to refer to this issue as?
It's certainly not a reason to call GMP "buggy", not that any one has.
An issue in an internal interface between core ScriptBasic and what is intended to be a standard ScriptBasic extension for big number arithmetic.
An issue with code in the ScriptBasic development source code repository.
What would you like me to refer to this issue as?
It's certainly not a reason to call GMP "buggy", not that any one has.
Memory in C++ is a leaky abstraction .
 John_Spikowski
 Posts: 1614
 Joined: Wed Apr 03, 2019 5:53 pm
 Location: Anacortes, WA USA
 Contact: Website Twitter
Re: A Final Fibonacci Challenge
Heater,
I ran extensive tests to make sure ScriptBasic wasn't leaking calling extension modules and recursive routines. I only saw unexplained memory use when GMP was introduced. That is the problem that needs to be worked out by the SB community.
I posted an issue for this in the sandbox so it's noted.
I ran extensive tests to make sure ScriptBasic wasn't leaking calling extension modules and recursive routines. I only saw unexplained memory use when GMP was introduced. That is the problem that needs to be worked out by the SB community.
I posted an issue for this in the sandbox so it's noted.
 John_Spikowski
 Posts: 1614
 Joined: Wed Apr 03, 2019 5:53 pm
 Location: Anacortes, WA USA
 Contact: Website Twitter
Re: A Final Fibonacci Challenge
Here is a couple fibo functions from the Python gmpy extension module C code.
Code: Select all
PyDoc_STRVAR(doc_fib,
"fib(n) > mpz\n\n"
"Return the nth Fibonacci number.");
static PyObject *
Pygmpy_fib(PyObject *self, PyObject *other)
{
PympzObject *result;
mpir_si n;
n = SI_From_Integer(other);
if ((n == 1) && PyErr_Occurred()) {
TYPE_ERROR("fib() requires 'int' argument");
return NULL;
}
else if (n < 0) {
VALUE_ERROR("Fibonacci of negative number");
return NULL;
}
else {
if (!(result = (PympzObject*)Pympz_new()))
return NULL;
mpz_fib_ui(Pympz_AS_MPZ(result), n);
}
return (PyObject*)result;
}
PyDoc_STRVAR(doc_fib2,
"fib2(n) > tuple\n\n"
"Return a 2tuple with the (n1)th and nth Fibonacci numbers.");
static PyObject *
Pygmpy_fib2(PyObject *self, PyObject *other)
{
PyObject *result;
PympzObject *fib1 = 0, *fib2 = 0;
mpir_si n;
n = SI_From_Integer(other);
if ((n == 1) && PyErr_Occurred()) {
TYPE_ERROR("fib2() requires 'int' argument");
return NULL;
}
else if (n < 0) {
VALUE_ERROR("Fibonacci of negative number");
return NULL;
}
else {
CREATE_TWO_MPZ_TUPLE(fib1, fib2, result);
mpz_fib2_ui(fib1>z, fib2>z, n);
}
PyTuple_SET_ITEM(result, 0, (PyObject*)fib1);
PyTuple_SET_ITEM(result, 1, (PyObject*)fib2);
return result;
}
Speeding up the fast doubling algorithm
I implemented the fast doubling algorithm in Python as shown below.
Theoretically it should be faster than the recursive doubling with memoization which has been the fastest so far but it runs definitely slower.
The main reason is, that it calculates one more (large) Fibonacci number than we really need. To get fibo(4784969) it also calculates fibo(4784970), which is costly. This can be easily avoided as shown below.
This version is a bit faster than the recursive doubling version for many numbers and at least not slower for others. And it also uses less memory. It should be easily adaptable to any other programming language.
The attachment contains four complete Python scripts, which work the same way but use different algorithms. They use GMP, if gmpy2 is installed, but this can be prevented with the i option (use internal Python BIGINTs). It can print any Fibonacci number (default is fibo(4784969)), but can also be used to measure the timing of the algorithm and the string conversion (needed for printing). For a full list of options run "./programname h". All programs can be used with Python 2, Python 3 and pypy (no GMP support). Default is Python 3.
fibo_rd.py
This uses recursive doubling with memoization similar to the github version. It is surely the most elegant algorithm, but may use more memory than other implementations (memoization in global dictionary fibs).
fibo_rdr.py
This means "recursive doubling reversed". The algorithm is the same but it avoids any recursion. The required indexes are calculated first and then the Fibonacci numbers are calculated from bottom up (reversed). The fibs dictionary is now a local variable, which will be released, when the function returns. Memory overhead by memoization is avoided, because fibonacci numbers which are not needed any more are deleted in the dictionary.
fibo_fd.py
Standard fast doubling algorithm as shown above.
fibo_fdi.py
Faster (improved) fast doubling algorithm as shown above.
Timing examples (running on a RPi 3B+).
Using GMP BIGINTs:
Using Python's internal BIGINTs:
Code: Select all
def fibo(n):
if n <= 0:
return 0
if use_gmp:
a = mpz(0)
b = mpz(1)
else:
a = 0
b = 1
numbits = int(math.log(n,2))
for i in range(numbits,1,1):
d = a*(b*2a)
e = a*a+b*b
if (n >> i) & 1:
a = e
b = d + e
else:
a = d
b = e
return a
The main reason is, that it calculates one more (large) Fibonacci number than we really need. To get fibo(4784969) it also calculates fibo(4784970), which is costly. This can be easily avoided as shown below.
Code: Select all
def fibo(n):
if n <= 0:
return 0
if use_gmp:
a = mpz(0)
b = mpz(1)
else:
a = 0
b = 1
numbits = int(math.log(n,2))
for i in range(numbits,1,1):
if i > 0:
d = a*(b*2a)
e = a*a+b*b
if (n >> i) & 1:
a = e
b = d + e
else:
a = d
b = e
else:
if n & 1:
d = a*a+b*b
else:
d = a*(b*2a)
return d
The attachment contains four complete Python scripts, which work the same way but use different algorithms. They use GMP, if gmpy2 is installed, but this can be prevented with the i option (use internal Python BIGINTs). It can print any Fibonacci number (default is fibo(4784969)), but can also be used to measure the timing of the algorithm and the string conversion (needed for printing). For a full list of options run "./programname h". All programs can be used with Python 2, Python 3 and pypy (no GMP support). Default is Python 3.
fibo_rd.py
This uses recursive doubling with memoization similar to the github version. It is surely the most elegant algorithm, but may use more memory than other implementations (memoization in global dictionary fibs).
fibo_rdr.py
This means "recursive doubling reversed". The algorithm is the same but it avoids any recursion. The required indexes are calculated first and then the Fibonacci numbers are calculated from bottom up (reversed). The fibs dictionary is now a local variable, which will be released, when the function returns. Memory overhead by memoization is avoided, because fibonacci numbers which are not needed any more are deleted in the dictionary.
fibo_fd.py
Standard fast doubling algorithm as shown above.
fibo_fdi.py
Faster (improved) fast doubling algorithm as shown above.
Timing examples (running on a RPi 3B+).
Using GMP BIGINTs:
Code: Select all
pi@raspberrypi4:~/fibochallenge $ ./fibo_rd.py t n
Fibonacci(4784969) calculation took 0.4217264652252197 seconds
pi@raspberrypi4:~/fibochallenge $ ./fibo_rdr.py t n
Fibonacci(4784969) calculation took 0.4217088222503662 seconds
pi@raspberrypi4:~/fibochallenge $ ./fibo_fd.py t n
Fibonacci(4784969) calculation took 0.5097312927246094 seconds
pi@raspberrypi4:~/fibochallenge $ ./fibo_fdi.py t n
Fibonacci(4784969) calculation took 0.3734128475189209 seconds
Code: Select all
pi@raspberrypi4:~/fibochallenge $ ./fibo_rd.py t n i
Fibonacci(4784969) calculation took 10.606588363647461 seconds
pi@raspberrypi4:~/fibochallenge $ ./fibo_rdr.py t n i
Fibonacci(4784969) calculation took 10.56157374382019 seconds
pi@raspberrypi4:~/fibochallenge $ ./fibo_fd.py t n i
Fibonacci(4784969) calculation took 13.833927631378174 seconds
pi@raspberrypi4:~/fibochallenge $ ./fibo_fdi.py t n i
Fibonacci(4784969) calculation took 9.754611492156982 seconds
 Attachments

 fibochallenge.tar.gz
 (1.82 KiB) Downloaded 73 times
Minimal Kiosk Browser (kweb)
Slim, fast webkit browser with support for audio+video+playlists+youtube+pdf+download
Optional fullscreen kiosk mode and command interface for embedded applications
Includes omxplayerGUI, an X front end for omxplayer
Slim, fast webkit browser with support for audio+video+playlists+youtube+pdf+download
Optional fullscreen kiosk mode and command interface for embedded applications
Includes omxplayerGUI, an X front end for omxplayer
Re: A Final Fibonacci Challenge
Can we run all these again on a Pi4? whoops been asked
I'm dancing on Rainbows.
Raspberries are not Apples or Oranges
Raspberries are not Apples or Oranges
Re: Speeding up the fast doubling algorithm
That's a nice roundup of Python codes. I'll run them through fibench on the supercheap cluster to see what happens. With all the Pi 4B excitement, it seems the updated JavaScript codes are somewhat delayed. Fortunately, the Pi Zero is still state of the art for a computer that comes free with a magazine subscription. I wonder if there will ever be a replacement with a singlecore CortexA53, smaller process size and less requirements for electricity.
Re: A Final Fibonacci Challenge
It would be interesting to see which of those handcoded bignumber multiplication algorithms run faster (or slower) on the new hardware. Given these preliminary results for the merge sort (perhaps due only to different compiler optimization settings), I'm not sure what to expect.
Re: A Final Fibonacci Challenge
ejolson,
Not just Pi 4 excitement.
Sometimes I remember that I'm supposed to be writing software for a living.... Today I'm going to blow the socks off people by demoing a solution that makes use of my new found Javascript plus C++ compiled to WASM skills. Something I learned in the course of this very challenge!
Imagine there is a server side process in node JS that does a lot of typical server things, wrangling with SQL databases, dealing with web sockets and so on. Node is a great solution there, quick and easy to develop and as most of the work is done by the OS or native compiled modules performance is excellent.
Now imagine a new requirement for that process that involves a lot of dirty bit twiddling and byte munging to extract data from some weird binary protocol. Node and JS is a disaster for that, horribly slow.
One could write that dirty code in C/C++ as a node.js module. That is complicated. And shitty to maintain.
One could run the C/C++ code in a separate process and use IPC between it and the node.js, that is complicated and has performance implications.
Or one could learn from the Fibo challenge. Just compile the C/C++ to WASM with Emscripten and call it from Javascript. Boom job done, performance is a couple of times slower than native compilation and the additional interfacing. But an order of magnitude faster than doing it in JS. Maintenance and testing is a breeze.
Of course, I had to write all that C++ first ....
Sorry for rambling. I'm kind of proud of this creation. I'll get back to Fibo JS as soon as possible... Looks like I have to checkout gkreidl's new approaches as well.
Ah, sorry about that.With all the Pi 4B excitement, it seems the updated JavaScript codes are somewhat delayed.
Not just Pi 4 excitement.
Sometimes I remember that I'm supposed to be writing software for a living.... Today I'm going to blow the socks off people by demoing a solution that makes use of my new found Javascript plus C++ compiled to WASM skills. Something I learned in the course of this very challenge!
Imagine there is a server side process in node JS that does a lot of typical server things, wrangling with SQL databases, dealing with web sockets and so on. Node is a great solution there, quick and easy to develop and as most of the work is done by the OS or native compiled modules performance is excellent.
Now imagine a new requirement for that process that involves a lot of dirty bit twiddling and byte munging to extract data from some weird binary protocol. Node and JS is a disaster for that, horribly slow.
One could write that dirty code in C/C++ as a node.js module. That is complicated. And shitty to maintain.
One could run the C/C++ code in a separate process and use IPC between it and the node.js, that is complicated and has performance implications.
Or one could learn from the Fibo challenge. Just compile the C/C++ to WASM with Emscripten and call it from Javascript. Boom job done, performance is a couple of times slower than native compilation and the additional interfacing. But an order of magnitude faster than doing it in JS. Maintenance and testing is a breeze.
Of course, I had to write all that C++ first ....
Sorry for rambling. I'm kind of proud of this creation. I'll get back to Fibo JS as soon as possible... Looks like I have to checkout gkreidl's new approaches as well.
Memory in C++ is a leaky abstraction .
Re: Speeding up the fast doubling algorithm
Nice one!gkreidl wrote: ↑Wed Jun 26, 2019 7:37 amThe main reason is, that it calculates one more (large) Fibonacci number than we really need. To get fibo(4784969) it also calculates fibo(4784970), which is costly. This can be easily avoided as shown below.
This version is a bit faster than the recursive doubling version for many numbers and at least not slower for others. And it also uses less memory. It should be easily adaptable to any other programming language.Code: Select all
def fibo(n): if n <= 0: return 0 if use_gmp: a = mpz(0) b = mpz(1) else: a = 0 b = 1 numbits = int(math.log(n,2)) for i in range(numbits,1,1): if i > 0: d = a*(b*2a) e = a*a+b*b if (n >> i) & 1: a = e b = d + e else: a = d b = e else: if n & 1: d = a*a+b*b else: d = a*(b*2a) return d
I adapted this for 8th programming language. I also took some comparisons out from the fibo loop (handle zero bit outside the loop):
Code: Select all
\
\ Fibonacci with million digits
\
: bits? \ n  nbits1
n:ln 2 n:ln n:/ n:int ;
: fiboloop
>r \ Put loop counter on rstack
\ a b
2dup 2 n:* \ a b a 2b
over n: \ a b a (2ba)
n:* rot \ d=(2ba)*a a b
n:sqr swap n:sqr n:+ \ d=(2ba)*a e=b*b+a*a
r> r@ swap n:shr 1 n:band if
dup \ a b b
rot \ b b a
n:+ \ b c=b+a
then ;
: fibo \ n  fibo(n)
>r \ Put n on rstack
F0 F1 \ a b
' fiboloop 1 r@ bits? loop
\ a b
r> 1 n:band if
n:sqr swap n:sqr n:+ \ b*b+a*a
else
2 n:* over n: n:* \ (2ba)*a
then ;
: app:main
d:msec >r
4784969 fibo
"%.f" strfmt \ Convert result to just an 'int' string.
d:msec r> n: >r
s:len . " digits:" . cr
. cr
r> . " msec" . cr
bye ;
Re: A Final Fibonacci Challenge
Here is my old Basic version adapted to use gkreidl's approach. You need to change just a few lines for the JavaScript conversion you did from my old Basic source. Just remember to change all uint's to BIGINT's. Let me know how it performs vs your recursive fibo.
Code: Select all
func log2(double n), double
return log(n)/log(2)
endf
func fibo(int n),uint
uint a = 0
uint b = 1
int numbits = int(log2(n))
for i = numbits to 1 step 1
uint d = a*(b*2a)
uint e = a*a+b*b
a = d
b = e
if (n >> i) & 1
uint c = a+b
a = b
b = c
endif
next i
if n & 1
a = a*a + b*b
else
a = a*(b*2a)
endif
return a
endf
Re: A Final Fibonacci Challenge
Taking out the check for 0 is a good idea. My Python function now looks like this:
Code: Select all
def fibo(n):
if n <= 0:
return 0
if use_gmp:
a = mpz(0)
b = mpz(1)
else:
a = 0
b = 1
numbits = int(math.log(n,2))
for i in range(numbits,0,1):
d = a*(b*2a)
e = a*a+b*b
if (n >> i) & 1:
a = e
b = d + e
else:
a = d
b = e
if n & 1:
return a*a+b*b
else:
return a*(b*2a)
Minimal Kiosk Browser (kweb)
Slim, fast webkit browser with support for audio+video+playlists+youtube+pdf+download
Optional fullscreen kiosk mode and command interface for embedded applications
Includes omxplayerGUI, an X front end for omxplayer
Slim, fast webkit browser with support for audio+video+playlists+youtube+pdf+download
Optional fullscreen kiosk mode and command interface for embedded applications
Includes omxplayerGUI, an X front end for omxplayer
 John_Spikowski
 Posts: 1614
 Joined: Wed Apr 03, 2019 5:53 pm
 Location: Anacortes, WA USA
 Contact: Website Twitter
Re: A Final Fibonacci Challenge
I'm amazed how much faster GMP is vs. native Python BIGINT. Can't wait until the ScriptBasic issues with GMP are worked out.
Re: A Final Fibonacci Challenge
Hey, I finally tracked down and fixed up the memory leak in my inbrowser big Fibonacci number calculator. It's working a treat.
https://otaniemi.conveqs.fi:3000/public/fibo.html
I tested it to fibo(10,000,000). After that it may fail as n goes out of the JS number range or it eats all your memory. I have no checks in place for either.
Surprisingly it is quicker to calculate fibo(5000000) than fibo(4784969). By about 30%. Which is a lot. Go figure.
https://otaniemi.conveqs.fi:3000/public/fibo.html
I tested it to fibo(10,000,000). After that it may fail as n goes out of the JS number range or it eats all your memory. I have no checks in place for either.
Surprisingly it is quicker to calculate fibo(5000000) than fibo(4784969). By about 30%. Which is a lot. Go figure.
Memory in C++ is a leaky abstraction .
 John_Spikowski
 Posts: 1614
 Joined: Wed Apr 03, 2019 5:53 pm
 Location: Anacortes, WA USA
 Contact: Website Twitter
Re: A Final Fibonacci Challenge
Congrats!
Maybe you can help me figured out why GMP leaks when used with the ScriptBasic extension module.
Maybe you can help me figured out why GMP leaks when used with the ScriptBasic extension module.
Re: A Final Fibonacci Challenge
fibo(5000000) has 1735013 set bits
fibo(4784969) has 1660411 set bits
using the GMP function mpz_popcount()
Last edited by jahboater on Fri Jul 05, 2019 6:43 am, edited 1 time in total.
Re: A Final Fibonacci Challenge
Nonsense.
5000000 = 0b010011000100101101000000
4784969 = 0b010010010000001101001001
Minimal Kiosk Browser (kweb)
Slim, fast webkit browser with support for audio+video+playlists+youtube+pdf+download
Optional fullscreen kiosk mode and command interface for embedded applications
Includes omxplayerGUI, an X front end for omxplayer
Slim, fast webkit browser with support for audio+video+playlists+youtube+pdf+download
Optional fullscreen kiosk mode and command interface for embedded applications
Includes omxplayerGUI, an X front end for omxplayer
Re: A Final Fibonacci Challenge
Re: A Final Fibonacci Challenge
Yes, but that was not the question.
Having more "1"s in the lowest bits is important.
Code: Select all
pi@raspberrypi4:~/fibochallenge $ ./fibo_rd.py t n 4194320
Fibonacci(4194320) calculation took 0.2915217876434326 seconds
pi@raspberrypi4:~/fibochallenge $ ./fibo_rd.py t n 4194319
Fibonacci(4194319) calculation took 0.3306257724761963 seconds
4194319 = 0x40000f
Minimal Kiosk Browser (kweb)
Slim, fast webkit browser with support for audio+video+playlists+youtube+pdf+download
Optional fullscreen kiosk mode and command interface for embedded applications
Includes omxplayerGUI, an X front end for omxplayer
Slim, fast webkit browser with support for audio+video+playlists+youtube+pdf+download
Optional fullscreen kiosk mode and command interface for embedded applications
Includes omxplayerGUI, an X front end for omxplayer
Re: A Final Fibonacci Challenge
Interesting.gkreidl wrote: ↑Fri Jul 05, 2019 6:56 amHaving more "1"s in the lowest bits is important.4194320 = 0x400010Code: Select all
pi@raspberrypi4:~/fibochallenge $ ./fibo_rd.py t n 4194320 Fibonacci(4194320) calculation took 0.2915217876434326 seconds pi@raspberrypi4:~/fibochallenge $ ./fibo_rd.py t n 4194319 Fibonacci(4194319) calculation took 0.3306257724761963 seconds
4194319 = 0x40000f
But it may be implementation specific.
It doesn't make any difference to the execution time of mpz_fib_ui() for the two numbers above.