Ruby 中的卡拉苏巴乘法优化 - 失败

Question

将 N 位数字

的 2 个数字相乘，其中 N 是偶数。 multiply（1234,5678） 返回 7006652，这是正确的乘积。 #multiply_opt 在传递相同的参数时应返回相同的值，但事实并非如此。

任何想法总是非常感谢！

def multiply(x, y)
  return x * y if x.to_s.length <= 1 && y.to_s.length <= 1
  n = x.to_s.length
  x_mid = x.to_s.length / 2
  y_mid = y.to_s.length / 2
  a = x.to_s[0..x_mid-1].to_i
  b = x.to_s[x_mid..-1].to_i
  c = y.to_s[0..y_mid-1].to_i
  d = y.to_s[y_mid..-1].to_i
  ac = multiply(a,c)
  ad = multiply(a,d)
  bc = multiply(b,c)
  bd = multiply(b,d)
  ((10**n) * ac) + (10**(n/2) * (ad + bc)) + bd
end
def multiply_opt(x, y)
  # Not sure if this base case is correct...
  return x * y if x.to_s.length <= 1 || y.to_s.length <= 1
  # Not sure exactly how to define n
  n = [x.to_s.length, y.to_s.length].max
  x_mid = x.to_s.length / 2
  y_mid = y.to_s.length / 2
  a = x.to_s[0..x_mid-1].to_i
  b = x.to_s[x_mid..-1].to_i
  c = y.to_s[0..y_mid-1].to_i
  d = y.to_s[y_mid..-1].to_i
  # Recursive Calls
  s1 = multiply_opt(a,c)
  s2 = multiply_opt(b,d)
  s3 = multiply_opt((a + b),(b + d))
  s4 = s3 - s1 - s2
  (10**n)*s1 + (10**(n/2)* s4) + s2
end

Answer 1

你的问题是你定义了单独的x_mid，y_mid这是错误的。并且分裂必须发生在相同的位置，即在n/2，从较低的数字来看。

您的示例失败的地方是第 3 次乘法，因为那里的操作数有 2 位和 3 位数字。拆分应分隔最后一个数字。使用您的方法，3 位数字被拆分为 1 位和 2 位，这是错误的。

---

更多细节：卡拉苏巴从将您的数字拆分

为

x = x1*M+x0
y = y1*M+y0

使产品

x*y = x1*y1*M^2+((x1+x0)*(y1+y0)-x1*y1-x0*y0)*M + x0*y0

可以使用较小数字的三个乘法来计算。流行的是使用带有数基B的M=B^k，以便x0和y0包含x和y的最低k位。

在您的示例中，您必须决定始终如一地使用k=1或k=2，通过 Karatsuba 的设计，人们会要求x,y<M^2，这意味着k=2 .

---

考虑到这些想法，您的算法应该修改为

def multiply_opt(x, y)
  # Not sure if this base case is correct...
  return x * y if x.to_s.length <= 1 || y.to_s.length <= 1
  # Not sure exactly how to define n
  n = [x.to_s.length, y.to_s.length].max
  k = (n+1) / 2
  x_mid = x.to_s.length - k
  y_mid = y.to_s.length - k
  a = x.to_s[0..x_mid-1].to_i
  b = x.to_s[x_mid..-1].to_i
  c = y.to_s[0..y_mid-1].to_i
  d = y.to_s[y_mid..-1].to_i
  # Recursive Calls
  s1 = multiply_opt(a,c)
  s2 = multiply_opt(b,d)
  s3 = multiply_opt((a + b),(c + d))
  s4 = s3 - s1 - s2
  (10**(2*k))*s1 + (10**k * s4) + s2
end

第一种方法中的拆分和重构语句应相应修改。