Deepak Kota - 1 year ago 140
Python Question

# First Digits of a number

I want the first 9 digits and last 9 digits of a fibonocci series for an infinite loop. Running the tests individually, I get better result for the last 9 digits using modulo operator no where comparable to the first 9 digits. I ran different tests like

`int(str(b)[::-1])%10**9, b/(10**(len(str(b))-9))`
but still the same result. I think this happens because of number to string conversion of higher digits. Is there any other way of printing the first 9 digits without converting into a string or an efficient way with/without strings?

``````def fibby():
a,b = 1,1
yield [a,a]
yield [b,b]
while True:
a,b = b,a+b
yield [str(b)[:9], b%10**9]
``````

Here are a few versions and timings for getting the first 30000 prefixes. I left out the first two yields and the last digits for simplicity.

• `fibby1` is the original way just using `str(b)[:9]`.
• `fibby2` keeps track of the appropriate power of 10 to divide by.
• `fibby3` keeps the first 9 digits in `a` and `b` and the remaining digits in `A` and `B`. Compared to `fibby2`, this avoids dividing a large `b` by a large power of 10. Large numbers are only added/subtracted/compared, or multiplied with a tiny number.
• `fibby4` uses `math.log10` suggested by @therefromhere.
• `fibby5` uses the `decimal` module.

The output:

``````All agree? True
fibby1: 24.835 seconds
fibby2:  0.289 seconds
fibby3:  0.201 seconds
fibby4:  2.802 seconds
fibby5:  0.216 seconds
``````

Just for comparison I also tried `str(b % 10**9)`, i.e., the last nine digits, and that took 0.506 seconds. Which is slower than my fast solutions for the first nine digits.

The code:

``````def fibby1():
a, b = 1, 1
while True:
yield str(b)[:9]
a, b = b, a+b

def fibby2():
a, b = 1, 1
div = 1
while True:
while True:
front = b // div
if front < 10**9:
break
div *= 10
yield str(front)
a, b = b, a+b

def fibby3():
a,b = 1,1
A,B,C = 0,0,1
while True:
yield str(b)
a, b = b, a+b
A, B = B, A+B
if B >= C:
B -= C
b += 1
if b >= 10**9:
A += a%10 * C
B += b%10 * C
a //= 10
b //= 10
C *= 10

def fibby4():
from math import log10
a, b = 1, 1
while True:
yield str(b // 10**max(0, int(log10(b) - 8)))
a, b = b, a+b

def fibby5():
from decimal import Decimal, getcontext
getcontext().prec = 7000 # enough for n = 30000
a, b = Decimal(1), Decimal(1)
while True:
yield str(b)[:9]
a, b = b, a+b

from timeit import timeit
from itertools import islice
from time import time

n = 30000
t0 = time()
list1 = list(islice(fibby1(), n))
t1 = time()
list2 = list(islice(fibby2(), n))
t2 = time()
list3 = list(islice(fibby3(), n))
t3 = time()
list4 = list(islice(fibby4(), n))
t4 = time()
list5 = list(islice(fibby5(), n))
t5 = time()
print('All agree?', list1 == list2 == list3 == list4 == list5)
print('fibby1: %6.3f seconds' % (t1 - t0))
print('fibby2: %6.3f seconds' % (t2 - t1))
print('fibby3: %6.3f seconds' % (t3 - t2))
print('fibby4: %6.3f seconds' % (t4 - t3))
print('fibby5: %6.3f seconds' % (t5 - t4))
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download