-1

在将两个二进制值相乘时，我试图找出一个关于 Karatsuba 算法的问题。我正在尝试乘以：

10110110 * 11001000

我需要弄清楚使用 Karatsuba 算法时完成了哪些子问题。我知道算法是

x * y = ((2^n)(xHyH))+(2^(n/2))(xHyL + xLyH) + xLyL

但是每个值代表什么？如何从二进制值转到xH,yH,xL,and yL？谢谢。

4

1 回答 1

0

关键是将您的数字分成低部分和高部分：

x = 10110110b
xh= 1011b
xl=     0110b
x = xh<<4 + xl

在 Karatsuba 中处理数字时，数字的底数并不重要（但所有底数都必须相同），因此您可以使用任何底数。您只需要在您使用的使用过的基础上定义所需的操作。因此，例如，如果您的数字是十进制字符串，则无需将其转换为二进制。

因此，关键是在第一次运行中从右到零填充x,y到 2 位宽的常用幂（如果尚未完成），或者在每次运行中只到常用大小，以避免/处理分割时的舍入问题。由于数字通常采用某种寄存器或编程语言变量类型，因此它们通常已经被零填充。如果是 bignums 或字符串，则不能保证。

然后在每一步中，你将你x,y分成两半并计算方程。

这些方程涉及乘法，因此它递归地调用相同的 karatsuba 乘法，但现在使用半位宽数字。

一旦达到可计算位宽，就直接计算乘法，而不是使用 Karatsuba（这通常是ALU支持乘法x,y的最高字位宽）。

由于您输入x,y的数字已经是 8 位，因此不需要大多数CPU可以直接处理 Karatsuba。如果您没有乘法或只想尝试可以细分直到位宽为 1 并使用真值表的东西：

0*0=0
0*1=0
1*0=0
1*1=1

现在的问题是您需要将可能超过其位宽的数字块相加（在部分乘法之后）。（如果你添加两个 4 位数字，结果可能是 9 位）在 Karatsuba 方程中，你添加了很多东西，所以你需要记住你需要的不仅仅是单个进位位（我认为两个应该削减它，我改为使用双增量（检查溢出两次），这对我有用）。

此外，如果您使用限制 ALU 位宽和更高级别的语言（如 C/C++），您可能根本无法访问进位并需要解决它，例如像这样：

这里的小例子（以及其他一些方法）：

如果您想测量速度，请记住 Karatsuba 的开销比天真O(n^2)的乘法开始更快，只有在足够大的数字时才会更快......

现在回到你的分裂问题。一切都取决于您的号码是如何存储的。因此，对于字符串，您可以使用字符串函数将它们拆分。如果是数字，您将它们放在一些已经以二进制表示的变量中（在硅级别上），因此您可以使用位移位和掩码。对于8 -> 4 + 4 C++ 中的位，它是这样完成的：

x = your number;
xl = x&15; // bitwise AND
xh = x>>4; // shift right arithmetic SRA by 4 bits

where15 = (1<<4)-1和4是您要拆分到的位宽。因此，如果您想要n位宽，您可以重写为：

x = your number;
n = new bit width (half of x bitwidth)
xl = x&((1<<n)-1); // bitwise AND
xh = x>>n; // shift right arithmetic SRA by 4 bits

您也可以将n递归作为操作数传递，然后将其减半n>>=1并停止，n=0这意味着您已经处于 1 位宽度并且没有理由拆分...

于 2018-04-20T06:29:46.067 回答