Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
CoffeeScript Javascript Fast Fibonacci
Author: Jason Giedymin <jasong _a_t_ apache -dot- org>
This CoffeeScript Javascript Fast Fibonacci code is
based on the python code from Robin Houston's blog.
See below links.
A few things I want to introduce in time are implementions of
Newtonian, Burnikel / Ziegler, and Binet's algorithms on top
of a Big Number framework.
- BZ and Newton mods.
- Timing
Cool Links:
fib_bits = (n) ->
#Represent an integer as an array of binary digits.
bits = []
while n > 0
[n, bit] = divmodBasic(n, 2)
return bits.reverse()
fibFast = (n) ->
#Fast Fibonacci
if n < 0
console.log "Choose an number >= 0"
[a, b, c] = [1, 0, 1]
for bit in fib_bits(n)
if bit
[a, b] = [(a+c)*b, b*b + c*c]
[a, b] = [a*a + b*b, (a+c)*b]
c = a + b
return b
divmodBasic = (x, y) ->
Absolutely nothing special here. Maybe later versions will be Newtonian or
Burnikel / Ziegler _if_ possible...
return [(q = Math.floor(x/y)), (r = if x < y then x else x % y)]
start = (new Date).getTime();
calc_value = fibFast(MAXIMUM_JS_FIB_N)
diff = (new Date).getTime() - start;
console.log("[#{calc_value}] took #{diff} ms.")

This comment has been minimized.

Copy link
Owner Author

@JasonGiedymin JasonGiedymin commented Oct 12, 2011

Previous versions of this app had weird formatting. Blame Cygwin, fixed on my Mac. ;-)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.