2-4:
1. If m is very small, that is, M / 10 <= _INT64, N * m is a high-absorbent single-degree problem, multiplied a digit of N of N, and records M * i (1 <= The result of i <= 9), then the left shift is added.
2. If M is also high-precision, divide N into N / M part, each part is divided into multiplication, complexity O (m ^ (log3)), the total complexity is N / m * m ^ ( LOG3), ie O (n * mlog (3/2)).
2-5:
For large numbers by 10n, only N 0 is added after the array.
Set u = a * 10 ^ (2N / 3) B * 10 ^ (N / 3) C, V = E * 10 ^ (2N / 3) f * 10 ^ (n / 3) g.
Then w = u * v = ae * 10 ^ (4n / 3) (AF BE) * 10 ^ N (AG BF CE) * 10 ^ (2N / 3) (BG CF) * 10 ^ (N / 3) CG.
Ag BF CE = (A B C) * (E F G) - AE - AF - BE - BG - CF - CG.
Then w = ae * 10 ^ (4n / 3) [(A B C) * (E F G) -AE-CG] * 10 ^ (2n / 3) (AF BE) * 10 ^ N - (AF BE) * 10 ^ (2N / 3) - (BG CF) * 10 ^ (2N / 3) (BG CF) * 10 ^ (N / 3) CG
(AF BE) * 10 ^ N - (AF BE) * 10 ^ (2N / 3) - (BG CF) * 10 ^ (2N / 3) - (BG CF) * 10 ^ (N / 3)
= 10 ^ (2n / 3) * ((A * 10 ^ (N / 3) -C) F (E * 10 ^ (N / 3) -g) b) - 10 ^ (n / 3) * (( A * 10 ^ (N / 3) -C) F (E * 10 ^ (N / 3) -g) b)
So W = AE * 10 ^ (4N / 3) [(A B C) * (E F G) -AE-CG] * 10 ^ (2n / 3) 10 ^ (2N / 3) * ((A * 10 ^ (N / 3) -C) F (E * 10 ^ (N / 3) -g) b) - 10 ^ (n / 3) * ((A * 10 ^ (N / 3) ) -c) f (e * 10 ^ (n / 3) -g) b) cg
As long as AE, CG, (A B C) * (E F G), (A * 10 ^ (N / 3) -C) F, (E * 10 ^ (N / 3) -g) B five
2-6:
For any integer N can be broken down into m * 2c (odd), the N * N matrix can be divided into a matrix of m * m 2c * 2c multiplied, and the rapid matrix multiplication for the 2C * 2C matrix is complex. The degree is O (7C), and the total complexity is O (M37C).
