[Tutor] fib (was recursive factoring)

[Kirby Urner]

>
>You mean to say that if tomorrow a mathematician dreams
>up a quick and easy factoring solution for huge numbers ...
>all the gpg and ssl etc. becomes a pack of useless
>byte-exchanging software ?

Yes.  Anything RSA-based that is.  I think ssl qualifies.
You can bet many talented math heads have cracked their
nut on this problem.  Fame and glory awaits the solver.
In the meantime, lots of good math has stemmed from the
research, as a side-effect.

>What is the limit for floats in python anyway ? I've seen that long
>integers are very long indeed ... are floats as long or not ?

Floats occupy a fixed number of bits, some of which belong
to a mantissa, some to the exponent, and then there's
the sign.  No way to use floats to get good number-
theoretic results involving long strings of digits.

There are some Python modules that do something like
infinite precision floats.  Harder to use than long integers
but possible.

Here's another fib program that computes the nth fib:

   def fib(n):
         a,b = 0,1
         while n:
             a,b = b,a+b
             n -= 1
         return a

   >>> [fib(i) for i in range(10)]
   [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

In Python 2.2, you don't have to start out with a,b long
-- it goes to long automatically, when a,b start getting
big.  The 10,000th fib is well within the capabilities
of this program.  No method with ordinary floats'll do
it.

Kirby