algorithm - 将大量小数相乘的有效方法

Question

这个问题是在面试中被问到的。

你有一个小整数数组。你必须将它们全部相乘。你不必担心溢出你有足够的支持。您可以做什么来加快机器上的乘法运算？

在这种情况下，多次添加会更好吗？

我建议使用分而治之的方法进行乘法运算，但面试官并不以为然。最好的解决方案是什么？

Answer 1

以下是一些想法:

多线程分而治之:将输入分成 n 个大小为 b 的不同 block ，然后递归地将每个 block 中的所有数字相乘。然后，递归地将所有 n/b block 相乘。如果您有多个内核并且可以并行运行其中的一部分，那么您总体上可以节省大量时间。

Word-Level Parallelism:假设您的数字都以某个数字 U 为界，该数字恰好是 2 的幂。现在，假设您要将 a、b、c 和 d 相乘。从计算 (4U²a + b) × (4U²c + d) = 16U⁴ac + 4U^{2 开始}ad + 4U²bc + bd。现在，请注意这个表达式 mod U² 只是 bd。 (因为 bd < U²，我们不需要担心 mod U² 步骤搞砸了)。这意味着如果我们计算此乘积并将其取模 U²，我们将返回 bd。由于 U² 是 2 的幂，这可以通过位掩码来完成。

接下来，注意

4U²ad + 4U²bc + bd < 4U⁴ + 4U⁴ + U² < 9U⁴ < 16U⁴

这意味着如果我们将整个表达式除以 16U⁴ 并向下舍入，我们最终将只返回 ad。这种除法可以通过位移来完成，因为 16U⁴ 是 2 的幂。

因此，通过一次乘法，您可以通过应用后续的移位和位掩码来取回 ac 和 bd 的值。一旦有了 ac 和 bd，就可以直接将它们相乘得到 abcd 的值。假设位掩码和位移位比乘法更快，这会将所需的乘法次数减少 33%(这里是两个而不是三个)。

希望这对您有所帮助!