<story><title>&quot;The worst algorithm in the world?&quot;</title><url>http://bosker.wordpress.com/2011/04/29/the-worst-algorithm-in-the-world/</url></story><parent_chain><item><author>stralep</author><text>Actually, you need just Z ring enriched (if this is right word) with sqrt(5). So instead of one float, you use pair of integers of arbitrary precision. So&lt;p&gt;(a,b)+(c,d) = (a+c,b+d)&lt;p&gt;(a,b)/sqrt(5) = (b,a/5)&lt;p&gt;(a,b)&lt;i&gt;&lt;/i&gt;(c,d) = (a&lt;i&gt;&lt;/i&gt;c+5&lt;i&gt;&lt;/i&gt;b&lt;i&gt;&lt;/i&gt;d,a&lt;i&gt;&lt;/i&gt;d+b&lt;i&gt;&lt;/i&gt;c)&lt;p&gt;2phi = (1,1)&lt;p&gt;F(n) = (2phi^n - (2-2phi)^n)/(2^n*sqrt(5))&lt;p&gt;[edit] As ot said, the right word is &quot;extended&quot;</text></item><item><author>mynegation</author><text>Very good demonstration of subsequent improvements of a naive algorithm. To me that was somewhat depreciated by the fact that you can actually calculate n-the Fibonacci number using Binet&apos;s closed form formula (&lt;a href=&quot;http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression&quot; rel=&quot;nofollow&quot;&gt;http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex...&lt;/a&gt;). You will need arbitrary precision arithmetic starting with certain &apos;n&apos; though, as IEEE 754 will not give you correct result.</text></item></parent_chain><comment><author>ot</author><text>&amp;#62;  Z ring enriched (if this is right word) with sqrt(5)&lt;p&gt;I think &quot;extended&quot; is the right word (see &lt;a href=&quot;http://en.wikipedia.org/wiki/Ring_extension&quot; rel=&quot;nofollow&quot;&gt;http://en.wikipedia.org/wiki/Ring_extension&lt;/a&gt;)&lt;p&gt;It is commonly denoted as Z[sqrt(5)]</text></comment>
<story><title>&quot;The worst algorithm in the world?&quot;</title><url>http://bosker.wordpress.com/2011/04/29/the-worst-algorithm-in-the-world/</url></story><parent_chain><item><author>stralep</author><text>Actually, you need just Z ring enriched (if this is right word) with sqrt(5). So instead of one float, you use pair of integers of arbitrary precision. So&lt;p&gt;(a,b)+(c,d) = (a+c,b+d)&lt;p&gt;(a,b)/sqrt(5) = (b,a/5)&lt;p&gt;(a,b)&lt;i&gt;&lt;/i&gt;(c,d) = (a&lt;i&gt;&lt;/i&gt;c+5&lt;i&gt;&lt;/i&gt;b&lt;i&gt;&lt;/i&gt;d,a&lt;i&gt;&lt;/i&gt;d+b&lt;i&gt;&lt;/i&gt;c)&lt;p&gt;2phi = (1,1)&lt;p&gt;F(n) = (2phi^n - (2-2phi)^n)/(2^n*sqrt(5))&lt;p&gt;[edit] As ot said, the right word is &quot;extended&quot;</text></item><item><author>mynegation</author><text>Very good demonstration of subsequent improvements of a naive algorithm. To me that was somewhat depreciated by the fact that you can actually calculate n-the Fibonacci number using Binet&apos;s closed form formula (&lt;a href=&quot;http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression&quot; rel=&quot;nofollow&quot;&gt;http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_ex...&lt;/a&gt;). You will need arbitrary precision arithmetic starting with certain &apos;n&apos; though, as IEEE 754 will not give you correct result.</text></item></parent_chain><comment><author>vog</author><text>This is a great method! It avoids arbitrary floating point arithmetics[1] and thus makes it more comparable with the method presented in the article.&lt;p&gt;As far as I can see, this algorithm is very similar to the matrix operations of the article, at least in terms of complexity.&lt;p&gt;[1] Only the very last step might involve fp arithmetics, because you&apos;ll have to convert the result pair (x,y) back to x+y*sqrt(5). However, we already know that the result has to be an integer, so the its second part will always be 0, no fp arithmetics required.</text></comment>