快速幂

快速幂的核心是：减少乘法次数。

问题：计算 2的10000次方

普通方法：answer = 1，循环10000次 answer*=2，得到结果answer。

快速幂：10000化为二进制=0b10011100010000；从-1位起，因数=2；从-2位起到第1位执行循环，判定-n位是否为1，为1则answer*=因数；因数*=因数。具体详见代码~

#coding=utf-8
import time

def normal_power(a,x):
    answer = 1
    i = 0
    while i < x:
        answer*=a
        i+=1

def quick_power(a,x):
    answer = 1
    base = a
    while x != 0:
        if x & 1 == 1: # 代表二进制x最后一位是1
            answer*=base
        base *= base
        x >>= 1

if __name__ == '__main__':
    print(str(time.strftime("%Y-%m-%d %H:%M:%S", time.localtime())))
    for i in range(1,100000):
        quick_power(2, 10000)
    print(str(time.strftime("%Y-%m-%d %H:%M:%S", time.localtime())))

    for i in range(1,10000):
        normal_power(2, 10000)
    print(str(time.strftime("%Y-%m-%d %H:%M:%S", time.localtime())))

这里执行了10w次快速幂，和1w次普通幂运算，运算时间相差巨大。结果如下：

2018-09-18 17:02:01
2018-09-18 17:02:07
2018-09-18 17:02:39

斐波那契数列

问题：兔子生产；爬楼梯，一次能爬1或2步，能有多少爬法；等……

传统方法：F(n) = F(n-1) + F(n-2)，使用递归，或者普通循环，逐层运算。

改进方法：
基于如下公式

运用快速幂的操作

def normal_fib(n):
    if n ==1 or n==2:
        return 1
    else:
        a = 1
        b = 1

        while n >= 3:
            a,b = a+b,a
            n-=1
        return a

def quick_fib(n):
    n-=1

    ta, tb, tc, td = 1, 1, 1, 0
    a,b,c,d = 1,1,1,0

    while n != 0:
        if n & 1 == 1:  # 代表二进制x最后一位是1
            ta,tb,tc,td = ta*a+tb*c,ta*b+tb*d,tc*a+td*c,tc*b+td*d
        a, b, c, d = a * a + b * c, a * b + b * d, c * a + d * c, c * b + d * d
        n >>= 1
    return tb

if __name__ == '__main__':
    print(str(time.strftime("%Y-%m-%d %H:%M:%S", time.localtime())))
    for i in range(1,10000):
        quick_fib(10000)
    print(str(time.strftime("%Y-%m-%d %H:%M:%S", time.localtime())))

    for i in range(1,10000):
        normal_fib(10000)
    print(str(time.strftime("%Y-%m-%d %H:%M:%S", time.localtime())))

这里分别执行了1w次fib(10000)，时间分别为：3s，21s。差距显著。

2018-09-18 19:48:07
2018-09-18 19:48:10
2018-09-18 19:48:31

斐波那契数列基础

直接递归，效率最低，因为会不断算相同的数据，所以可以改进。

1. 由底自上

a = 1, b=1, c=a+b, a=b, b=c
按的顺序计算，不重复，效率为O(n)

2. 通式

如果依次计算，效率为O(n)，但用递归求平方，可减至O(lgn)，但运算中出现根号，会有精度问题。

3. 矩阵乘方

虽然乘方效率很低，但若矩阵维数在较小值上，矩阵乘方与一般乘法效率相似，在一个数量级。
由于数列是二阶递推数列，故存在二维方阵，使得

代入n项斐波那契，可得

故有

即

求该矩阵A的n次方，效率为O(lgn)，且无浮点误差。

矩阵乘法优化

矩阵乘法优化，不想打字了，直接上图啦。

附：知识补充

位运算操作 >：将整数二进制后的最后一位略去，

位与操作 &： x & 1 是将x的二进制 1000101010 与 000001，用来判定最后一位是0还是1

python中的时间函数：

import time 
print(str(time.strftime("%Y-%m-%d %H:%M:%S", time.localtime())))

python文件加上 #coding=utf-8 使中文正常显示