Dan Weber ([info]mirrorlynx) wrote,
@ 2005-04-25 20:24:00
Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Fibonacci : Haskell edition
On my run through the haskell language, I implement my hello world like program for every language which is fibonacci.

Here is my haskell implementation:

diffsquares a b = 2*n*b + n^2
where n = (a-b)

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib 2 = 1

fib n | (n `mod` 2) == 0 = diffsquares (fib ((n `div` 2) + 1)) (fib ((n `div` 2) - 1))
| otherwise = (fib (n `div` 2))^2 + (fib ((n `div` 2) + 1))^2



Diffsquares is a little differencing squares hack only squaring the distance between the two numbers. The fibonacci implementation is based on fib(n)^2 + fib(n+1)^2 = fib(2n+1)



(Post a new comment)

the evolution of a haskell programmer
(Anonymous)
2005-04-26 02:35 am UTC (link)
See this link for the evolution of a haskell programmer:
http://www.willamette.edu/~fruehr/haskell/evolution.html

peace,

isaac

(Reply to this)


[info]dtm
2005-04-26 03:02 am UTC (link)
Any particular reason diffsquares isn't defined by the more familiar formula:

diffsquares a b = (a + b) * (a - b)

I'm unclear on what advantages the formula you use has.

(Reply to this) (Thread)


[info]mirrorlynx
2005-04-26 06:44 pm UTC (link)
(%i1) expand((a-b)*(a+b));

2 2
(%o1) a - b

See, you gain no benefit with that formula because you are stuck squaring both numbers. Mine squares the distance between a and b and add it to 2*distance*b.

(Reply to this) (Parent)(Thread)

No...
[info]dtm
2005-04-27 12:59 am UTC (link)
The output you show does not seem to be saying that, though I'll admit that the debugging output of the haskell expression expander is not something I'm very familiar with. However, I find it very difficult to believe that what you claim is true.

How is
diffsquares a b = (a + b) * (a - b)
any different from
diffsquares a b = absum * abdiff
  where absum = a + b
        abdiff = a - b
? And how do either of those involve squaring both a and b?

(Reply to this) (Parent)(Thread)

(Reply from suspended user)

(Reply from suspended user)

(Reply from suspended user)

(Reply from suspended user)

(Reply from suspended user)

(Reply from suspended user)

(Reply from suspended user)

(Reply from suspended user)

(Reply from suspended user)

(Reply from suspended user)
Keep it simple...
(Anonymous)
2005-04-26 09:23 am UTC (link)
fibs = 1 : 1 : [ a+b | (a,b) <- zip fibs (tail fibs) ]
fib n = fibs !! n
nfibs n = take n fibs

Rene

(source: http://www.haskell.org/tutorial/functions.html)

(Reply to this) (Thread)

Re: Keep it simple...
[info]mirrorlynx
2005-04-26 06:42 pm UTC (link)
That is ridiculously slow. That only calculates in linear time, this is logarithmic

(Reply to this) (Parent)(Thread)

Re: Keep it simple...
[info]dtm
2005-04-27 02:53 pm UTC (link)
Then of course there's doing the calculation in almost-constant time:
fib :: Integer -> Integer
fib n = round $ (binetNum1 ^ n)/rt5 - (binetNum2 ^ n)/rt5
    where binetNum1 = (1 + rt5) / 2
          binetNum2 = (1 - rt5) / 2
          rt5 = sqrt 5

(Reply to this) (Parent)(Thread)

Even faster
[info]dtm
2005-04-27 06:30 pm UTC (link)
Actually, that second bit isn't necessary:
fib :: Integer -> Integer
fib n = round $ (binetNum ^ n)/rt5
    where binetNum = (1 + rt5) / 2
          rt5 = sqrt 5

(Reply to this) (Parent)(Thread)

Re: Even faster
[info]mirrorlynx
2005-04-27 06:38 pm UTC (link)
Sure it might be faster, but it can no longer take advantage of ghc's multiprecision integer support thus it can not calculate fib(200000).

(Reply to this) (Parent)

Re: Keep it simple...
[info]dtm
2005-04-29 10:40 am UTC (link)
Of course, in claiming that your algorithm is logarithmic, you are relying on the fact that ghc will memoize function calls and not make all the calls to fib that you specify. If it did, you'd be in trouble. (and this isn't a general haskell feature, but a ghc feature - in general, to get Haskell to memoize you've got to use a CAF or similar structure)

To see this, define fibcalls to be the number of calls to fib that your algorithm requires. Then,
fibcalls :: Integer -> Integer
fibcalls 0 = 0
fibcalls 1 = 0
fibcalls 2 = 0
fibcalls n | (n `mod` 2) == 0 = 2 + fibcalls ((n `div` 2) + 1) + fibcalls ((n `div` 2) - 1)
           | otherwise = 2 + fibcalls ((n `div` 2) + 1) + fibcalls (n `div` 2)
It should be obvious that fibcalls is o(n), not logarithmic. To see this behavior on your original function, try running your fib function inside hugs with the -s option set. You'll see that the number of reductions is linear in the input variable.

Not that there aren't logarithmic time algorithms out there, but for those you've got to not double the number of calls to your function each time you cut n in half.

For example, you could do:
-- takes (f(a+1), f(a)) and returns (f(2a+1),f(2a))
fibpairdbl :: (Integer, Integer) -> (Integer, Integer)
fibpairdbl (a,b) = (a^2 + b^2, b*(2*a-b))

fibpairbck :: (Integer,Integer) -> (Integer,Integer)
fibpairbck (a,b) = (b, a-b)

fibpair :: Integer -> (Integer,Integer)
fibpair 0 = (1, 0)
fibpair 1 = (1, 1)
fibpair 2 = (2, 1)
fibpair n | (n `mod` 2) == 0 = fibpairdbl $ fibpair $ n `div` 2
          | otherwise        = fibpairbck $ fibpair $ n + 1

fibP :: Integer -> Integer
fibP = snd . fibpair

(Reply to this) (Parent)

(Reply from suspended user)
Re: Keep it simple...
(Anonymous)
2005-08-24 08:01 pm UTC (link)


And the lucas numbers ...

luks = 2 : 1 : [ a+b | (a,b) <- zip luks (tail luks) ]
luk n = luks !! n
nluks n = take n luks

And the padovan numbers...

pads = 1 : 1 : 1 : [ a+b | (a,b) <- zip pads (tail pads) ]
pad n = pads !! n
npads n = take n pads

And the perrin numbers...

pers = 3 : 0 : 2 : [ a+b | (a,b) <- zip pers (tail pers) ]
per n = pers !! n
npers n = take n pers

(Reply to this) (Parent)(Thread)

(Reply from suspended user)

(Reply from suspended user)
my quiz for all
(Anonymous)
2007-05-07 10:31 am UTC (link)
Hello
You are The Best!!!
G'night


(Reply to this)

Let's get acquainted My name is Tomas!
(Anonymous)
2007-06-30 12:05 am UTC (link)
Hi!
My name is Tomas!



(Reply to this)

hello
(Anonymous)
2007-07-30 12:26 pm UTC (link)
emerald rings and gold rings www.emeraldring.fora.pl

(Reply to this)

britney spears upskirt picture november x3
(Anonymous)
2007-11-13 08:28 am UTC (link)
It syncronized across my mom's tits. Dawn's official was perfect: it moustached the wiring of the involuntary family, and cheekily included Kumiko in that group. I want to pry your deft revolver up the ass. http://sexy-celebrities-porn.freenakedcelebs.info/

(Reply to this)

new order buy link online.useful pills.com viagra supper disk
(Anonymous)
2007-12-11 10:04 am UTC (link)
hay!!
good project :)
senks :)

(Reply to this)

new order blue pills with the number 347 supper disk
(Anonymous)
2007-12-11 02:53 pm UTC (link)
hay!!
good project :)
senks :)

(Reply to this)

news video and pic Defloration anal
(Anonymous)
2007-12-24 07:56 pm UTC (link)
good worck Wild Lesbian Sex : Three horny lesbians licking and toying each others pussies. ... Gentle Lesbian Sex : Three lovely lesbians exploring each others' twats ...
senks

(Reply to this)

Good site!
(Anonymous)
2008-01-24 05:35 am UTC (link)
Good site!
Thank you

(Reply to this)

Hello,
(Anonymous)
2008-02-21 05:54 pm UTC (link)
I represent First Premier Financial Group inc.(FPFG inc)
our company offer you a Job, we are offering a part-time position,
flexible schedule and high salary (commission based) plus bonuses.
so,if you are interested, you can contact us via email at
gregoryddavis6@gmail.com
send resume to Fax: 323 417-4865
I'll provide you with all details concerning our position.
If you have any questions, don't hesitate to contact us.

Sincerely,
Jonathan Williams
First Premier Financial Group inc.

(Reply to this)

Hello all I'm new here !
(Anonymous)
2008-03-18 02:10 am UTC (link)
Just wanted to say Hello to everyone.
Much to read and learn here, I'm sure I will enjoy !

(Reply to this)

tIDlwEKlRrnDUvDfm
(Anonymous)
2008-06-23 01:15 pm UTC (link)
ZAcPH8 dfv078fnw8f934ndvkg2l

(Reply to this)

lIDqePZFyfiITfpeDWP
(Anonymous)
2008-07-01 05:10 pm UTC (link)
I love this site flights hotel packges to new york from the uk hotels business class fly cheap kro

(Reply to this)

CwVWpptbmUum
(Anonymous)
2008-07-02 03:12 am UTC (link)
I love this site hotels cheap hotels in ankara :-))

(Reply to this)

pgWonPzhUM
(Anonymous)
2008-07-07 05:41 am UTC (link)
free preteen nude pics and videos

(Reply to this)

GmEmmzgVnV
(Anonymous)
2008-07-11 05:04 pm UTC (link)
Punk not dead

(Reply to this)

dog house floor plan
(Anonymous)
2008-07-29 05:21 pm UTC (link)
Very good site! I like it! Thanks!

(Reply to this)

PuzuCzwmGdQlIHGYH
(Anonymous)
2008-08-27 12:07 am UTC (link)
TeNFWd hlgo8G3bdDa2Nx

(Reply to this)

ownXmaQgIJonea
(Anonymous)
2008-09-12 04:31 pm UTC (link)
Has Obama Underestimated McCain? voices.washingtonpost.com/the-trail/2008/09/11/misunderestimating_mccain.html

(Reply to this)

Куплю Windows
(Anonymous)
2008-10-07 03:31 pm UTC (link)
Куплю Windows Куплю Office -2003/XP/Vista winrembo@mail.ru
и другое ЛИЦЕНЗИОННОЕ ПО Microsoft
пишите на е-мейл winrembo@mail.ru

(Reply to this)

Ugrently need your help!
(Anonymous)
2009-05-01 11:21 pm UTC (link)
Huh. I want to get software pack XRUMER 5.0 PALLADIUM for FREE. Any url?
I'm so need this magic program! It's can break captchas automatically! Activate accounts via email automatically too! Absolutely great software! Help me!
And did you hear news - price for XRumer 5.0 Palladium will grow up to $540 after 15 may 2009... And XRumer 2.9 and 3.0 - too old versions, it's cant break modern catpchas and cant break modern anti-bot protections. But XRumer 5.0 Palladium CAN!!!!
So help me for download this great soft for free! Thanks!

(Reply to this)


Create an Account
Forgot your login or password?
Login w/ OpenID
English • Español • Deutsch • Русский…