[Tutor] fib (was recursive factoring)

[mikalzet@libero.it]

On Fri, 18 Jan 2002, Lloyd Hugh Allen wrote:

> Of course, an even faster way to compute fibs would be to use
>
> import math
> r = (1 + math.sqrt(5))/2
> s = (1 - math.sqrt(5))/2
> def fib(n):
>     return long((r**n - s**n)/math.sqrt(5))
>
> if only Python had infinite precision. This method should break about
> where floats run out of digits.

Which proves one thing: to make a good program to solve a problem it is
necessary first to have a good knowledge of how to solve the problem
normally ... I didn't have any idea of how to solve fibs mathematically.
(Nor do I have any idea of what they may be useful for      :-)    )

I also didn't realize when we started speaking about factoring that we
were actually entering such dangerous ground (encryption and so forth).
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 ?

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 ?

-- 
Michele Alzetta