Kru*_*nch 3 performance biginteger multiplication addition
我需要一些帮助来决定什么是更好的性能.我正在使用bigints (超过500万个数字)并且大部分计算(如果不是全部)都是将当前bigint加倍的部分.所以我想知道将每个单元格(bigint的一部分)乘以2然后修改它然后知道其余的更好.或者更好的方法是将 bigint 添加到自身.
我正在考虑一下实现的简易性(添加2个bigint更复杂然后乘以2),但我更关心的是性能而不是代码的大小或易于实现.
其他信息:我将用C++编写代码,我对bigints非常熟悉(只是从未遇到过这个问题).我不需要任何源代码或类似的东西我只需要一个很好的意见和解释/证明它,因为我需要从一开始做出一个很好的决定,因为项目将相当大,并且主要围绕这部分构建这在很大程度上取决于我现在选择的内容
谢谢.
尝试每位移位.这可能是最快的方法.当你将一个整数向左移位时,你将它加倍(乘以2).如果链中有几个长整数,那么你需要存储最高位,因为在移位之后,它将消失,你需要将它作为下一个长整数的最低有效位.
这实际上并不重要.现代64位计算机可以在对它们进行位移(1个时钟周期)的同时添加两个整数,因此它需要同样长的时间.我建议你尝试不同的方法,然后报告是否有任何重大的时间差异.所有这三种方法都应该易于实现,使用随机数生成器生成5mb数也应该很容易.
要存储一个500万位的整数,你需要相当多的位 - 如果你指的是二进制数字,则需要500万,如果是十进制数字,则需要大约1700万位.假设数字以二进制表示形式存储,并且算术以某种大小的块发生,例如32位或64位.
如果将数字添加到自身,则每个块都会添加到自身以及添加前一个块的进位.任何结转都保留在下一个块中.这是一些额外的操作,还有一些用于跟踪进位的簿记.
如果通过左移乘以2,则为乘法的一个左移操作,一个右移操作+和1以获得进位.携带簿记比较简单.
从表面上看,换档版本看起来略快一些.然而,将数量加倍的总成本很大程度上受到数量的影响.一个1700万位的数字超过了cpu的L1缓存,处理时间很可能被内存提取操作所淹没.在现代PC硬件上,内存提取比添加和移位慢几个数量级.
有了这个,你可能想选择一个更容易实现的那个.我倾向于左移版本.