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...@gmail.com> wrote:
On Friday, May 6, 2016 at 6:46:26 PM UTC-5, Michael Litchard wrote:
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`.