7. Разделяй и владей - бързо умножение на дълги числа [7.7] - 18.11.2003

* Класическият алгоритъм за умножение на цели числа има сложност O(n2).

* Алгоритъм за умножение на две n-цифрени числа X и Y, като n е степен на 2.

X = 2n/2 A + B,    Y = 2n/2 C + D
XY = 2n AC + 2n/2 [(A - B)(D - C) + AC + BD] + BD
Числата A, B, C и D са n/2 цифрени числа (разделяй) - може да се използва рекурсия, като тривиалния случай е (директно) умножение на едноцифрени числа.

* Тази формула изисква 3 умножения, 6 събирания и 2 премествания вляво (умножения на степени на 2). От рекурентната формула

T(1) = 1,  T(n) = 3T(n/2) + cn, n > 0
получаваме, че сложността на алгоритъма е O(nr), r = log23. Тъй като log23 < 2, то този алгоритъм е по-добър от класическия.

* Пример 1: 15 x 8 = 120,  X = 15 = 11112,  Y = 8 = 10002, n = 4 = 22
 A = 11, B = 11, C = 10, D = 00
 AC = 110,  (A - B)(D - C) = 0.10 = 0, BD = 0
 XY = 110 << 4 + 110 << 2 = 1100000 + 11000 = 11110002 = 8+16+32+64 = 12010

* Когато числата са с различен брой цифри и/или този брой не е степен на 2, допълваме отляво с незначещи нули и използваме горния алгоритъм.

* Пример 2. 50 x 25 = 1250, X = 50 = 1100102,  Y = 25 = 110012, n = 8 = 24 с допълване до най-близката степен на 2.
 A = 0011 (3), B = 0010 (2), C = 0001 (1), D = 1001 (9)
 AC = 0011 (3),  (A - B)(D - C) = 0001.1000 = 1000 (8), BD = 10010 (18)
 XY = 3.256 + (8 + 3 + 18).16 + 18 =
          11 << 8 + 11101 << 4 = 11 0000 0000 + 1 1101 0000 + 10010 = 100111000102 =
          2+32+64+128+1024 = 125010
* Подзадачи:
  - представяне на дълги числа (низ или вътрешно);
  - брой на битовете на цяло число;
  - разделяне на десните от левите битове на числото;
  - сума и разлика на две числа.
Пример: Сума на две числа, записани като C-низове.