4 ms·
At first glance, the given integer formula is worse regarding arbitrary precision. The first bracket term is (4 << n*(3+n)) That is shifting 4 by n square
by tspiteri 10y ago
At first glance, the given integer formula is worse regarding arbitrary precision. The first bracket term is
(4 << n*(3+n))
That is shifting 4 by n squared digits to the left, requiring more than n^2 binary digits.
I think calling this an integer formula is misleading, since in computing algorithms, by integers we normally understand the basic integer supported by an ALU. This formula, while dealing with integers in the mathematical sense, deals with arbitrary precision (or bignum, or whatever you call it) in the computing sense.
- hnkain 10y agoI'm the author of the blog post. You're right, it requires n^2 binary digits (and I mention this at the end of the article). The formula isn't, and isn't meant to be, a good way to find Fibonacci numbers -- it's more of a fun curiosity.