CoffeeScript 更快的 Fibonacci 算法

更快的 Fibonacci 算法

問題

你想計(jì)算出Fibonacci數(shù)列中的數(shù)值N ，但需迅速地算出結(jié)果。

解決方案

下面的方案（仍有需改進(jìn)的地方）最初在Robin Houston的博客上被提出來。

這里給出一些關(guān)于該算法和改進(jìn)方法的鏈接：

• http://bosker.wordpress.com/2011/04/29/the-worst-algorithm-in-the-world/
• http://www.math.rutgers.edu/~erowland/fibonacci
• http://jsfromhell.com/classes/bignumber
• http://www.math.rutgers.edu/~erowland/fibonacci
• http://bigintegers.blogspot.com/2010/11/square-division-power-square-root
• http://bugs.python.org/issue3451

以下的代碼來源于：https://gist.github.com/1032685

###
Author: Jason Giedymin <jasong _a_t_ apache -dot- org>
        http://www.jasongiedymin.com
        https://github.com/JasonGiedymin

CoffeeScript Javascript 的快速 Fibonacci 代碼是基于 Robin Houston 博客里的 python 代碼。
見下面的鏈接。

我要介紹一下 Newtonian，Burnikel / Ziegle 和Binet 關(guān)于大數(shù)目框架算法的實(shí)現(xiàn)。

Todo:
- https://github.com/substack/node-bigint
- BZ and Newton mods.
- Timing

###

MAXIMUM_JS_FIB_N = 1476

fib_bits = (n) ->
    #代表一個(gè)作為二進(jìn)制數(shù)字陣列的整數(shù)

    bits = []
    while n > 0
        [n, bit] = divmodBasic n, 2
        bits.push bit

    bits.reverse()
    return bits

fibFast = (n) ->
    #快速 Fibonacci

    if n < 0
        console.log "Choose an number >= 0"
        return

    [a, b, c] = [1, 0, 1]

    for bit in fib_bits n
        if bit
            [a, b] = [(a+c)*b, b*b + c*c]
        else
            [a, b] = [a*a + b*b, (a+c)*b]

        c = a + b
        return b

divmodNewton = (x, y) ->
    throw new Error "Method not yet implemented yet."

divmodBZ = () ->
    throw new Error "Method not yet implemented yet."

divmodBasic = (x, y) ->
    ###
   這里并沒有什么特別的。如果可能的話，也許以后的版本將是Newtonian 或者 Burnikel / Ziegler 的。
   ###

    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."