Sutton：I think we are now entering the era of human experience, because AI needs a source of data that grows and improves and changes as the agent becomes stronger, rather than static data sets, because as large as the Internet is, it's still a static data set

 Everything should be made as simple as possible, but no simpler”
-Albert Einstein

要真正领略计算机进行大数乘法的巧妙之处，可以从时间复杂度的角度衡量

 递归抽象子问题的卡拉楚巴算法

四次的做法，但其实也要几乎 n^1.91次量级，看似是无用只用，但这也才有了我们后面的三次做法

 递归乘法从四次减少到了三次 n^1.5次量级，递归抽象了相同子问题

a*c

b*d

(a+b)*(c+d)

 

伪代码实现思路

// 计算两个整数的最大值

int max(int a, int b) {

    return a > b? a : b;

}

// 分治实现乘法的函数

long long naive_mult(long long num1, long long num2)

{

    if (num1 < 2 && num2 < 2) {

        return num1 * num2; 

    }

    // 计算二进制位数（减 2 是去掉二进制表示开头的 "0b"）

    int len1 = std::to_string(num1).size(); 

    int len2 = std::to_string(num2).size(); 

    int n = max(len1, len2);

    int mid = n / 2; 

    long long a = num1 / (1LL << mid); 

    long long b = num1 % (1LL << mid); 

    long long c = num2 / (1LL << mid); 

    long long d = num2 % (1LL << mid); 

    long long ac = naive_mult(a, c);

    long long bd = naive_mult(b, d);

    long long ad = naive_mult(a, d);

    long long bc = naive_mult(b, c);

    long long ad_plus_bc = ad + bc;

    return (ac * (1LL << (mid * 2))) + (ad_plus_bc * (1LL << mid)) + bd;

}

可视化分析

应用 

eg. rsa加密