Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # -*- coding: utf-8 -*-
- import time, random
- class MatrixFibonacci:
- A = [[1, 1],
- [1, 0]]
- def __init__(self):
- self.__memo = {}
- # умножение матриц
- # ожидаются матрицы в виде списка список размером 2x2
- def __multiply_matrices(self, M1, M2):
- a11 = M1[0][0]*M2[0][0] + M1[0][1]*M2[1][0]
- a12 = M1[0][0]*M2[0][1] + M1[0][1]*M2[1][1]
- a21 = M1[1][0]*M2[0][0] + M1[1][1]*M2[1][0]
- a22 = M1[1][0]*M2[0][1] + M1[1][1]*M2[1][1]
- r = [[a11, a12], [a21, a22]]
- return r
- # возведение матрицы в степень
- # ожидается p равная степени двойки
- def __get_matrix_power(self, M, p):
- if p == 1:
- return M
- if p in self.__memo:
- return self.__memo[p]
- K = self.__get_matrix_power(M, int(p/2))
- R = self.__multiply_matrices(K, K)
- self.__memo[p] = R
- return R
- # получение n-го числа Фибоначчи
- # в качестве n ожидается неотрицательное целое число
- def get_number(self, n):
- if n == 0:
- return 0
- if n == 1:
- return 1
- # разложение переданной степени на степени, равные степени двойки
- # т.е. 62 = 2^5 + 2^4 + 2^3 + 2^2 + 2^0 = 32 + 16 + 8 + 4 + 1
- powers = [ int(pow(2, b)) for (b, d) in enumerate(reversed(bin(n-1)[2:])) if d == '1' ]
- # тоже самое, но менее pythonic: http://pastebin.com/h8cKDkHX
- matrices = [ self.__get_matrix_power(MatrixFibonacci.A, p) for p in powers ]
- while len(matrices) > 1:
- M1 = matrices.pop()
- M2 = matrices.pop()
- R = self.__multiply_matrices(M1, M2)
- matrices.append(R)
- return matrices[0][0][0]
- class IterationFibonacci:
- def __init__(self):
- pass
- # получение n-го числа Фибоначчи
- # в качестве n ожидается неотрицательное целое число
- def get_number(self, n):
- if n == 0:
- return 0
- a = 0
- b = 1
- c = 1
- for i in range(n-1):
- c = a + b
- a = b
- b = c
- return c
- import time, sys
- from math import log, floor
- # A fast algorithm for computing large Fibonacci numbers
- # http://www.ii.uni.wroc.pl/~lorys/IPL/article75-6-1.pdf
- # used for http://weblogs.java.net/blog/kabutz/archive/2012/02/24/fibonacci-1000000000-challenge
- def fib(n):
- if n == 0:
- return n
- F, L, sign, exp = 1, 1, -2, int(floor(log (n,2)))
- mask = 2**exp
- for i in xrange (exp - 1):
- mask = mask >> 1
- F2 = F**2
- FL2 = (F + L)**2
- F = ((FL2 - 6*F2) >> 1) - sign
- if n & mask:
- temp = (FL2 >> 2 ) + F2
- L = temp + (F << 1)
- F = temp
- else:
- L = 5*F2 + sign
- sign = -2 if n & mask else 2
- if n & (mask >> 1) == 0:
- return F * L
- else:
- return ((F + L) >> 1) * L - (sign >> 1)
- def benchmark():
- N = 1000000
- t = time.time()
- mfib = MatrixFibonacci()
- m = mfib.get_number(N)
- print "Time (s): %f" % (time.time()-t)
- s = time.time()
- fib(N)
- print("Time (s): %f" % (time.time() - s))
- benchmark()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement