[ create a new paste ] login | about

Link: http://codepad.org/vU5b27DI    [ raw code | output | fork ]

Python, pasted on Jan 12:
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.'


Output:
1
All tests completed.


Create a new paste based on this one


Comments: