As others have pointed out, if you are brute-forcing this:
- there's no reason to keep the old values around in a list. You just need
a += b; b += a;
to go 2 steps, or in Python a,b = b,a+b
to go one step.
- binary integer -> base-10 digit string is very expensive, requiring repeated division by 10 or equivalent. (And that's division of the whole BigInteger by 10; it can't be done in chunks because the lowest decimal digit depends on all higher binary digits.) So compare against a threshold instead.
There's another trick nobody's mentioned:
Fib(n) grows fast enough that you can discard some of the the lowest digits occasionally without affecting the most-significant digits of your running total. Fib(n) grows close to exponentially; faster than any polynomial function.
For example, an Extreme Fibonacci code-golf question was to print the first 1000 digits of Fib(1 billion)
with a program that could actually finish in a reasonable amount of time. One Python2 answer from @AndersKaseorg used this code:
## golfed for minimum source-code size in bytes, not readability or performance
a,b=0,1
i=1e9
while i:
a,b=b,a+b;i-=1
if a>>3360:a/=10;b/=10
print a
# prints first 1000 digits of Fib(1**9),
# plus some (possibly wrong) extra trailing digits, as allowed by that question
which discards the low decimal digit of a
and b
if a > 2 ** 3360
. That's a 1012 digit number, so this keeps at least 1012 significant digits. (And slightly more in b
which is the larger of the 2).
For your case, you only care about the magnitude, so basically 1 significant digit of precision. You probably only have to keep about 12 or 13 significant digits to make sure the leading significant digit is always correct and doesn't grow too soon or too late. Maybe fewer; you might get away with keeping your running totals small enough to fit into 32-bit integers. Although I think Python on 64-bit machines will use 64-bit integers.
For your case, you do care about how many total digits there are. So you need to count how many times you truncate.
For efficiency, you probably want to set a higher truncation threshold and divide by 100 or 1000 so you don't have to do as many divisions. You might also be able to bit-shift (divide by a power of 2) instead of dividing by 10, if handle your final threshold appropriately, but that's trickier.
(That Python version takes about 12.5 minutes on a 4.4GHz Skylake x86-64 with Arch Linux CPython 2.7. My hand-written asm answer on the same question takes about 70 seconds by using base-10^9 extended precision, making it efficient to discard groups of 9 decimal digits.)
You can also unroll the loop so you only check for truncation every few additions because compare isn't free either. Perhaps have an efficient main loop that stops one or two orders of magnitude below the target digit-count, then go one step at a time without further truncation.
Working out the implementation details is left as an exercise for the reader (because the most efficient solution for large n is the closed-form FP math version). Keeping the numbers small should make the run time scale linearly with n
, instead of having each addition take longer as the numbers get larger.