[Haskell-cafe] Floating phi, round and even Fibonnaci numbers

[Brian L. Troutwine]

Hello Robert,

Thanks for the comments. The lazy list with Double phi embedded does indeed 
begin to deviate, at the 81st Fibonacci number, if I'm not mistaken. Another 
fellow in this thread calculated the deviation points for Double, Float and 
CReal.

By way of further explanation, I'm writing up various approaches and solutions 
to the problems posed at Project Euler, discussing the various defects to 
each approach, comparing the runtimes of solutions and, hopefully, deriving 
interesting tidbits of math along the way. The project was begun to improve 
my Haskell ability by exercising it in as many ways on a single idea as 
possible. I'd not thought of the algorithm you pointed out in SICP and will 
now happily include it. Thanks.

Brian

On Wednesday 11 July 2007 07:00:05 you wrote:
> Brian,
>
> I am also a Haskell newbie, and unfortunately can not answer your type
> question, but wish to make a 'side comment'. The use of a floating point
> phi to calculate Fibonacci numbers makes me a bit nervous. In 'Structure
> and Interpretation of Computer Programs' 2n Edition Exercise 1.19 there is
> an algorithm for calculating the n'th  Fibonacci number in order of log n
> steps. Take a look at:
>
> http://mitpress.mit.edu/sicp/full-text/sicp/book/node18.html
>
> I would use the type Integer, with this algorithm, for arbitrary precision
> Fibonacci numbers. My concern is that your lazy list will start to deviate
> at some point from Fibonacci numbers because of the floating point
> calculations. Comments welcome, and I look forward to seeing the experts
> answer your type question.
>
> Best Regards,
> Robert
>
> On Wednesday 11 July 2007 05:11, Brian L. Troutwine wrote:
> > I'm rather new to Haskell and need, in typical newbie style,
> > a bit of help understanding the type system.
> >
> > The Nth even Fibonacci number, EF(n) can be defined by the recursive
> > relation EF(0) = 2, EF(n) = [EF(n-1) * (phi**3)], where phi is the
> > golden ratio and [] is the nearest integer function. An infinite lazy
> > list of this sequence would be nice to have for my Project Euler, er,
> > project. Defining phi thusly,
> >
> > > phi :: (Floating t) => t
> > > phi = (1+sqrt(5))/2
> >
> > With phi in place, if I understood types properly (and if I understand
> > iterate correctly as I think), the lazy list should be a relatively
> > quick matter.
> >
> > > even_fibs :: (Num t) => [t]
> > > even_fibs = iterate (\x -> round(x * (phi**3))) 2
> >
> > Dynamically typed even_fibs :: (Floating t, Integral t, RealFrac t) =>
> > [t], assuming I pass -fno-monomorphism-restriction to ghci. That's not
> > at all the type I assumed even_fibs would take, as can be seen from
> > above. So, I went on a bit of sojourn. Having seen the sights of the
> > Haskell Report section 6.4, the marvels of the references cited in the
> > wiki's article on the monomorphism restriction and the Gentle
> > Introduction's chapter 10 I must say I'm rather more terribly confused
> > than when I started out, possibly.
> >
> > Can someone explain where my type statements have gone wrong?
> > _______________________________________________
> > Haskell-Cafe mailing list
> > Haskell-Cafe at haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell-cafe