Liberation through Computer Literacy

[John_Spikowski]

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

[John_Spikowski]

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

[gkreidl]

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

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.

[John_Spikowski]

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

[Heater]

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

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
$

fibo.py

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
$

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

[John_Spikowski]

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

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

afibo.sb

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$

fibo.sb

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$

[Heater]

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:

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

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.

[gkreidl]

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

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
$

fibo.py

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
$

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

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]

gkreidl,

Why don't you mention the possible use of GMT BIGINTs in Python...

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.

[John_Spikowski]

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.

[John_Spikowski]

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.

Is this true?

[Heater]

ScriptBasic,

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

We have had this discussion before.

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.

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

Of course not. By the way, where does SciptBasic get it's memory from if it's not using malloc under the hood?

When did this become the native BIGINT club members only challenge?

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.

Others are welcome to entertain us with there feeble attempts with emulation.

I have no idea what that is supposed to mean. I have not seen any solutions that require emulators.

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.

[John_Spikowski]

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?

[John_Spikowski]

By the way, where does SciptBasic get it's memory from if it's not using malloc under the hood?

This memory manager is standalone and used in other applications besides ScriptBasic.

Peter Verhas's MyAlloc

[Heater]

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.

[John_Spikowski]

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?

[Heater]

ScriptBasic,

What other popular languages use GMP for BIGINT support?

I have no idea. It would not surprise me if some did.

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.

[DougieLawson]

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

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))

And rewrote that in a naïve C program (using math.h / libm)

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;
}

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).

[Heater]

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.

[jahboater]

What other popular languages use GMP for BIGINT support?

do an apt-cache search gmp
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.

[DougieLawson]

I do mean that simplistic approach

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;
}

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).

[jahboater]

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).

This is even simpler (and includes an overflow check),

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 );
}

The limit is 92 for signed 64 bit integers and 93 for unsigned integers.

[jahboater]

I didn't look at whether I could get to 128-bit integers with GMP (that's for another day).

GMP is arbitrary precision.
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.

[John_Spikowski]

I didn't look at whether I could get to 128-bit integers with GMP (that's for another day).

GMP is arbitrary precision.
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.

That function was the birth of the ScriptBasic GMP extension module.

[John_Spikowski]

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)