Karatsuba算法：分裂字符串

Question

我正在尝试在C中实现Karatsuba算法。我使用char字符串（它是某个基数中的数字），虽然我认为我已经理解了大多数Karatsuba算法，但我没有得到我应该将字符串拆分到的位置乘。

例如，我应该在哪里切123 * 123，哪里可以切123 * 12？ 我无法找到适用于这两种计算的解决方案。

我尝试将它切成两半并将结果放在地板上，如果数字是奇数，但它不起作用，并且天花板也不起作用。

任何线索？

设a，b，c和d为字符串的一部分。

• 让我们试试123 * 12 首先尝试（a = 1，b = 23，c = 1，d = 2）（失败）

  z0 = a * c = 1
  z1 = b * d = 46
  z2 = (a + b) * (c + d) - z0 - z1 = 24 * 3 - 1 - 46 = 72 - 1 - 46 = 25
  
  z0_padded = 100
  z2_padded = 250
  
  z0_padded + z1 + z2_padded = 100 + 46 + 250 = 396 != 123 * 12

  第二次尝试（a = 12，b = 3，c = 12，d = 0）（失败）

  z0 = 144
  z1 = 0
  z2 = 15 * 12 - z1 - z0 = 180 - 144 = 36
  
  z0_padded = 14400
  z2_padded = 360
  
  z0_padded + z1 + z2_padded = 14760 != 1476

  第三次尝试（a = 12，b = 3，c = 0，d = 12）（成功）

  z0 = 0
  z1 = 36
  z2 = 15 * 12 - z0 - z1 = 144
  
  z0_padded = 0
  z2_padded = 1440
  
  z0_padded + z1 + z2_padded = 1476 == 1476

• 让我们试试123 * 123 首先尝试（a = 1，b = 23，c = 1，d = 23）（失败）

  z0 = 1
  z1 = 23 * 23 = 529
  z2 = 24 * 24 - z0 - z1 = 46
  
  z0_padded = 100
  z2_padded = 460
  
  z0_padded + z1 + z2_padded = 561 != 15129

  第二次尝试（a = 12，b = 3，c = 12，d = 3）（成功）

  z0 = 12 * 12 = 144
  z1 = 3 * 3 = 9
  z2 = 15 * 15 - z0 - z1 = 72
  
  z0_padded = 14400
  z2_padded = 720
  
  z0_padded + z1 + z2_padded = 15129 == 15129

  第三次尝试（a = 12，b = 3，c = 1，d = 23）（失败）

  z0 = 12
  z1 = 3 * 23 = 69
  z2 = 15 * 24 - z0 - z1 = 279
  
  z0_padded = 1200
  z2_padded = 2799
  
  z0_padded + z1 = z2_padded = 4068 != 15129

在这里，我没有得到我搞砸了的地方。请注意，我的填充方法在数字的末尾添加n个零，其中n = m * 2，m等于最长字符串的大小除以2。

EDIT

现在我已经明白b和d必须具有相同的长度，它几乎每次都有效，但仍然有例外：例如1234 * 12

a = 123
b = 4
c = 1
d = 2

z0 = 123
z1 = 8
z2 = 127 * 3 - 123 - 8 = 250

z0_padded = 1230000
z2_padded = 25000

z0_padded + z1 + z2_padded = 1255008 != 14808

在这里，假设我正确地分割了字符串，问题是填充，但我不知道应该如何填充。我在Wikipedia上读到我应该根据最大字符串的大小来填充（见几行），应该有另一个解决方案。

Answer 1

Karatsuba算法是一种很好的执行乘法的方法。 如果你想让它起作用，b和d的长度必须相同。

以下是计算123x12的两种可能性：

a= 1;b=23;c=0;d=12;
a=12;b= 3;c=1;d= 2;

让我们解释它如何适用于第二种情况：

123=12×10+3
 12= 1×10+2
123×12=(12×10+3)×(1×10+2)
123×12=12×1×100+             (12×2+3×1)×10+3×2
123×12=12×1×100+((12+3)×(1+2)-12×1-3×2)×10+3×2

让我们解释一下第一种情况是如何工作的：

123=1×100+23
 12=0×100+12
123×12=(1×100+23)×(0×100+12)
123×12=1×0×10000+              (1×12+23×0)×100+23×12
123×12=1×0×10000+((1+23)×(0+12)-1×0-23×12)×100+23×12

它也适用于10^k，2^k或n而不是10或100。