User avatar
Paeryn
Posts: 2704
Joined: Wed Nov 23, 2011 1:10 am
Location: Sheffield, England

Re: A little fun with REALLY big python numbers

Sat Nov 03, 2018 10:14 pm

jahboater wrote:
Sat Nov 03, 2018 8:19 am
I "suspect" that GCC has deduced the relationship between recur_fibo(n-1) and recur_fibo(n-2) and therefore doesn't need to call it a second time.
Its only my guess, as the asm gives me a headache too. GCC 7+ intersperses the original C source code with asm insns but its not making it clearer here.

BTW I changed it to an expression.

static int
recur_fibo( const int n )
{
return n <= 1 ? n : recur_fibo(n-1) + recur_fibo(n-2);
}
GCC 8.1 doesn't do all the unrolling (some in main() but not in the function itself) but the function is being reduced to one recursive call in a loop.
GCC 6.3 is further inlining the function 4 times inside itself.

Converting the ARM assembly back into C gives

Code: Select all

static int
opt_fibbo( const int n )
{
  if (n <= 1)
    return n;
  int n2 = n - 2;
  int n_stop = n - 3 - (n2 & -2);
  int total = 0;
  for (int x = n - 1; x != n_stop; x -= 2)
    total += opt_fibbo(x);
  total += n2 & 1;
  return total;
}
The limit can be optimised out (it is either 0 or -1 so we can loop until x <= 0) and the final increment of total can be moved to the initialisation, not sure why gcc doesn't see this.

Code: Select all

static int
opt_fibbo( const int n )
{
  if (n <= 1)
    return n;

  int total = n & 1;
  for (int x = n - 1; x > 0; x -= 2)
    total += opt_fibbo(x);
  return total;
}
Strangely, clang-4 doesn't do much to the original function (keeps it as summing the two recursive calls) but it does unroll my final version like gcc 6.3 was doing to the original, and to roughly the same depth (5).

Hand-inlining the code (which gives roughly what gcc is doing in 6.3)

Code: Select all

static int
fib( const int n )
{
    if (n <= 1)
       return n;
    int t = n & 1;
    for (int n1 = n-1; n1 > 0; n1 -= 2) {
        t += n1 & 1;
        if (n1 <= 1)
            break;
        for (int n2 = n1-1; n2 > 0; n2 -= 2) {
            t += n2 & 1;
            if (n2 <= 1)
                break;
            for (int n3 = n2 - 1; n3 > 0; n3 -= 2) {
                t += n3 & 1;
                if (n3 <= 1)
                    break;
                for (int n4 = n3 - 1; n4 > 0; n4 -= 2) {
                    t += n4 & 1;
                    if (n4 <= 1)
                        break;
                    for (int n5 = n4 - 1; n5 > 0; n5 -= 2) {
                        t += fib( n5 );
                    }
                }
            }
        }
    }
    return t;
}
Just for completeness, the same in Python :-

Code: Select all

import timeit

def recur_fibbo(n):
    if n <= 1:
        return n
    else:
        return recur_fibbo(n-1) + recur_fibbo(n-2)

def opt_fibbo(n):
    if n <= 1:
        return n
    else:
        total = n & 1
        for x in range (n-1, 0, -2):
            total = total + opt_fibbo(x)
        return total

nterms = 25

def run_recur():
    for i in range(nterms):
        print(i, recur_fibbo(i))

def run_opt():
    for i in range(nterms):
        print(i, opt_fibbo(i))

recur_time = timeit.timeit('run_recur()', setup="from __main__ import run_recur", number=10)
opt_time = timeit.timeit('run_opt()', setup="from __main__ import run_opt", number=10)

print('Recur time = {}'.format(recur_time))
print('Opt time = {}'.format(opt_time))
For Python the original is faster. For C the opt version is faster (and my hand-inlined opt is faster than that).
She who travels light — forgot something.

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

Re: A little fun with REALLY big python numbers

Sun Nov 04, 2018 10:24 am

Interesting, thanks.
Its a pity the compiler couldn't remove the recursion completely, even so gcc seems to have a better understanding of the problem than I have!

asm to C isn't something I have done very much of, but I tried the same on aarch64 which I usually find easier to read
It looks quite different.

Code: Select all

recur_fibo:
    mov w19, w0  // n2 = n
    mov w20, 0   // total = 0
    mov w21, w0  // save_n = n
    
.L3:
    cmp w19, 1   // if( n2 <= 1 ) break
    ble .L2
    sub w0, w19, 1     // n = n2 - 1
    sub w19, w19, 2    // n2 -= 2
    bl  recur_fibo     // n = recur_fibo(n)
    add w20, w20, w0   // total += n
    b   .L3

.L2:
    lsr w0, w21, 1   // n = save_n / 2
    mov w1, -2
    madd    w0, w0, w1, w21 // n = (n * -2) + save_n
    add w0, w0, w20  // total += n
    ret

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

Re: A little fun with REALLY big python numbers

Sun Nov 04, 2018 8:07 pm

That's a great piece of reverse engineering Paeryn. I'll have to find time to look at it properly. The ASM gave me headache, now your C gives me headache!
Memory in C++ is a leaky abstraction .

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

Re: A little fun with REALLY big python numbers

Sun Nov 04, 2018 9:00 pm

Getting back to the topic of big numbers:

A few posts back we were taking up gkreidl's challenge to calculate big Fibonacci numbers.

We got to the 400001th Fibonacci number using Python's big integers and the bignum module in Javascript. With the following results:

Code: Select all

fibo(400001):
JS     : 3  seconds with a total run time of about  5 seconds.
Python : 20 seconds with a total run time of about 40 seconds.
This got me guessing there are faster algorithms to do this and sure enough there are. So now I have this stunning result:

Code: Select all

fibo(400001):
JS     :  14 milliseconds with a total run time of about  0.5 seconds.
That is pretty stunning !
Most of that run time is displaying the result.

How is this magic done?

Well I found these nice equations for calculating Fibonacci numbers https://www.nayuki.io/page/fast-fibonacci-algorithms See "Fast Doubling" at the bottom of the page.

Implementing that recursively gets us to about 1 minute to do the job. But then I add some memoization and boom it takes no time at all.

Here is the code:

Code: Select all

var bignum = require('bignum');

function isEven(n) {
  return n % 2 === 0;
}

let memo = [bignum(0), bignum(1), bignum(1)]

function fiboFast (k) {
  let i = k
  let res
  if (memo[k]) {
    res = memo[k]
  } else if (isEven(k)) {
    k = k / 2
    res = fiboFast(k) .mul ((fiboFast(k + 1) .mul (2)) .sub (fiboFast(k)))
  } else {
    k = ((k + 0.5) / 2)|0
    let f = fiboFast(k)
    let f1 = fiboFast(k + 1)
    res = (f1.pow(2)) .add ((f.pow(2)))
  }
  memo[i] = res
  return res
}

let k = 400001

let t = new Date()

f = fiboFast(k)

let dur = new Date() - t
let fs = f.toString()
console.log(fs)
console.log(fs.length, "digits")
console.log(dur + "ms")
And here is the result:

Code: Select all

$ time node fiboFast.js
...
947841142842292600223177808511231471431584086256462442917968655682697969250521391177719540915132752661447337501
83595 'digits'
14ms

real    0m0.485s
user    0m0.328s
sys     0m0.141s

I'd love it if some kind soul would verify this result because it's so amazing I feel I must have made a mistake somewhere.

I'd also love to see a Python version if anyone is up to the challenge.
Memory in C++ is a leaky abstraction .

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

Re: A little fun with REALLY big python numbers

Sun Nov 04, 2018 11:03 pm

Big number challenge:

Using ones own Python code, who can tell which of the Fibonacci numbers is the first to have one million digits?

That is to say the value of n such that n is the first fibo(n) to have a million decimal digits.

No cheating, own code only. Do show your code.

Hint: The first and last 10 digits of the first million digit Fibonacci number are 1072739564....8405156269.

Amusingly if one enters that n into this online Fibobacci calculator: http://php.bubble.ro/fibonacci/ it responds with:

"Fibo(dedacted) has about 1000000 decimals. Have fun computing that."

Pfff... it's easy, only takes 1 second on my PC. And half a minute to create a string to display.

I guess I did have fun computing that !
Memory in C++ is a leaky abstraction .

User avatar
Paeryn
Posts: 2704
Joined: Wed Nov 23, 2011 1:10 am
Location: Sheffield, England

Re: A little fun with REALLY big python numbers

Mon Nov 05, 2018 4:26 am

Will this do? Rapidly searches for a number that is at least the required length, then divide and conquer to find the first one in that range.
<Edited> Now computes the number of digits rather than comparing the value to 10^100,000. Turns out it is slightly faster by about 3 seconds on the RPi (wasn't sure about how long log(x) would take on such big numbers).

Code: Select all

import timeit
import math

fibs = {0:0, 1:1, 2:1}

def fib(n):
    if n in fibs:
        return fibs[n]

    k = (n + 1) // 2
    fk = fib(k)
    fk1 = fib(k - 1)
    if n & 1:
        result = fk ** 2 + fk1 ** 2
    else:
        result = (2 * fk1 + fk) * fk
    fibs[n] = result
    return result

log10e = math.log10(math.e)  # No point calculating it each time

def num_digits(x):
    global log10e
    return math.ceil(log10e * math.log(x))

def find_first_with_length(digits):
    upper = 1
    value = 1
    while (num_digits(value) < digits):
        upper = upper * 2
        print('Testing fib({})'.format(upper))
        value = fib(upper)
    lower = upper // 2
    mid = (upper + lower) // 2
    while (mid != upper and mid != lower):
        print('Between {low} and {upp}, testing {mid}'.format(low=lower,upp=upper,mid=mid))
        value = fib(mid)
        if num_digits(value) >= digits:
            upper = mid
        else:
            lower = mid
        mid = (upper + lower) // 2
    return upper

value = find_first_with_length(1000000)
print('f({index}) has one million digits'.format(index=value))

command = 'fib({})'.format(value)
#time_to_run = timeit.timeit(command, 'from __main__ import fib', number=1)
#print('Took {time} seconds to run {cmd}'.format(time=time_to_run, cmd=command))
result = eval(command)
result_str = str(result)
length = len(result_str)
print('It contains {size} digits.'.format(size=length))
if length < 80:
    print(result_str)
else:
    print('First and last 38 digits:\n{}...{}'.format(result_str[:38], result_str[-38:]))
My PC does this in 24 seconds (only printing 76 digits of the Fibonacci number). Still waiting for the RPi to generate the string... Oh - it's done it, 9 minutes and 52 seconds. I'll run it again and see how long it takes just to find it without generating the one million character string, 3 minutes and 59 seconds, so it takes longer to convert the number into a string than it took to find it ;-)

Code: Select all

[email protected] ~/programming/fibo $ time python3 fib.py 
Testing fib(2)
Testing fib(4)
Testing fib(8)
Testing fib(16)
Testing fib(32)
Testing fib(64)
Testing fib(128)
Testing fib(256)
Testing fib(512)
Testing fib(1024)
Testing fib(2048)
Testing fib(4096)
Testing fib(8192)
Testing fib(16384)
Testing fib(32768)
Testing fib(65536)
Testing fib(131072)
Testing fib(262144)
Testing fib(524288)
Testing fib(1048576)
Testing fib(2097152)
Testing fib(4194304)
Testing fib(8388608)
Between 4194304 and 8388608, testing 6291456
Between 4194304 and 6291456, testing 5242880
Between 4194304 and 5242880, testing 4718592
Between 4718592 and 5242880, testing 4980736
Between 4718592 and 4980736, testing 4849664
Between 4718592 and 4849664, testing 4784128
Between 4784128 and 4849664, testing 4816896
Between 4784128 and 4816896, testing 4800512
Between 4784128 and 4800512, testing 4792320
Between 4784128 and 4792320, testing 4788224
Between 4784128 and 4788224, testing 4786176
Between 4784128 and 4786176, testing 4785152
Between 4784128 and 4785152, testing 4784640
Between 4784640 and 4785152, testing 4784896
Between 4784896 and 4785152, testing 4785024
Between 4784896 and 4785024, testing 4784960
Between 4784960 and 4785024, testing 4784992
Between 4784960 and 4784992, testing 4784976
Between 4784960 and 4784976, testing 4784968
Between 4784968 and 4784976, testing 4784972
Between 4784968 and 4784972, testing 4784970
Between 4784968 and 4784970, testing 4784969
f(4784969) has one million digits
It contains 1000000 digits.
First and last 38 digits:
10727395641800477229364813596225004321...07167474856539211500699706378405156269

real	0m24.529s
user	0m24.439s
sys	0m0.080s
She who travels light — forgot something.

User avatar
bertlea
Posts: 299
Joined: Wed Dec 07, 2016 6:33 am
Location: Hong Kong

Re: A little fun with REALLY big python numbers

Mon Nov 05, 2018 5:51 am

Javascript also got BigInt in proposal (TC39 stage 3) now and latest version of Chrome and Node.js (since 10.4.0) implemented it. I did a simple test and it seems the Javascript BigInt also able to do bitwise operations such as left-shift (makes the value double). It will be nice if someone good at both JS and Python to test and compare the 2 implementations (Python3 vs JS in V8) on the same system.

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

Re: A little fun with REALLY big python numbers

Mon Nov 05, 2018 6:53 am

Paeryn,

Yes, that will do nicely. Awesome, thanks.

On my big old PC fibo(4784969) takes:

Code: Select all

Python : 770 ms with a total run time of about 17 seconds.

vs

JS     : 1218 ms with a total run time of about 34 seconds.
So I take it all back. Python is actually pretty good with it's big integers. It's the first time I have seen Python outpace JS. If you want to work with big integers Python is the way to go.

That's a pretty amazing way of calculating fibo don't you think. That I had never come across before. A big thanks to Nayuki at https://www.nayuki.io for that.
Memory in C++ is a leaky abstraction .

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

Re: A little fun with REALLY big python numbers

Mon Nov 05, 2018 8:02 am

bertlea,

Thanks for the heads up on BigInt in JS. You know, I had heard rumror of this a while back and it totally escaped my mind.
It will be nice if someone good at both JS and Python to test and compare the 2 implementations (Python3 vs JS in V8) on the same system.
OK, below is our fast Fibonacci in JS using the new BigInt, calculating the million digits of fibo(4784969) on my PC. Now I have the results:

Code: Select all

Python2         : 770 ms with a total run time of about 17 seconds.

Python3         : 705 ms with a total run time of about 17 seconds.

JS (bignum)     : 1218 ms with a total run time of about 34 seconds.

JS (BigInt)     : 8140 ms with a total run time of about 60 seconds.
The new BigInt in Javascript is about 10 times slower than Python.
Using the old bignum module JS is about half the speed of Python.

Perhaps not surprising, bignum uses the big integer features of the openssl library which has been around for ages and BigInt is a new language feature that may get honed over time.

Still it's neat that we don't need to turn to Python for big integer work anymore. Not that I use big integers very often.

Code: Select all

function isEven(n) {
  return n % 2 === 0;
}

let memo = [BigInt(0), BigInt(1), BigInt(1)]
let two = BigInt(2)

function fiboFast (k) {
  let i = k
  let res
  if (memo[k]) {
    res = memo[k]
  } else if (isEven(k)) {
    k = k / 2
    res = fiboFast(k) * ((fiboFast(k + 1) * two) - fiboFast(k))
  } else {
    k = ((k + 0.5) / 2)|0
    let f = fiboFast(k)
    let f1 = fiboFast(k + 1)
    res = (f1 * f1) + (f * f)
  }
  memo[i] = res
  return res
}

let res

function timeIt (f, k) {
  t = new Date()
  res = f(k)
  dur = new Date() - t
  console.log(res)
  console.log(dur + "ms")
}

timeIt(fiboFast, 4784969)
Memory in C++ is a leaky abstraction .

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

Re: A little fun with REALLY big python numbers

Mon Nov 05, 2018 8:22 am

If BigInt can do bitwise operations, perhaps:-

function isEven(n) {
return n % 2 === 0;
}
if (isEven(k)) { k = k / 2 ...

could be reduced to something like (removing two costly divisions and a function call):

if ( (k & 1) == 0 ) { k >>= 1 ...

Maybe the JS optimizer does that anyway.

I wonder how the 0.5 is dealt with in "k = ((k + 0.5) / 2)" ?
I think "k = k / 2" might be OK, I'm not sure the rounding is needed (produces the correct results for a few smallish tests).

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

Re: A little fun with REALLY big python numbers

Mon Nov 05, 2018 9:05 am

For amusement only:

fibo 4784969 in C

$ time ./fibo >/dev/null

real 0m0.195s
user 0m0.188s
sys 0m0.004s

Code: Select all

int main( void )
{
  mpz_t res;
  mpz_init( res );

  mpz_fib_ui( res, 4784969 );

  gmp_printf( "%Zd\n", res );
}
GMP (GNU Multiple Precision) is not part of C like Python and JS, its n external library (-lgmp), but it is very effective.
There is also arbitrary precision floating-point with IEEE semantics (correct rounding control for example) and a large library of math functions.
Last edited by jahboater on Mon Nov 05, 2018 9:44 am, edited 1 time in total.

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

Re: A little fun with REALLY big python numbers

Mon Nov 05, 2018 9:40 am

jahboater,
If BigInt can do bitwise operations, perhaps:-
BigInt is not required there. We are testing the k values which are just normal JS numbers not BigInts. Only the resulting fibo numbers are BigInts. We will never have a big enough computer to require k to be a BigInt as well !

Changing to a logical test does work:

Code: Select all

function isEven(n) {
  return (n & 1) === 0;
}
Makes no difference to the run time.

I defined the isEven() function so as to make the code descriptive of what is going on rather than add a comment.
I wonder how the 0.5 is dealt with in "k = ((k + 0.5) / 2)" ?
k is an odd integer at that point. Javascript handles integers up to 53 bits perfectly well but as soon as you divide them by 2 they get converted to floats. At which point everything blows up. That is what the "|0" is for. Logic operations on numbers in JS force them to be 32 bit integers.

The "+0.5" is there because otherwise we have the same case as for the evens. For the odds we need k to be one bigger.

Can you show the source of the C version? I'd like to compare on my machine just for completeness.
Memory in C++ is a leaky abstraction .

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

Re: A little fun with REALLY big python numbers

Mon Nov 05, 2018 9:51 am

Heater wrote:
Mon Nov 05, 2018 9:40 am
Can you show the source of the C version? I'd like to compare on my machine just for completeness.
This is the plain "int" version. I was about to convert it to big nums, but spotted the purpose made library function mpz_fib() see post above.

Code: Select all

#include <stdio.h>

#define even(n) ((n & 1) == 0)

static int
fibofast( int k )
{
  static int memo[] = { 0, 1, 1 };
  int res, i = k;
  if( memo[k])
    res = memo[k];
  else if( even(k) )
  {
    k >>= 1;
    res = fibofast(k) * ((fibofast(k + 1) * 2) - fibofast(k));
  }
  else
  {
    k >>= 1;
    const int f = fibofast(k), f1 = fibofast(k + 1);
    res = (f1 * f1) + (f * f);
  }
  memo[i] = res;
  return res;
}

int
main( int argc, const char *argv[] )
{
  printf( "%d\n", fibofast( 37 ) );
}

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

Re: A little fun with REALLY big python numbers

Mon Nov 05, 2018 10:04 am

Oops, yes, I missed that little detail. The big fibo is already a library function.
Memory in C++ is a leaky abstraction .

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

Re: A little fun with REALLY big python numbers

Mon Nov 05, 2018 10:10 am

Heater wrote:
Mon Nov 05, 2018 9:40 am
k is an odd integer at that point. Javascript handles integers up to 53 bits perfectly well but as soon as you divide them by 2 they get converted to floats. At which point everything blows up.
There are various library functions for manipulating the exponent directly:

ldexp - multiply floating-point number by integral power of 2

ldexp( k, -1 )

is the same as k / 2

I don't know if JS has anything equivalent.

User avatar
Paeryn
Posts: 2704
Joined: Wed Nov 23, 2011 1:10 am
Location: Sheffield, England

Re: A little fun with REALLY big python numbers

Mon Nov 05, 2018 10:11 am

Heater wrote:
Mon Nov 05, 2018 9:40 am
I wonder how the 0.5 is dealt with in "k = ((k + 0.5) / 2)" ?
k is an odd integer at that point. Javascript handles integers up to 53 bits perfectly well but as soon as you divide them by 2 they get converted to floats. At which point everything blows up. That is what the "|0" is for. Logic operations on numbers in JS force them to be 32 bit integers.

The "+0.5" is there because otherwise we have the same case as for the evens. For the odds we need k to be one bigger.

Can you show the source of the C version? I'd like to compare on my machine just for completeness.
Surely if k is an integer then adding 0.5 before dividing by 2 is going to have no effect. Adding 0.5 is going to add 0.25 to the result, the result of dividing an odd number by two will have a result ending with 0.5, if you add a half first then the result now ends with 0.75, either way as soon as you convert that back to an integer you have the same result (assuming the logical operation is truncating and not rounding).

In my version I use a slightly different transform using f(k-1) rather than f(k+1), that needs odd numbers rounding up so I have k = (n + 1) // 2
She who travels light — forgot something.

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

Re: A little fun with REALLY big python numbers

Mon Nov 05, 2018 10:16 am

If you want to try the library function (you could redirect the output to a file and compare it to the other versions to confirm correctness)
the complete source is:-

Code: Select all

#include <stdio.h>
#include <gmp.h>

int
main( void )
{
  mpz_t res;
  mpz_init( res );

  mpz_fib_ui( res, 4784969 );

  gmp_printf( "%Zd\n", res );
}
Compile with: gcc fibo.c -o fibo -lgmp

You may need "sudo apt install gmp"

Info at
https://gmplib.org/manual/GMP-Basics.html#GMP-Basics
and
https://gmplib.org/manual/Integer-Funct ... -Functions

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

Re: A little fun with REALLY big python numbers

Mon Nov 05, 2018 12:36 pm

Paeryn,
Surely if k is an integer then adding 0.5 before dividing by 2 is going to have no effect....
By George you are right. What was I thinking?

In the light of that I rearranged the code a bit:

Code: Select all

let memo = [BigInt(0), BigInt(1), BigInt(1)]
let two = BigInt(2)

function fibo (n) {
  if (memo[n]) {
    return  memo[n]
  }
  let k = (n / 2) | 0
  if (isEven(n)) {
    return memo[n] = fibo(k) * ((fibo(k + 1) * two) - fibo(k))
  }
  let f = fibo(k)
  let f1 = fibo(k + 1)
  return memo[n] = (f1 * f1) + (f * f)
}
Thanks.
Memory in C++ is a leaky abstraction .

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

Re: A little fun with REALLY big python numbers

Mon Nov 05, 2018 12:40 pm

Thanks jahboater. The GMP versions works a treat. Blinding!
Memory in C++ is a leaky abstraction .

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

Re: A little fun with REALLY big python numbers

Mon Nov 05, 2018 1:41 pm

There is a version mpz_fib2 for producing a sequence.
https://gmplib.org/manual/Number-Theore ... -Functions

User avatar
Paeryn
Posts: 2704
Joined: Wed Nov 23, 2011 1:10 am
Location: Sheffield, England

Re: A little fun with REALLY big python numbers

Mon Nov 05, 2018 1:47 pm

Heater wrote:
Mon Nov 05, 2018 12:36 pm
Paeryn,
Surely if k is an integer then adding 0.5 before dividing by 2 is going to have no effect....
By George you are right. What was I thinking?
We all have those moments! I won't say what silly mistake I was originally doing to test for a one million digit Fibonacci number, suffice to say it kept settling on one that wasn't the first (either that or was one digit longer or shorter).
She who travels light — forgot something.

User avatar
bertlea
Posts: 299
Joined: Wed Dec 07, 2016 6:33 am
Location: Hong Kong

Re: A little fun with REALLY big python numbers

Tue Nov 06, 2018 9:52 am

Thank you @Heater for writing the code and test it. I am having some fun to run your code on my PC. Somehow I found the run time using your revised function ("In the light of that I rearranged the code a bit:"...) runs about 6 times slower compared to your first version on my machine. I am not sure what is causing that.

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

Re: A little fun with REALLY big python numbers

Tue Nov 06, 2018 1:32 pm

That is a bit odd.

My latest version, using JS standard BigInt, is about twice the run time of the previous version using the bignum module.

What version of node.js do you have? I'm using v11.1.0
Memory in C++ is a leaky abstraction .

User avatar
bertlea
Posts: 299
Joined: Wed Dec 07, 2016 6:33 am
Location: Hong Kong

Re: A little fun with REALLY big python numbers

Wed Nov 07, 2018 7:06 am

I am only talking about the new BigInt not about the bignum and there are two BigInt versions you showed. The first one is called fiboFast(k) that you showed when you reply my first post here.

Code: Select all

function fiboFast (k) {
    let i = k;
    let res;

    if (memo[k]) {
        res = memo[k];

    } else if (isEven(k)) {
        k = k / 2;
        res = fiboFast(k) * ((fiboFast(k + 1) * 2n) - fiboFast(k));
    } else {
        k = ((k + 0.5) / 2) | 0;
        res = fiboFast(k) ** 2n + fiboFast(k + 1) ** 2n;
    }

    memo[i] = res;
    return res;
}
The second one is called fibo(n) when you replied Paeryn, later.

Code: Select all

function fibo (n) {
    if (memo[n]) {
        return memo[n];
    }

    let k = (n / 2) | 0;

    if (isEven(n)) {
        return fiboFast(k) * ((fiboFast(k + 1) * 2n) - fiboFast(k));
    }

    return fiboFast(k) ** 2n + fiboFast(k + 1) ** 2n;
}
I found the second one runs 6 times slower (~60,000 ms) compare to the first one (~ 10,000 ms). I am using node.js version 10.12.0 running on my Windows 7 i-5 laptop (Dell Latitude 5480). May be the function name got a "Fast" there for a reason! :P
Notes, I changed the style a bit using the trailing-n notation and I do not use the “two” variable. But these should not affect the performance.

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

Re: A little fun with REALLY big python numbers

Wed Nov 07, 2018 10:27 am

bertlea,

You have missed a very important feature. When I moved to the newer version I did away with "res" variable and returned the results immediately. But not before stuffing them into the memo array with an assignment. Like so:

return memo[n] = ....

With that back in place your version is back up to speed. Like so:

Code: Select all

function isEven(n) {
  return (n & 1) === 0;
}

let memo = [BigInt(0), BigInt(1), BigInt(1)]

function fibo (n) {
  if (memo[n]) {
    return memo[n];
  }
  let k = (n / 2) | 0;
  if (isEven(n)) {
      return memo[n] = fibo(k) * ((fibo(k + 1) * 2n) - fibo(k));
  }
  return memo[n] = fibo(k) ** 2n + fibo(k + 1) ** 2n;
}
Hadn't heard of the "2n" notation before. Thanks for the heads up on that.

I'm getting about 12 seconds here.

Here is an interesting observation: When I run fibo(4784969) twice in the same program the second time it only takes 1ms !!!

Like so:

Code: Select all

fibo(4784969)
timeIt(fibo, 4784969)
With result:

Code: Select all

...
1766313865956891695455563801462249978567353436540666740580717167763216988216644330074030719891463180149736853685001275152076875379936330930391815964864885353407167474856539211500699706378405156269n
1ms

real    0m57.180s
user    0m56.875s
sys     0m0.156s
$
Seems Javascript is memoizing results of BigInt calculations some how.

Are you seeing the same?
Memory in C++ is a leaky abstraction .

Return to “Python”