唐津乘法实现 [英] Karatsuba Multiplication Implementation

问题描述

我最近实施了Karatsuba乘法作为个人练习。我按照伪装在维基百科上的伪代码

I recently implemented Karatsuba Multiplication as a personal exercise. I wrote my implementation in Python following the pseudocode provided on wikipedia:

procedure karatsuba(num1, num2)
if (num1 < 10) or (num2 < 10)
    return num1*num2
  /* calculates the size of the numbers */
  m = max(size_base10(num1), size_base10(num2))
  m2 = m/2
  /* split the digit sequences about the middle */
  high1, low1 = split_at(num1, m2)
  high2, low2 = split_at(num2, m2)
  /* 3 calls made to numbers approximately half the size */
  z0 = karatsuba(low1, low2)
  z1 = karatsuba((low1+high1), (low2+high2))
  z2 = karatsuba(high1, high2)
  return (z2*10^(2*m2)) + ((z1-z2-z0)*10^(m2)) + (z0)

这是我的python实现：

Here is my python implementation:

def karat(x,y):
    if len(str(x)) == 1 or len(str(y)) == 1:
        return x*y
    else:
        m = max(len(str(x)),len(str(y)))
        m2 = m / 2

        a = x / 10**(m2)
        b = x % 10**(m2)
        c = y / 10**(m2)
        d = y % 10**(m2)

        z0 = karat(b,d)
        z1 = karat((a+b),(c+d))
        z2 = karat(a,c)

        return (z2 * 10**(2*m2)) + ((z1 - z2 - z0) * 10**(m2)) + (z0)

我的问题是关于 z0 ， z1的最终合并和 z2 。

z2 移位了 m 个数字over（其中 m 是两个相乘数中最大数的长度）。

该算法不是简单地乘以 10 ^（m）使用* 10 ^（2 * m2）*，其中 m2 是 m / 2 。

My question is about final merge of z0, z1, and z2.
z2 is shifted m digits over (where m is the length of the largest of two multiplied numbers).
Instead of simply multiplying by 10^(m), the algorithm uses *10^(2*m2)* where m2 is m/2.

我尝试用 m 替换 2 * m2 ，但结果不正确。我认为这与数字的分割方式有关，但我不太确定发生了什么。

I tried replacing 2*m2 with m and got incorrect results. I think this has to do with how the numbers are split but I'm not really sure what's going on.

推荐答案

根据您的Python版本，您必须或应该将 / 替换为显式的楼层划分运算符 // 在这里合适；

Depending on your Python version you must or should replace / with the explicit floor division operator // which is the appropriate here; it rounds down ensuring that your exponents remain entire numbers.

例如，在将操作数以高位数进行拆分时（按下限除以 10即可），这非常重要。 ^ m2 ）和低位数字（通过采用余模 10 ^ m2 ），这不适用于小数 m2 。

This is essential for example when splitting your operands in high digits (by floor dividing by 10^m2) and low digits (by taking the residual modulo 10^m2) this would not work with a fractional m2.

这也解释了为什么 2 *（x // 2）为什么不如果x为奇数，则必须等于 x ，而必须等于 x-1 。
在算法的最后一行 2 m2 是正确的，因为您正在做的是给 a 和 c 返回零。

It also explains why 2 * (x // 2) does not necessarily equal x but rather x-1 if x is odd. In the last line of the algorithm 2 m2 is correct because what you are doing is giving a and c their zeros back.

如果您使用的是较旧的Python版本，由于 / 在应用于整数时曾经被解释为地板分割。

If you are on an older Python version your code may still work because / used to be interpreted as floor division when applied to integers.

def karat(x,y):
    if len(str(x)) == 1 or len(str(y)) == 1:
        return x*y
    else:
        m = max(len(str(x)),len(str(y)))
        m2 = m // 2

        a = x // 10**(m2)
        b = x % 10**(m2)
        c = y // 10**(m2)
        d = y % 10**(m2)

        z0 = karat(b,d)
        z1 = karat((a+b),(c+d))
        z2 = karat(a,c)

        return (z2 * 10**(2*m2)) + ((z1 - z2 - z0) * 10**(m2)) + (z0)

这篇关于唐津乘法实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！