codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
def fib1(n): def fib_inner(n): '''Returns F[n] and L[n]''' if n == 0: return 0, 2 m = n >> 1 u, v = fib_inner(m) q = (n & 2) - 1 u, v = u*v, v*v + 2*q if (n & 1): u1 = (u + v) >> 1 return u1, 2*u + u1 return u, v m = n >> 1 u, v = fib_inner(m) if (n & 1): q = (n & 2) - 1 u1 = (u + v) >> 1 return v * u1 + q return u * v def fib2(n): def fib_inner(n): '''Returns F[n] and F[n+1]''' if n == 0: return 0, 1 m = n >> 1 u, v = fib_inner(m) q = (n & 2) - 1 if (n & 1): # L[m + 1] l = (2*u + v) return u * l - q, v * l # L[m] l = (2*v - u) return u * l, v * l + q m = n >> 1 u, v = fib_inner(m) # L[m] l = (2*v - u) if (n & 1): q = (n & 2) - 1 return v * l + q return u * l def fib3(n): def fib_inner(n): '''Returns L[n] and L[n+1]''' if n == 0: return 2, 1 m = n >> 1 u, v = fib_inner(m) q = (n & 2) - 1 if (n & 1): return u * v + q, v * v - 2*q return u * u + 2*q, u * v + q m = n >> 1 u, v = fib_inner(m) # F[m] f = (2*v - u) / 5 if (n & 1): q = (n & 2) - 1 return v * f - q return u * f def fib4(n): def fib_inner(n): '''Returns F[n] and L[n+1]''' if n == 0: return 0, 1 m = n >> 1 u, v = fib_inner(m) q = (n & 2) - 1 if (n & 1): return u * v - q, v * v - 2*q # L[m] l = 2*v - 5*u return u * l, v * l + q m = n >> 1 u, v = fib_inner(m) if (n & 1): q = (n & 2) - 1 return u * v - q # L[m] l = 2*v - 5*u return u * l def fib5(n): def fib_inner(n): '''Returns F[n+1] and L[n]''' if n == 0: return 1, 2 m = n >> 1 u, v = fib_inner(m) q = (n & 2) - 1 if (n & 1): # L[m + 1] v1 = 5*u - 2*v return u * v1, v * v1 + q return u * v + q, v * v + 2*q m = n >> 1 u, v = fib_inner(m) if (n & 1): q = (n & 2) - 1 return u*v + q # F[m] u1 = 2*u - v return u1 * v def fib6(n): def fib_inner(n): '''Returns F[n+1] and L[n+1]''' if n == 0: return 1, 1 m = n >> 1 u, v = fib_inner(m) q = (n & 2) - 1 if (n & 1): return u * v, v * v - 2*q # L[m] l = (5*u - v) >> 1 return u * l + q, v * l + q m = n >> 1 u, v = fib_inner(m) q = (n & 2) - 1 if (n & 1): # L[m] l = (5*u - v) >> 1 return u * l + q # L[m - 1] l = (3*v - 5*u) >> 1 return u * l - q a, b = 0, 1 for n in range(1000): assert(a == fib1(n)) assert(a == fib2(n)) assert(a == fib3(n)) assert(a == fib4(n)) assert(a == fib5(n)) assert(a == fib6(n)) a, b = b, a + b print 'All tests completed.'
Private
[
?
]
Run code
Submit