[Haskell-cafe] The maths behind the Fastest Fibb In The West.

[Erik Rantapaa]

On Saturday, May 7, 2016 at 12:59:10 AM UTC-5, Michael Litchard wrote:
>
> Thanks for your response Erik. It appears I have not articulated my 
> question well enough.
> When p is odd, why is the return value 
>
> (f*(f+2*g), f^2 + g^2)
>
> as opposed to the return value of
>
> (f^2+g^2,   g*(2*f-g))
>
> What is it about the boolean value that requires two entirely seperate things to be done?
>
>
The algorithm is based on the following Fibonacci identities (which 
hopefully I've recited correctly):

    F_{2n} = F_n^2 + F_{n+1}^2
    F_{2n+1) = F_{n+1}*(2*F_n + F_{n+1})

and there is a similar formula for F_{2n-1} in terms of F_n and F_{n+1}. So 
given a pair of consecutive Fibonacci numbers, (F_n, F_{n+1}), we can use 
these formulas to compute another pair of consecutive Fibonacci's, either 
(F_{2n-1}, F_2n) or (F_2n, F_{2n+1}). This is what fib'  is doing -- f and 
g are a pair of consecutive Fibonacci's and it returns one of these new 
pairs based on whatever p is.

So, starting from the pair (F_1, F_2) we have to figure out the sequence of 
p's which will get us to our target F_n, and that appears to be related to 
 the binary representation of n.


> On Fri, May 6, 2016 at 7:38 PM, Erik Rantapaa <eran... at gmail.com 
> <javascript:>> wrote:
>
>>
>>
>> On Friday, May 6, 2016 at 6:46:26 PM UTC-5, Michael Litchard wrote:
>>>
>>> I've been working on a project that needs a good fibonacci generator, 
>>> and I'm to the point where can now improve upon this one: 
>>> https://wiki.haskell.org/The_Fibonacci_sequence#Fastest_Fib_in_the_West 
>>> <https://www.google.com/url?q=https%3A%2F%2Fwiki.haskell.org%2FThe_Fibonacci_sequence%23Fastest_Fib_in_the_West&sa=D&sntz=1&usg=AFQjCNFzix5dbPVZ36_StXEF6yTYuaAg4w>
>>>
>>> thanks to this guy:
>>> https://groups.google.com/forum/#!topic/haskell-cafe/HUgbAUCvCp4
>>>
>>> He suggested breaking up a guard into two diffeent functions, which I 
>>> can do, but I don't know what to call them because I don't know why the 
>>> operations are different. I'm referring to this section:
>>>
>>> fib' (f, g) p
>>>             | p         = (f*(f+2*g), f^2 + g^2)
>>>             | otherwise = (f^2+g^2,   g*(2*f-g))
>>>
>>> I'd like to know the reason why each guard does two entirely different things, so I know what to call the functions when I seperate them out.
>>>
>>>
>> Clearly `p` is a Bool, and it comes from the expression:
>>
>>      map (toEnum . fromIntegral) $ unfoldl divs n
>>
>> What's going on in `toEnum . fromIntegral` is that a remainder (either 0 
>> or 1 - it blows up for anything else) is being converted to a Bool, with 0 
>> mapping to False and 1 mapping to True. So `isOdd` would be a more 
>> descriptive name for `p`.
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20160507/02870267/attachment.html>