brief intro

The following image is from coursera’s course which is called Divided And Conquer opened from Stanford University.

n = digit
a, b = (digit_1)[0..n/2], (digit_1)[n/2..]
c, d = (digit_2)[0..n/2], (digit_2)[n/2..]

我的猜測(但有誤)

麻煩是在如何計算結果 ex. 123*26 a = 12, b =3
c = 2, d = 6

1. a*c 後面幾顆 0 = b*c的位數 所以b*c = (int)log(18)+1 = 2
   so a*c = 2400
2. 3)-2)-1) 的這步運算要到幾位數 = (int)log(a*c) = round(log(2400)) = 3(need 3 digit)
   3)-2)-1) = b*c+a*d = 780(until 3 digit)
3. b*d = 18
4. Add all result -> 2400 + 18 + 780 = 3198

ex. 24*39 a = 2, b = 4
c = 3, d = 9
按照上面的計算過程

1. b*d = 36
2. a*c = 600
3. bc+ad = 12 + 18 = 300
4. Add all 936

ex. 99*18 a = 9, b = 9
c = 1, d = 8

1. b*d = 72
2. a*c = 900
3. bc+ad = 9+72 = 810 because round(log(900)) = 3
4. 1782 ex. 396*2499 a = 39, b = 6
   c = 24, d = 99
5. b*d = 594
6. a*c = 936000
7. bc+ad = 144+3861 = 400500
8. add all 1,337,094 (出錯) 正確答案為 989,604

老師解釋