### Re: A Final Fibonacci Challenge

Posted:

**Sat Jun 15, 2019 6:27 pm**This fibo challenge was equivalent to reaching the summit of Mount Everest. It's starting to get crowded up here.

A small, affordable computer with free resources to help people learn, make things, and have fun

https://lb.raspberrypi.org/forums/

https://lb.raspberrypi.org/forums/viewtopic.php?f=31&t=240287

Page **20** of **67**

Posted: **Sat Jun 15, 2019 6:27 pm**

This fibo challenge was equivalent to reaching the summit of Mount Everest. It's starting to get crowded up here.

Posted: **Sat Jun 15, 2019 6:35 pm**

How much faster is GMP over Python's native BIGINT?

Posted: **Sat Jun 15, 2019 8:06 pm**

Fibo function: 26 (Python 3) to 31 (Python 2) times faster. For small numbers the difference is smaller.

The string conversion needed for printing is 240 times faster.

The GMP fibo function is about 1.6 times faster than the Python function using GMP.

Posted: **Sat Jun 15, 2019 8:11 pm**

I'm surprised Python hasn't adapted GMP and deprecated their ancient BIGINT direction.,

Posted: **Sat Jun 15, 2019 8:40 pm**

To compare the speed of doing maths with big integers in Python and C we can look at the results of running ejolson's fibogmp.c and my fibo.py. Neither of these cheat by using any ready made fibo function, they just do regular maths operations on big ints.

**fibogmp.c**
**fibo.py**
Overall we see C+GMP is 20 times faster than Python here.

Looking at the actual calculation time we see C+GMP is 36 times faster than Python's big integers.

Python is spending most of it's over 16 of it's 17 seconds run time thinking about printing the result!

The code I'm running above can be found here: https://github.com/ZiCog/fibo_4784969

Code: Select all

```
$ time ./fibogmp | tail -c 100
GMP Doubling Percent
fibo 0.019891000 0.023732000 83.81510
print 0.114708000 0.115453000 99.35472
total 0.134599000 0.139185000 96.70510
180149736853685001275152076875379936330930391815964864885353407167474856539211500699706378405156269
real 0m0.881s
user 0m0.750s
sys 0m0.109s
$
```

Code: Select all

```
$ time python3 ../python/fibo.py | tail -c 100
379936330930391815964864885353407167474856539211500699706378405156269
Run time = 0.7061800000083167
real 0m17.490s
user 0m17.391s
sys 0m0.078s
$
```

Looking at the actual calculation time we see C+GMP is 36 times faster than Python's big integers.

Python is spending most of it's over 16 of it's 17 seconds run time thinking about printing the result!

The code I'm running above can be found here: https://github.com/ZiCog/fibo_4784969

Posted: **Sat Jun 15, 2019 8:45 pm**

The new **fiboair** GMP extension module version may be the fastest **fibo** function going. My next test will be on the RPi 3 B.

**afibo.sb**
**fibo.sb**

Code: Select all

```
besFUNCTION(fiboair)
int fval, count;
mpz_t a, b, p, q, psq, qsq, twopq, bq, aq, ap, bp;
besARGUMENTS("i")
&fval
besARGEND
count = fval;
mpz_init_set_si(a, 1);
mpz_init_set_si(b, 0);
mpz_init_set_si(p, 0);
mpz_init_set_si(q, 1);
mpz_init(psq);
mpz_init(qsq);
mpz_init(twopq);
mpz_init(bq);
mpz_init(aq);
mpz_init(ap);
mpz_init(bp);
while(count > 0) {
if ((count % 2) == 0) {
mpz_mul(psq, p, p);
mpz_mul(qsq, q, q);
mpz_mul(twopq, p, q);
mpz_mul_si(twopq, twopq, 2);
mpz_add(p, psq, qsq);
mpz_add(q, twopq, qsq);
count/=2;
}else{
mpz_mul(bq, b, q);
mpz_mul(aq, a, q);
mpz_mul(ap, a, p);
mpz_mul(bp, b, p);
mpz_add(a, bq, aq);
mpz_add(a, a, ap);
mpz_add(b, bp, aq);
count--;
}
}
char* res_string = mpz_get_str (0, 10, b);
besSET_RETURN_STRING(res_string);
free(res_string);
besEND
```

Code: Select all

```
DECLARE SUB Fibo_AIR ALIAS "fiboair" LIB "gmp"
PRINT Fibo_AIR(4784969)
jrs@jrs-laptop:~/sb/GMP$ time scriba afibo.sb > fibout
real 0m0.366s
user 0m0.353s
sys 0m0.012s
jrs@jrs-laptop:~/sb/GMP$ ls -l fibout
-rw-r--r-- 1 jrs jrs 1000000 Jun 15 13:37 fibout
jrs@jrs-laptop:~/sb/GMP$ tail -c64 fibout
6330930391815964864885353407167474856539211500699706378405156269
jrs@jrs-laptop:~/sb/GMP$
```

Code: Select all

```
DECLARE SUB fibo ALIAS "fibofunc" LIB "gmp"
PRINT fibo(4784969)
jrs@jrs-laptop:~/sb/GMP$ time scriba fibo.sb > fibofunc
real 0m0.258s
user 0m0.254s
sys 0m0.004s
jrs@jrs-laptop:~/sb/GMP$ ls -l fibofunc
-rw-r--r-- 1 jrs jrs 1000000 Jun 15 13:38 fibofunc
jrs@jrs-laptop:~/sb/GMP$ tail -c64 fibofunc
6330930391815964864885353407167474856539211500699706378405156269
jrs@jrs-laptop:~/sb/GMP$
```

Posted: **Sat Jun 15, 2019 8:56 pm**

ejolson,

All this talk of real world rabbits made me think that the schoolboy fibo algorithm is too abstract and theoretical. All that addition and stuff. No, what we need, in the spirit of modern scientific method of Physics and Cosmology, is a simulation.

So I wrote a Finonacci rabbit simulator. Rather than pairs of rabbits it works with hermaphrodite rabbits for simplicity. One rabbit gets put into the an empty field at time zero then every month we see what happens:
Conclusively proving that after one year we have 144 rabbits in the field. Without having to do any of that tricky maths stuff.

As we see, initially we have zero rabbits.

Sadly my field overflows at month 36 and only 2.5 million rabbits.

All this talk of real world rabbits made me think that the schoolboy fibo algorithm is too abstract and theoretical. All that addition and stuff. No, what we need, in the spirit of modern scientific method of Physics and Cosmology, is a simulation.

So I wrote a Finonacci rabbit simulator. Rather than pairs of rabbits it works with hermaphrodite rabbits for simplicity. One rabbit gets put into the an empty field at time zero then every month we see what happens:

Code: Select all

```
let field = []
let month = 0
let millisecondsPerMonth = 100
class Rabbit {
constructor (location) {
this.location = field
this.age = 0
}
ageByOneMonth () {
if (this.age > 0) {
this.spawn()
}
this.age++
}
spawn () {
let rabbit = new Rabbit(this.location)
this.location.push(rabbit)
}
}
function printField() {
console.log(`Month ${month} : Rabbits ${field.length}`)
}
function zerothMonth () {
field = []
printField()
let rabbit = new Rabbit(field)
field.push(rabbit)
month++
}
function nextMonth() {
printField()
field.map(rabbit => {
rabbit.ageByOneMonth()
});
month++
}
zerothMonth()
setInterval(function () {
nextMonth()
}, millisecondsPerMonth)
[code]
With results:
[code]
$ node rabbit-simulator.js
Month 0 : Rabbits 0
Month 1 : Rabbits 1
Month 2 : Rabbits 1
Month 3 : Rabbits 2
Month 4 : Rabbits 3
Month 5 : Rabbits 5
Month 6 : Rabbits 8
Month 7 : Rabbits 13
Month 8 : Rabbits 21
Month 9 : Rabbits 34
Month 10 : Rabbits 55
Month 11 : Rabbits 89
Month 12 : Rabbits 144
```

As we see, initially we have zero rabbits.

Sadly my field overflows at month 36 and only 2.5 million rabbits.

Posted: **Sat Jun 15, 2019 9:00 pm**

Why don't you mention the possible use of GMT BIGINTs in Python which is not much slower than your c code? And the time for string conversion is then 240 times faster. The Python code needs almost no change. Just importing gmpy2 and modifying the initial dictionary to use mpz (GMP ints) is enough.Heater wrote: βSat Jun 15, 2019 8:40 pmTo compare the speed of doing maths with big integers in Python and C we can look at the results of running ejolson's fibogmp.c and my fibo.py. Neither of these cheat by using any ready made fibo function, they just do regular maths operations on big ints.

fibogmp.cCode: Select all

`$ time ./fibogmp | tail -c 100 GMP Doubling Percent fibo 0.019891000 0.023732000 83.81510 print 0.114708000 0.115453000 99.35472 total 0.134599000 0.139185000 96.70510 180149736853685001275152076875379936330930391815964864885353407167474856539211500699706378405156269 real 0m0.881s user 0m0.750s sys 0m0.109s $`

fibo.pyOverall we see C+GMP is 20 times faster than Python here.Code: Select all

`$ time python3 ../python/fibo.py | tail -c 100 379936330930391815964864885353407167474856539211500699706378405156269 Run time = 0.7061800000083167 real 0m17.490s user 0m17.391s sys 0m0.078s $`

Looking at the actual calculation time we see C+GMP is 36 times faster than Python's big integers.

Python is spending most of it's over 16 of it's 17 seconds run time thinking about printing the result!

The code I'm running above can be found here: https://github.com/ZiCog/fibo_4784969

Posted: **Sat Jun 15, 2019 9:12 pm**

gkreidl,

Only because I don't have that version in my fibo(4784969) repository. It does not meet this criteria of the Fibonacci Challenge by virtue of using the GMP library.Why don't you mention the possible use of GMT BIGINTs in Python...

Posted: **Sat Jun 15, 2019 9:22 pm**

Are you saying that the ScriptBasic GMP extension module assisted submission fails to meet the criteria of the challenge?

Should ScriptBasic be banned from any further challenges due to it not using**malloc** as its memory manager by default?

When did this become the native BIGINT club members only challenge? Others are welcome to entertain us with there feeble attempts with emulation.

Should ScriptBasic be banned from any further challenges due to it not using

When did this become the native BIGINT club members only challenge? Others are welcome to entertain us with there feeble attempts with emulation.

Posted: **Sat Jun 15, 2019 9:40 pm**

Is this true?Stackless python just limits its use of the C stack. It will clear everything off the stack at the end of a function call. I was originally doing this on rcbasic v1.0. I changed it because it will produce some unintended results in recursive function calls.

For example, if you create a variable called MyVar with an initial value of 0. Then set MyVar equal to 5 before your recursive call. At the start of the call MyVar is equal to 5 instead of 0 since a new function call does not create a new instance of the variable.

Posted: **Sat Jun 15, 2019 10:03 pm**

ScriptBasic,

I posed the million digit Fibonacci number challenge to DavidS early in his thread "Why Avoid BASIC". David suggested the rule that libraries and modules non-strandard to the language be disallowed. The idea being to disallow "cheating" by just using something like the GMP fibo function or big intger libraries. I and other thread participants agreed. Sadly David did not follow through with a solution in BASIC or assembler as he said he might.

As for this thread, it belongs to ejolson, I assumed it was a continuation of the miliion digit Fibonnaci Challenge discussion. Perhaps it's not. It's up to him to say what he likes and does not like to see here.

As for ScriptBasic, when the big integer capability is built into the ScriptBasic installation, available out of the box, then your big fibo solution will fulfill the requirements of the original challenge. No problem.

We have had this discussion before.Are you saying that the ScriptBasic GMP extension module assisted submission fails to meet the criteria of the challenge?

I posed the million digit Fibonacci number challenge to DavidS early in his thread "Why Avoid BASIC". David suggested the rule that libraries and modules non-strandard to the language be disallowed. The idea being to disallow "cheating" by just using something like the GMP fibo function or big intger libraries. I and other thread participants agreed. Sadly David did not follow through with a solution in BASIC or assembler as he said he might.

Of course not. By the way, where does SciptBasic get it's memory from if it's not using malloc under the hood?Should ScriptBasic be banned from any further challenges due to it not using malloc as its memory manager by default?

I have also answered that question for you before. As I said before: The million digit Fibonacci challenge has never been "native BIGINT club members only". There are solutions in C, C++, Javascript, BASIC and whatever else that do not use any big integer types built into the language or contained in external libraries. People have done the big integer maths themselves. There are solutions in Python, Scheme, Scala etc that do use the languages big integer types, that's OK, that's part of the language itself.When did this become the native BIGINT club members only challenge?

I have no idea what that is supposed to mean. I have not seen any solutions that require emulators.Others are welcome to entertain us with there feeble attempts with emulation.

As for this thread, it belongs to ejolson, I assumed it was a continuation of the miliion digit Fibonnaci Challenge discussion. Perhaps it's not. It's up to him to say what he likes and does not like to see here.

As for ScriptBasic, when the big integer capability is built into the ScriptBasic installation, available out of the box, then your big fibo solution will fulfill the requirements of the original challenge. No problem.

Posted: **Sat Jun 15, 2019 10:11 pm**

Are you saying as long as the GMP extension module is part of the standard distribution for ScriptBasic I'm welcome to join the club?

Are you saying that if a client of yours had a need for BIGINT support, you would write it in native Python BIGINT even though it's 20X slower than GMP?

Are you saying that if a client of yours had a need for BIGINT support, you would write it in native Python BIGINT even though it's 20X slower than GMP?

Posted: **Sat Jun 15, 2019 10:23 pm**

This memory manager is standalone and used in other applications besides ScriptBasic.Heater wrote: By the way, where does SciptBasic get it's memory from if it's not using malloc under the hood?

Peter Verhas's MyAlloc

Posted: **Sat Jun 15, 2019 10:27 pm**

Yes of course. I have said that more than once here recently.

Originally I was reluctant because the big integer extension to ScriptBasic did not exist when the challenge was started. Indeed it has been created as a response to the challenge. As such it is a solution mostly not written in BASIC but C and using a non standard library to both ScriptBasic and C.

However, given the effort put into getting it working by yourself and others I have softened up on that. When one can install ScriptBasic and run that fibo solution out of the box then it seems a reasonable solution.

Originally I was reluctant because the big integer extension to ScriptBasic did not exist when the challenge was started. Indeed it has been created as a response to the challenge. As such it is a solution mostly not written in BASIC but C and using a non standard library to both ScriptBasic and C.

However, given the effort put into getting it working by yourself and others I have softened up on that. When one can install ScriptBasic and run that fibo solution out of the box then it seems a reasonable solution.

Posted: **Sat Jun 15, 2019 10:30 pm**

Thanks for softening up on your position and taking into consideration the effort that went into getting BIGINT support for ScriptBasic.

What other popular languages use GMP for BIGINT support?

What other popular languages use GMP for BIGINT support?

Posted: **Sat Jun 15, 2019 10:42 pm**

ScriptBasic,

Point is, it does not matter how they get their big integer types done. If big integer types are as much part of the language as int or char in C then it's an implementation detail the programmer does not need to think about.

I bet that MyAlloc is using malloc in there somewhere.

I have no idea. It would not surprise me if some did.What other popular languages use GMP for BIGINT support?

Point is, it does not matter how they get their big integer types done. If big integer types are as much part of the language as int or char in C then it's an implementation detail the programmer does not need to think about.

I bet that MyAlloc is using malloc in there somewhere.

Posted: **Sat Jun 15, 2019 10:45 pm**

I found this https://www.nayuki.io/page/fast-fibonacci-algorithms

Got it working with the supplied python3 program
And rewrote that in a naΓ―ve C program (using math.h / libm)
That fast doubling algorithm is incredibly fast compared to simple recursion. I didn't look at whether I could get to 128-bit integers with GMP (that's for another day).

Got it working with the supplied python3 program

Code: Select all

```
#!/usr/bin/python3
# (Public) Returns F(n).
def fibonacci(n):
if n < 0:
raise ValueError("Negative arguments not implemented")
return _fib(n)[0]
# (Private) Returns the tuple (F(n), F(n+1)).
def _fib(n):
if n == 0:
return (0, 1)
else:
q = n // 2
a, b = _fib(q)
c = a * (b * 2 - a)
d = a * a + b * b
if n % 2 == 0:
return (c, d)
else:
return (d, c + d)
print (fibonacci(88))
print (fibonacci(89))
print (fibonacci(90))
print (fibonacci(91))
print (fibonacci(92))
```

Code: Select all

```
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
unsigned long long * _fib(unsigned long long n)
{
unsigned long long *a;
unsigned long long q;
static unsigned long long b[2];
static unsigned long long c[2];
if (n == 0)
{
c[0] = 0;
c[1] = 1;
}
else
{
q = n / 2;
a = _fib(floor(q));
b[0] = a[0] * (a[1] * 2 - a[0]);
b[1] = a[0] * a[0] + a[1] * a[1];
if (n % 2 == 0)
{
c[0] = b[0];
c[1] = b[1];
}
else
{
c[0] = b[1];
c[1] = b[0] + b[1];
}
}
return c;
}
unsigned long long * fibonacci(unsigned long long n)
{
if (n < 0)
{
printf("Negative arguments not implemented\n");
exit(20);
}
return _fib(n);
}
int main(void)
{
unsigned long long *p;
p = fibonacci(88);
printf("%lld\n", p[0]);
p = fibonacci(89);
printf("%lld\n", p[0]);
p = fibonacci(90);
printf("%lld\n", p[0]);
p = fibonacci(91);
printf("%lld\n", p[0]);
p = fibonacci(92);
printf("%lld\n", p[0]);
return 0;
}
```

Posted: **Sat Jun 15, 2019 10:54 pm**

If you mean simple recursion as in the solutions that contain something like:

return fibo(n-2) + fibo(n-1)

that soon gets millions of times slower than the schoolboy iterative addition solutions as n gets bigger. That "tree" of recursions grows out of hand.

return fibo(n-2) + fibo(n-1)

that soon gets millions of times slower than the schoolboy iterative addition solutions as n gets bigger. That "tree" of recursions grows out of hand.

Posted: **Sat Jun 15, 2019 10:59 pm**

do an apt-cache search gmpScriptBasic wrote: βSat Jun 15, 2019 10:30 pmWhat other popular languages use GMP for BIGINT support?

Lots of noise, but I can see perl, ocam, php, ada, python (gmpy), gambas?, possibly free pascal,

and obviously C and C++, since GMP is written in C, for C.

Posted: **Sat Jun 15, 2019 11:02 pm**

I do mean that simplistic approach
That one is one way to get one core of your Raspberry running at 100% flat out for minutes/hours on end.

I reckon fib(92) is about the limit in a 64-bit long long integer. I found a really quick Javascript page at http://www.maths.surrey.ac.uk/hosted-si ... CalcX.html (which, probably, does more maths than EJolson was looking for).

Code: Select all

```
#include <stdio.h>
unsigned long long f(unsigned long long x)
{
if (x <= 1) return x;
return f(x-1) + f(x-2);
}
int main(void)
{
printf("%lld\n", f(92));
return 0;
}
```

I reckon fib(92) is about the limit in a 64-bit long long integer. I found a really quick Javascript page at http://www.maths.surrey.ac.uk/hosted-si ... CalcX.html (which, probably, does more maths than EJolson was looking for).

Posted: **Sat Jun 15, 2019 11:04 pm**

This is even simpler (and includes an overflow check),DougieLawson wrote: βSat Jun 15, 2019 11:02 pmI reckon fib(92) is about the limit in a 64-bit long long integer. I found a really quick Javascript page at http://www.maths.surrey.ac.uk/hosted-si ... CalcX.html (which, probably, does more maths than EJolson was looking for).

Code: Select all

```
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#define N 93
int
main( void )
{
int term = N - 1;
uint64_t n, a = 0, b = 1;
do
{
if( __builtin_add_overflow( a, b, &n ) )
{
puts("Overflow");
exit(1);
}
a = b;
b = n;
}
while( --term );
printf( "%" PRIu64 "\n", b );
}
```

Posted: **Sat Jun 15, 2019 11:11 pm**

GMP is arbitrary precision.DougieLawson wrote: βSat Jun 15, 2019 10:45 pmI didn't look at whether I could get to 128-bit integers with GMP (that's for another day).

You can, for example, compute the million digit fibo(4784969) simply with:

mpz_fib_ui( res, 4784969 );

which executes in 38 milliseconds on my 7 year old Intel PC.

Posted: **Sat Jun 15, 2019 11:29 pm**

That function was the birth of the ScriptBasic GMP extension module.jahboater wrote: βSat Jun 15, 2019 11:11 pmGMP is arbitrary precision.DougieLawson wrote: βSat Jun 15, 2019 10:45 pmI didn't look at whether I could get to 128-bit integers with GMP (that's for another day).

You can, for example, compute the million digit fibo(4784969) simply with:

mpz_fib_ui( res, 4784969 );

which executes in 38 milliseconds on my 7 year old Intel PC.

Posted: **Sat Jun 15, 2019 11:56 pm**

The Fastest BigInt In The West

The moral of the BIGINT story is GMP is the Genie in the bottle. You just need a heater to let it out.

**FACT:** GMP is needed to build the GNU Compiler Collection (**GCC**)

The moral of the BIGINT story is GMP is the Genie in the bottle. You just need a heater to let it out.