StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Yes, there's a better way. This is a <code>log(n)</code> tested and very efficient way for calculating a value of Fibonacci with arbitrary precision, given a positive integer as input. The algorithm was adapted from a solution to <a href="https://mitpress.mit.edu/sicp/full-text/book/book.html" rel="noreferrer">SICP</a>'s <a href="https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.4" rel="noreferrer">exercise 1.19</a>:</p> <pre><code>public static BigInteger fibonacci(int n) { int count = n; BigInteger tmpA, tmpP; BigInteger a = BigInteger.ONE; BigInteger b = BigInteger.ZERO; BigInteger p = BigInteger.ZERO; BigInteger q = BigInteger.ONE; BigInteger two = new BigInteger("2"); while (count != 0) { if ((count & 1) == 0) { tmpP = p.multiply(p).add(q.multiply(q)); q = two.multiply(p.multiply(q)).add(q.multiply(q)); p = tmpP; count >>= 1; } else { tmpA = b.multiply(q).add(a.multiply(q).add(a.multiply(p))); b = b.multiply(p).add(a.multiply(q)); a = tmpA; count--; } } return b; } </code></pre> <p>In the linked chapter of the book there's an explanation of how it works (scroll down to exercise 1.19), and it's stated that:</p> <blockquote> <p>This is a clever algorithm for computing the Fibonacci numbers in a logarithmic number of steps ... This exercise was suggested by Joe Stoy, based on an example in Kaldewaij, Anne. 1990. <em>Programming: The Derivation of Algorithms</em>.</p> </blockquote> <p>Of course, if the same values need to be calculated over and over again, further performance gains can be achieved by <a href="https://en.wikipedia.org/wiki/Memoization" rel="noreferrer">memoizing</a> results that have been already calculated, for instance using a map for storing previous values.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload