User avatar
paddyg
Posts: 2389
Joined: Sat Jan 28, 2012 11:57 am
Location: UK

Re: A little fun with REALLY big python numbers

Wed Nov 07, 2018 2:15 pm

Apologies in advance for dredging up the earlier diversion (from the OP 'big numbers' thoughts) but it wasn't apparent from the dialogue that people were aware of numba @jit.

So, with this tiny addition before the function def

Code: Select all

from numba import jit
@jit
def recur_fibo(...
I get

Code: Select all

[email protected]:~/python/pi3d_demos$ time node fibo.js
...
14930352

real	0m0.932s
user	0m0.910s
sys	0m0.016s

[email protected]:~/python/pi3d_demos$ time python3 fibo.py
...
14930352

real	0m0.760s
user	0m0.699s
sys	0m0.044s
also https://groups.google.com/forum/?hl=en-GB&fromgroups=#!forum/pi3d

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

Re: A little fun with REALLY big python numbers

Wed Nov 07, 2018 9:42 pm

What is this "numba @jit" of which you speak?

My machine seems to not have one and not being a Python guy I have no idea where to get one.

If you have a moment how does this jit deal with fibo(4784969) ?

So that we can compare with our latest experiments in Python and JS.
Memory in C++ is a leaky abstraction .

User avatar
paddyg
Posts: 2389
Joined: Sat Jan 28, 2012 11:57 am
Location: UK

Re: A little fun with REALLY big python numbers

Wed Nov 07, 2018 11:36 pm

see https://numba.pydata.org/ it's not as battle hardened as js but I think it's the scientific python users trying to streamline the odd bottleneck function without refactoring the problem into numpy, tensorflow or cython. It is geared up to split over parallel processors quite easily.

I will look at fibo(4784969) but I don't know what big number capacity is built into it.

EDIT

OK, running fibo(4784969) on this computer with vanilla python3 gave a timeit value of 0.69ms0.70s, with numba jit this worsened to 0.81ms0.71s. The reason was that it can't convert the function to jit (it fails if nopython=True initially because dict isn't yet supported but I don't think it will be able to cope without some bigint functionality)

PS for completeness I looked a bit more at this and a) spotted an error in which the same dict was reused between timeit runs :oops: so underestimated the time to do the calculation by 1000x! b) I modified the python code to use a ndarray instead of the dict which can calculate up to fibo(90) without overflowing. I also found that numba makes globals into static variables so fibs has to be passed in as a function argument. Using the code below the numba @jit function works out fibo(90) in 2.8micros c.f. vanilla python3 in 9.6micros

Code: Select all

import timeit

setup = '''
import math
import numpy as np
from numba import jit

N = 90
fibs = np.ones((N,), dtype=np.int64)

@jit(nopython=True)
def fib(n, fibs):
    if fibs[n] > -1:
        return fibs[n]

    k = (n + 1) // 2
    fk = fib(k, fibs)
    fk1 = fib(k - 1, fibs)
    if n & 1:
        result = fk ** 2 + fk1 ** 2
    else:
        result = (2 * fk1 + fk) * fk
    fibs[n] = result
    return result
'''
fn = '''
fibs[:3] = [0, 1, 1]
fibs[3:] = -1
fib(N, fibs)
'''
print(timeit.timeit(fn, setup=setup, number=1000000))
Last edited by paddyg on Fri Nov 09, 2018 6:15 pm, edited 1 time in total.
also https://groups.google.com/forum/?hl=en-GB&fromgroups=#!forum/pi3d

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

Thu Nov 08, 2018 3:18 am

@Heater, thanks for fixing my manual copy mistake! It works and yes, I also got the "1 ms" when I run it for the second time.

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

Re: A little fun with REALLY big python numbers

Thu Nov 08, 2018 3:22 am

Thanks. numba looks very cool.
Memory in C++ is a leaky abstraction .

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

Re: A little fun with REALLY big python numbers

Fri Nov 23, 2018 2:43 am

I know this is late, but I knew finding which index is the first Fibonacci number with one million digits can be done very quickly, your common-or-garden calculator can do it. Makes my earlier brute-force search very bad ;-)

I've only just gotten around to doing the maths on paper (it's been buzzing around my head like a wasp). I think it will always get it, there might be a corner case somewhere because it doesn't take into account phi which very quickly becomes insignificant (that term gets closer to 0 the higher you go) which is why 1 is handled separately (otherwise the formula calculates it as 2).

In Python (just calculating the index, not the number):

Code: Select all

import math
def first_fibo_index_of_size(x):
  if x == 1:
    return 1
  sqrt5 = math.sqrt(5)
  Phi = (1 + sqrt5) / 2
  i = (x - 1 + math.log10(sqrt5)) / math.log10(Phi)
  return int(i) + 1
Running it:

Code: Select all

>>> print('Fibo({}) is the first Fibonacci number with one million digits'.format(first_fibo_index_of_size(1000000))
Fibo(47894969) is the first Fibonacci number with one million digits.
I'm not even bothering to time it!
She who travels light — forgot something.

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

Re: A little fun with REALLY big python numbers

Fri Nov 23, 2018 2:35 pm

Paeryn,

We have a winner! Congratulations.

You have the shortest fastest code that answers the challenge.

Strangely enough I was trying to get the same formula working in JS this morning. I was too tired to get it right...

Of course what I had intended by the challenge was to produce the actual number. But that is not how I worded it:

"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."[/n]
Memory in C++ is a leaky abstraction .

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

Re: A little fun with REALLY big python numbers

Fri Nov 23, 2018 6:03 pm

Yes, I knew the idea was to get the actual value, but this tells you which to calculate (rather than searching) So using both methods finds the answer in the quickest time.

I must get around to calculating the first with one billion digits (and by that I mean a proper billion i.e. a million million, not an American billion). It should be roughly Fibo(47,874,971,966,778) though I'm not sure if the formula is suffering from imprecise floats on my calculator. I don't fancy waiting for the naive iterative method to check it!

Theoretically you can calculate the actual value in constant time provided you can raise a floating point number by a given power in one go, the only problem is calculating large powers of irrational numbers to sufficient accuracy takes progressively longer (floats and doubles are only good for small values) so the integer doubling rule is likely to be faster.

Phi = (sqrt(5) + 1) / 2
phi = (sqrt(5) - 1) / 2
F(n) = (pow(Phi, n) - pow(-phi, n)) / sqrt(5)
She who travels light — forgot something.

Return to “Python”