An Integer Formula For Fibonacci Numbers
April 26, 2016
Here is a Scheme version that uses the bitwise operators in R6RS:
(define (fib n) (bitwise-and (quotient (ash 4 (* n (+ 3 n))) (- (ash 4 (* 2 n)) (ash 2 n) 1)) (- (ash 2 n) 1)))
> (map fib (range 25))
(0 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584
4181 6765 10946 17711 28657 46368 75025)
You can run the program at http://ideone.com/phPnOi, where you will also see the range
function as well as the bitwise operators if your Scheme doesn’t provide them. Astonishing.
I wondered if that would show up. Nice piece by Paul Hankin. Here’s a base 10 version, generalized a bit so we can start with different base values, a and b, and it’s more interesting, I think, to show the whole number computed, which contains a complete initial segment of the series. The
int(...)
expression is attempting to calculate how many digits are needed for each value, I haven’t formally verified it & I suspect a tighter bound is possible, but it seems about right:Here’s a more or less literal translation to Haskell. To make it look more like the Python version we locally define an operator for left shift. It’s left associative (the l in infixl) and has a precedence less than that of addition, so we don’t need to add extra parentheses.