On Tue, 6 Nov 2007 [EMAIL PROTECTED] wrote:
However, this is still an O(log n) algorithm, because that's the
complexity of raising-to-the-power-of. And it's slower than the
simpler integer-only algorithms.
You mean computing the matrix power of
/1 1\
\0 1/
?
When discussing the complexity of fib don't forget that integer
operations for bignums are no longer constant time.
-- Lennart
On Nov 7, 2007 6:55 AM, Henning Thielemann
[EMAIL PROTECTED] wrote:
On Tue, 6 Nov 2007 [EMAIL PROTECTED] wrote:
However, this is still an O(log n) algorithm,
There are some nice formulae for the Fibonacci numbers that relate f_m
to values f_n where n is around m/2. This leads to a tolerably fast
recursive algorithm.
Here's a complete implementation:
fib 0 = 0
fib 1 = 1
fib 2 = 1
fib m | even m = let n = m `div` 2 in fib n*(fib (n-1)+fib (n+1))
Hi,
sorry my english is not the best :(
2007/11/5, gitulyar [EMAIL PROTECTED]:
Please help me. I'm new in Haskell programming, but wrote some things in
Scheme. I make so function:
fib 1 = 1
fib 2 = 2
fib n = fib (n-1) + fib (n-2)
And when I call fib 30 it works about 5 seconds. As for me
G'day all.
I wrote:
However, this is still an O(log n) algorithm, because that's the
complexity of raising-to-the-power-of. And it's slower than the
simpler integer-only algorithms.
Quoting Henning Thielemann [EMAIL PROTECTED]:
You mean computing the matrix power of
/1 1\
\0 1/
?
I
G'day all.
Quoting [EMAIL PROTECTED]:
There is one solution missing there (unless I skipped it) fib
n=((1+s)/2)^n-((1-s)/2)^n)/s where s=sqrt 5 If some of you complain
that this is real, not integer, please remember that
Leonardo of Pisa thought of applying this to rabbits. Well, rabbits are
For a more efficient Haskell implementation of fibonacci numbers, try
fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
fib n = fibs !! n
This is uglier, but just to keep using just plain recursion:
fib = fib' 0 1
where
fib' a b 0 = a
fib' a b n = fib' b (a+b) (n-1)
Brent Yorgey wrote:
On Nov 5, 2007 5:22 PM, gitulyar [EMAIL PROTECTED]
mailto:[EMAIL PROTECTED] wrote:
Please help me. I'm new in Haskell programming, but wrote some things in
Scheme. I make so function:
fib 1 = 1
fib 2 = 2
fib n = fib (n-1) + fib (n-2)
And when I
Andrew Bromage:
G'day all.
(MIS)Quoting Dan Weston:
fib00 = 0
fib01 = 1
fib02 = fib00 + fib01
[deletia]
fib7698760 = fib7698759 + fib7698758
This is why we don't pay programmers by LOC.
...
Incidentally, we've been here before. Check out this thread:
I assume you meant
fib n=(((1+s)/2)^n-((1-s)/2)^n)/s where s=sqrt 5
Your solution starts to diverge from reality at n = 76:
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
Prelude let n = 76 in fibs !! n - round (fib n)
1
[EMAIL PROTECTED] wrote:
Andrew Bromage:
G'day all.
(MIS)Quoting Dan
10 matches
Mail list logo
