User avatar
John_Spikowski
Posts: 1397
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Tue Jun 25, 2019 4:46 am

The answer may be looking at the GMP extension module for Python.

Heater
Posts: 13391
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Tue Jun 25, 2019 6:03 am

ScriptBasic,
Is it my understanding all fibos using GMP leak?
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.

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?
The answer may be looking at the GMP extension module for Python.
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.

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 .

User avatar
John_Spikowski
Posts: 1397
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Tue Jun 25, 2019 1:53 pm

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.
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.
Dr. Jekyll / Hyde,

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.

Heater
Posts: 13391
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Tue Jun 25, 2019 4:21 pm

ScriptBasic,
You said your JavaScript GMP fibo leaked.
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.

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.
This isn't a ScriptBasic issue only.
Yes it is. What else could a problem in ScriptBasic's use of the GMP library be?
Stop trashing SB for your enjoyment.
Since when is reporting bugs considered "trashing"?
Memory in C++ is a leaky abstraction .

User avatar
John_Spikowski
Posts: 1397
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Tue Jun 25, 2019 4:37 pm

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.

Heater
Posts: 13391
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Tue Jun 25, 2019 5:01 pm

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.
Memory in C++ is a leaky abstraction .

User avatar
John_Spikowski
Posts: 1397
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Tue Jun 25, 2019 5:15 pm

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.

User avatar
John_Spikowski
Posts: 1397
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Tue Jun 25, 2019 8:04 pm

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 n-th 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 2-tuple with the (n-1)-th and n-th 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;
}

gkreidl
Posts: 6101
Joined: Thu Jan 26, 2012 1:07 pm
Location: Germany

Speeding up the fast doubling algorithm

Wed Jun 26, 2019 7:37 am

I implemented the fast doubling algorithm in Python 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):
        d = a*(b*2-a)
        e = a*a+b*b
        if (n >> i) & 1:
            a = e
            b = d + e 
        else:
            a = d
            b = e
    return a
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.

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*2-a)
            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*2-a)
    return d
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:

Code: Select all

[email protected]:~/fibochallenge $ ./fibo_rd.py -t -n
Fibonacci(4784969) calculation took 0.4217264652252197 seconds
[email protected]:~/fibochallenge $ ./fibo_rdr.py -t -n
Fibonacci(4784969) calculation took 0.4217088222503662 seconds
[email protected]:~/fibochallenge $ ./fibo_fd.py -t -n
Fibonacci(4784969) calculation took 0.5097312927246094 seconds
[email protected]:~/fibochallenge $ ./fibo_fdi.py -t -n
Fibonacci(4784969) calculation took 0.3734128475189209 seconds
Using Python's internal BIGINTs:

Code: Select all

[email protected]:~/fibochallenge $ ./fibo_rd.py -t -n -i
Fibonacci(4784969) calculation took 10.606588363647461 seconds
[email protected]:~/fibochallenge $ ./fibo_rdr.py -t -n -i
Fibonacci(4784969) calculation took 10.56157374382019 seconds
[email protected]:~/fibochallenge $ ./fibo_fd.py -t -n -i
Fibonacci(4784969) calculation took 13.833927631378174 seconds
[email protected]:~/fibochallenge $ ./fibo_fdi.py -t -n -i
Fibonacci(4784969) calculation took 9.754611492156982 seconds
Attachments
fibochallenge.tar.gz
(1.82 KiB) Downloaded 25 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

User avatar
Gavinmc42
Posts: 3761
Joined: Wed Aug 28, 2013 3:31 am

Re: A Final Fibonacci Challenge

Wed Jun 26, 2019 8:15 am

Can we run all these again on a Pi4? whoops been asked :oops:
I'm dancing on Rainbows.
Raspberries are not Apples or Oranges

ejolson
Posts: 3588
Joined: Tue Mar 18, 2014 11:47 am

Re: Speeding up the fast doubling algorithm

Wed Jun 26, 2019 8:22 am

gkreidl wrote:
Wed Jun 26, 2019 7:37 am
I implemented the fast doubling algorithm in Python as shown below.
That's a nice roundup of Python codes. I'll run them through fibench on the super-cheap 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 single-core Cortex-A53, smaller process size and less requirements for electricity.

ejolson
Posts: 3588
Joined: Tue Mar 18, 2014 11:47 am

Re: A Final Fibonacci Challenge

Wed Jun 26, 2019 8:39 am

Gavinmc42 wrote:
Wed Jun 26, 2019 8:15 am
Can we run all these again on a Pi4? whoops been asked :oops:
It would be interesting to see which of those hand-coded big-number 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.

Heater
Posts: 13391
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Wed Jun 26, 2019 8:50 am

ejolson,
With all the Pi 4B excitement, it seems the updated JavaScript codes are somewhat delayed.
Ah, sorry about that.

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 .

jalih
Posts: 77
Joined: Mon Apr 15, 2019 3:54 pm

Re: Speeding up the fast doubling algorithm

Wed Jun 26, 2019 2:11 pm

gkreidl wrote:
Wed Jun 26, 2019 7:37 am
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*2-a)
            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*2-a)
    return d
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.
Nice one!

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 -- nbits-1
  n:ln 2 n:ln n:/ n:int ;


: fibo-loop
  >r                             \ Put loop counter on r-stack
  \ a b
  2dup 2 n:*                     \ a b a 2b
  over n:-                       \ a b a (2b-a)
  n:* -rot                       \ d=(2b-a)*a a b
  n:sqr swap n:sqr n:+           \ d=(2b-a)*a e=b*b+a*a
  r> [email protected] 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 r-stack
  F0 F1 \ a b
  ' fibo-loop 1 [email protected] 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:*  \ (2b-a)*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 ;
  
My original fibo using Fast Doubling took 245 millisecs to run on my PC. This version takes just 195 millisecs to run! Not bad at all!

jalih
Posts: 77
Joined: Mon Apr 15, 2019 3:54 pm

Re: A Final Fibonacci Challenge

Wed Jun 26, 2019 4:42 pm

Heater wrote:
Wed Jun 26, 2019 8:50 am
Looks like I have to checkout gkreidl's new approaches as well.
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*2-a)
    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*2-a)
  endif
  return a
endf

gkreidl
Posts: 6101
Joined: Thu Jan 26, 2012 1:07 pm
Location: Germany

Re: A Final Fibonacci Challenge

Wed Jun 26, 2019 6:09 pm

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*2-a)
        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*2-a)
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

User avatar
John_Spikowski
Posts: 1397
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Thu Jun 27, 2019 1:01 am

I'm amazed how much faster GMP is vs. native Python BIGINT. Can't wait until the ScriptBasic issues with GMP are worked out.

Heater
Posts: 13391
Joined: Tue Jul 17, 2012 3:02 pm

Re: A Final Fibonacci Challenge

Thu Jul 04, 2019 8:28 pm

Hey, I finally tracked down and fixed up the memory leak in my in-browser 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.
Memory in C++ is a leaky abstraction .

User avatar
John_Spikowski
Posts: 1397
Joined: Wed Apr 03, 2019 5:53 pm
Location: Anacortes, WA USA
Contact: Website Twitter

Re: A Final Fibonacci Challenge

Fri Jul 05, 2019 12:30 am

Congrats!

Maybe you can help me figured out why GMP leaks when used with the ScriptBasic extension module.

ejolson
Posts: 3588
Joined: Tue Mar 18, 2014 11:47 am

Re: A Final Fibonacci Challenge

Fri Jul 05, 2019 2:21 am

Heater wrote:
Thu Jul 04, 2019 8:28 pm
Surprisingly it is quicker to calculate fibo(5000000) than fibo(4784969). By about 30%. Which is a lot. Go figure.
In binary which number has more ones in it, 5000000 or 4784969?

jahboater
Posts: 4699
Joined: Wed Feb 04, 2015 6:38 pm

Re: A Final Fibonacci Challenge

Fri Jul 05, 2019 5:56 am

ejolson wrote:
Fri Jul 05, 2019 2:21 am
Heater wrote:
Thu Jul 04, 2019 8:28 pm
Surprisingly it is quicker to calculate fibo(5000000) than fibo(4784969). By about 30%. Which is a lot. Go figure.
In binary which number has more ones in it, 5000000 or 4784969?
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.

gkreidl
Posts: 6101
Joined: Thu Jan 26, 2012 1:07 pm
Location: Germany

Re: A Final Fibonacci Challenge

Fri Jul 05, 2019 6:39 am

jahboater wrote:
Fri Jul 05, 2019 5:56 am
ejolson wrote:
Fri Jul 05, 2019 2:21 am
Heater wrote:
Thu Jul 04, 2019 8:28 pm
Surprisingly it is quicker to calculate fibo(5000000) than fibo(4784969). By about 30%. Which is a lot. Go figure.
In binary which number has more ones in it, 5000000 or 4784969?
5000000 has 1735013 set bits
4784969 has 1660411 set bits

using the GMP function mpz_popcount()
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

jahboater
Posts: 4699
Joined: Wed Feb 04, 2015 6:38 pm

Re: A Final Fibonacci Challenge

Fri Jul 05, 2019 6:42 am

gkreidl wrote:
Fri Jul 05, 2019 6:39 am
jahboater wrote:
Fri Jul 05, 2019 5:56 am
ejolson wrote:
Fri Jul 05, 2019 2:21 am
In binary which number has more ones in it, 5000000 or 4784969?
5000000 has 1735013 set bits
4784969 has 1660411 set bits

using the GMP function mpz_popcount()
Nonsense.
5000000 = 0b010011000100101101000000
4784969 = 0b010010010000001101001001
I presumed Ejolson was referring to the fibonacci terms ?
4784969 has a million digits, counted the set bits in that.
Otherwise yes, they both have 8 set bits.

gkreidl
Posts: 6101
Joined: Thu Jan 26, 2012 1:07 pm
Location: Germany

Re: A Final Fibonacci Challenge

Fri Jul 05, 2019 6:56 am

jahboater wrote:
Fri Jul 05, 2019 6:42 am
gkreidl wrote:
Fri Jul 05, 2019 6:39 am
jahboater wrote:
Fri Jul 05, 2019 5:56 am

5000000 has 1735013 set bits
4784969 has 1660411 set bits

using the GMP function mpz_popcount()
Nonsense.
5000000 = 0b010011000100101101000000
4784969 = 0b010010010000001101001001
I presumed Ejolson was referring to the fibonacci terms ?
4784969 has a million digits, counted the set bits in that.
Otherwise yes, they both have 8 set bits.
Yes, but that was not the question.

Having more "1"s in the lowest bits is important.

Code: Select all

[email protected]:~/fibochallenge $ ./fibo_rd.py -t -n 4194320
Fibonacci(4194320) calculation took 0.2915217876434326 seconds
[email protected]:~/fibochallenge $ ./fibo_rd.py -t -n 4194319
Fibonacci(4194319) calculation took 0.3306257724761963 seconds
4194320 = 0x400010
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

jahboater
Posts: 4699
Joined: Wed Feb 04, 2015 6:38 pm

Re: A Final Fibonacci Challenge

Fri Jul 05, 2019 7:18 am

gkreidl wrote:
Fri Jul 05, 2019 6:56 am
Having more "1"s in the lowest bits is important.

Code: Select all

[email protected]:~/fibochallenge $ ./fibo_rd.py -t -n 4194320
Fibonacci(4194320) calculation took 0.2915217876434326 seconds
[email protected]:~/fibochallenge $ ./fibo_rd.py -t -n 4194319
Fibonacci(4194319) calculation took 0.3306257724761963 seconds
4194320 = 0x400010
4194319 = 0x40000f
Interesting.
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.

Return to “General programming discussion”