java - 乘法和除法 O(1) 是在最常用的计算机架构上实现的方式吗？

Question

乘法和除法 O(1) 是在最常用的计算机架构上实现的方式吗？

例如，在 x86 和 ARM 上，乘法和除法是 O(1) 吗？如果我使用 Java 的 BigInteger 类并将 BigInteger 的两个实例相乘或相除怎么办？这显然可能不是 O(1)，但复杂度是多少？

score 3 · Accepted Answer

3

BigInteger在 Oracle JDK 中，乘法和BigDecimal除法都是 O(M*N)。

于 2013-09-22T03:53:43.137 回答

score 1 · Accepted Answer

对于任意大操作数，复杂性保持不变似乎不太可能。除非您可以拥有任意大型硬件来遵循这一点（并且它可能不会线性增长）。

回答您的问题：它在不同的系统和不同的语言中有所不同。

但是对于“正常”大小的整数，您可以查看 ARM 文档。

例如，ARM 汇编乘法指令包含不同的小节。假设汇编语言和特定的 ARM 平台，您可以在官方文档中挖掘。这为您提供了执行乘法所需的周期数。因为 ARM 是一台 RISC 机器，所以使用它很方便。然后将其与您的供应商芯片频率进行比较。

例如对于ARM7 处理器。

2 回答 2