How Fast Can We Multiply Large Integers on an Actual Computer?
How Fast Can We Multiply Large Integers on an Actual Computer?
复制标题
我们在实际计算机上乘以大整数的速度有多快？
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Martin Fürer
中科院分区：
文献类型：
--
作者：
Martin Fürer
我们提供了两个复杂性度量，可用于度量计算长整数乘法的算法的运行时间。具有单位成本或对数成本的随机存取机不足以测量像长整数乘法这样的任务的复杂性。图灵机在这里更有用，但没有考虑到短整数的乘法指令，这在物理计算设备上可用。一个有趣的结果是，提出的改进复杂性度量并没有像图灵机模型那样对众所周知的乘法算法进行排名。
We provide two complexity measures that can be used to measure the running time of algorithms to compute multiplications of long integers. The random access machine with unit or logarithmic cost is not adequate for measuring the complexity of a task like multiplication of long integers. The Turing machine is more useful here, but fails to take into account the multiplication instruction for short integers, which is available on physical computing devices. An interesting outcome is that the proposed refined complexity measures do not rank the well known multiplication algorithms the same way as the Turing machine model.