<div dir="ltr"><br><br>On Saturday, May 7, 2016 at 12:59:10 AM UTC-5, Michael Litchard wrote:<blockquote class="gmail_quote" style="margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir="ltr"><div>Thanks for your response Erik. It appears I have not articulated my question well enough.<br></div>When p is odd, why is the return value <br><pre><span>(</span>f<span>*</span><span>(</span>f<span>+</span><span>2</span><span>*</span>g<span>)</span><span>,</span> f<span>^</span><span>2</span> <span>+</span> g<span>^</span><span>2</span><span>)<br></span></pre><pre><span>as opposed to the return value of<br><br></span><span>(</span>f<span>^</span><span>2</span><span>+</span>g<span>^</span><span>2</span><span>,</span> g<span>*</span><span>(</span><span>2</span><span>*</span>f<span>-</span>g<span>)</span><span>)<br><br></span></pre><pre><span>What is it about the boolean value that requires two entirely seperate things to be done?<br></span></pre></div></blockquote><div><br></div><div>The algorithm is based on the following Fibonacci identities (which hopefully I've recited correctly):</div><div><br></div><div> F_{2n} = F_n^2 + F_{n+1}^2</div><div> F_{2n+1) = F_{n+1}*(2*F_n + F_{n+1})</div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><blockquote class="gmail_quote" style="margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir="ltr"><pre><span></span></pre></div><div><br><div class="gmail_quote">On Fri, May 6, 2016 at 7:38 PM, Erik Rantapaa <span dir="ltr"><<a href="javascript:" target="_blank" gdf-obfuscated-mailto="Qm8co6sUCQAJ" rel="nofollow" onmousedown="this.href='javascript:';return true;" onclick="this.href='javascript:';return true;">eran...@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><br><br>On Friday, May 6, 2016 at 6:46:26 PM UTC-5, Michael Litchard wrote:<blockquote class="gmail_quote" style="margin:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div>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: <br><a href="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" rel="nofollow" target="_blank" onmousedown="this.href='https://www.google.com/url?q\x3dhttps%3A%2F%2Fwiki.haskell.org%2FThe_Fibonacci_sequence%23Fastest_Fib_in_the_West\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNFzix5dbPVZ36_StXEF6yTYuaAg4w';return true;" onclick="this.href='https://www.google.com/url?q\x3dhttps%3A%2F%2Fwiki.haskell.org%2FThe_Fibonacci_sequence%23Fastest_Fib_in_the_West\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNFzix5dbPVZ36_StXEF6yTYuaAg4w';return true;">https://wiki.haskell.org/The_<wbr>Fibonacci_sequence#Fastest_<wbr>Fib_in_the_West</a><br><br></div>thanks to this guy:<br><a href="https://groups.google.com/forum/#!topic/haskell-cafe/HUgbAUCvCp4" rel="nofollow" target="_blank" onmousedown="this.href='https://groups.google.com/forum/#!topic/haskell-cafe/HUgbAUCvCp4';return true;" onclick="this.href='https://groups.google.com/forum/#!topic/haskell-cafe/HUgbAUCvCp4';return true;">https://groups.google.com/<wbr>forum/#!topic/haskell-cafe/<wbr>HUgbAUCvCp4</a><br><br></div>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:<br><br><pre><span>fib'</span> <span>(</span>f<span>,</span> g<span>)</span> p
<span>|</span> p <span>=</span> <span>(</span>f<span>*</span><span>(</span>f<span>+</span><span>2</span><span>*</span>g<span>)</span><span>,</span> f<span>^</span><span>2</span> <span>+</span> g<span>^</span><span>2</span><span>)</span>
<span>|</span> <span>otherwise</span> <span>=</span> <span>(</span>f<span>^</span><span>2</span><span>+</span>g<span>^</span><span>2</span><span>,</span> g<span>*</span><span>(</span><span>2</span><span>*</span>f<span>-</span>g<span>)</span><span>)<br><br>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.<br></span></pre></div></blockquote><div><br></div></div></div><div>Clearly `p` is a Bool, and it comes from the expression:</div><div><br></div><div> map (toEnum . fromIntegral) $ unfoldl divs n</div><div><br></div><div>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`.</div><div><br></div></div></blockquote></div><br></div>
</blockquote></div>