mor*_*nik 23 c++ algorithm performance integer-division bigint
我正在考虑一个大数除法的算法:用bigint D除以余数bigint C,我们知道基数b中C的表示,D是b ^ k-1的形式.在一个例子中展示它可能是最容易的.让我们尝试将C = 21979182173除以D = 999.
实际上,21979182173/999 = 22001183,其余为356.
我已经计算了复杂度,如果我没弄错的话,算法应该在O(n)中工作,n是基本b表示中C的位数.我在C++中也做了一个非常粗略和未经优化的算法版本(仅适用于b = 10),根据GMP的一般整数除法算法进行测试,它确实看起来比GMP更好.在我看的任何地方都找不到这样的东西,所以我不得不求助于对抗一般师.
我发现有几篇文章讨论了看起来非常相似的问题,但没有一篇专注于实际的实现,特别是在不同于2的基础上.我想这是因为数字在内部存储的方式,尽管所提到的算法似乎很有用,比方说,b = 10,即使考虑到这一点.我也尝试过联系其他人,但是,再一次无济于事.
因此,我的问题是:是否有文章或书籍或其他描述上述算法的东西,可能会讨论实施？如果没有,那么尝试在C/C++中尝试实现和测试这样的算法是否有意义,或者这种算法本质上是不是很糟糕？
另外,我不是程序员,虽然我在编程方面还算合理,但我还是对计算机"内部"知之甚少.因此,请原谅我的无知 - 这篇文章很可能有一个或多个非常愚蠢的事情.再次抱歉.
非常感谢!
进一步澄清评论/答案中提出的观点:
谢谢,每个人 - 因为我不想用同样的事情评论所有伟大的答案和建议,我只想谈谈你提到的很多观点.
我完全清楚,一般来说,在基地2 ^ n工作显然是最有效的做事方式.几乎所有bigint库都使用2 ^ 32或其他.但是,如果(并且,我强调,它仅对这个特定算法有用!)我们将bigint实现为基数b中的数字数组？当然,我们要求b在这里"合理":b = 10,最自然的情况,似乎足够合理.我知道考虑到内存和时间,考虑到内部存储数字的方式或多或少效率不高,但我能够,如果我的(基本的和可能有些缺陷的)测试是正确的,产生的结果比GMP的一般部门更快,这对于实现这样的算法是有意义的.
Ninefingers通知我必须在这种情况下使用昂贵的模运算.我希望不是:我只能通过查看old + new + 1的位数来看看是否旧的+新交叉,比如说999.如果它有4位数字,我们就完成了.更重要的是,由于旧<999和新<= 999,我们知道如果旧+新+ 1有4位数(它不能有更多),那么,(旧+新)%999等于删除最左边的数字(老+新+ 1),我认为我们可以廉价地做.
当然,我并没有质疑这个算法的明显局限性,也没有声称它无法改进 - 它只能分成一定数量的数字,我们必须事先了解基数b中股息的表示.然而,例如,对于b = 10,后者看起来很自然.
现在,我们已经实施了如上所述的bignums.假设基数b中的C =(a_1a_2 ... a_n)且D = b ^ k-1.算法(可能更加优化)会像这样.我希望没有很多错别字.
在那里,感谢您与我讨论 - 正如我所说的,在我看来,这似乎是一个有趣的"特殊情况"算法,试图实现,测试和讨论,如果没有人看到任何致命的缺陷.如果它到目前为止还没有被广泛讨论,那就更好了.请让我知道你在想什么.抱歉这篇长篇文章.
另外,还有一些个人评论:
@Ninefingers:我实际上有一些(非常基本的!)GMP如何工作,它做什么以及一般bigint除法算法的知识,所以我能够理解你的大部分论点.我也知道GMP是高度优化的,并且在某种程度上为不同的平台定制自己,所以我当然不会试图"击败它" - 这似乎与攻击带有尖头棒的坦克一样富有成效.然而,这不是这个算法的想法 - 它适用于非常特殊的情况(GMP似乎没有涵盖).在一个不相关的说明中,你确定在O(n)中完成了一般划分吗？我见过的最多的是M(n).(如果我理解正确,那么在实践中(Schönhage-Strassen等)就不会达到O(n).Fürer算法仍然没有达到O(n),如果我是正确的,几乎是纯粹的理论.)
@Avi Berger:虽然这个想法很相似,但实际上它似乎并不完全与"淘汰9"相同.但是,如果我没有弄错的话,上述算法应该始终有效.
Avi*_*ger 12
您的算法是基础10算法的变体,称为"输出9".你的例子是使用基数1000并"逐出"999(比基数少一个).这曾经在小学教过,作为快速检查手工计算的方法.我有一个高中数学老师,他很惊讶地发现它不再被教导并且让我们充满了它.
在基数1000中输出999将不能作为一般除法算法.它将生成与实际商和余数一致的模999的值 - 而不是实际值.你的算法有点不同,我没有检查它是否有效,但它是基于有效地使用基数1000和除数比基数小1.如果您想尝试将其除以47,则必须先转换为基数为48的数字系统.
谷歌"淘汰了9"以获取更多信息.
编辑:我最初读的帖子太快了,你知道这是一个有效的算法.由于@Ninefingers和@Karl Bielefeldt在他们的评论中已经比我更清楚地说明了,你在绩效评估中没有包括的是转换成适合当前特定除数的基数.
小智 5
我认为有必要根据我的评论添加到此.这不是答案,而是对背景的解释.
bignum库使用所谓的肢体 - 在gmp源中搜索mp_limb_t,它通常是固定大小的整数字段.
当你做类似添加的事情时,一种方法(虽然效率低)接近它是这样做的:
doublelimb r = limb_a + limb_b + carryfrompreviousiteration
在总和大于肢体大小的情况下,这个双倍大小的肢体捕获limb_a + limb_b的溢出.因此,如果我们使用uint32_t作为我们的肢体大小,如果总数大于2 ^ 32,则可以捕获溢出.
我们为什么需要这个？好吧,你通常做的是循环遍历所有的肢体 - 你自己完成了将你的整数划分并通过每一个 - 但我们先做LSL(所以最小的肢体)就像你做算术一样用手.
这可能看起来效率低下,但这只是C方式.为了真正打破大枪,x86 adc作为一个指令 - 添加携带.这样做的是算术和字段,如果算术溢出寄存器的大小,则设置进位.下一次你做add或者adc,处理器因素也在进位中.在减法中,它被称为借用标志.
这也适用于换档操作.因此,处理器的这一特性对于使bignums快速变化至关重要.事实上,芯片中有电子电路用于完成这些工作 - 在软件中进行操作总是会变慢.
没有太多的细节,操作是通过这种添加,移位,减去等功能建立起来的.它们至关重要.哦,如果你做得对,你可以使用处理器每个肢体的整个宽度.
第二点 - 基地之间的转换.您不能在数字的中间取值并更改它的基数,因为您无法考虑原始基数下方数字的溢出,并且该数字无法解释下方数字的溢出. .. 等等.简而言之,每次要更改基础时,都需要将整个bignum从原始基础转换回新基础.所以你必须至少三次走到bignum(所有四肢).或者,或者,在所有其他操作中检测昂贵的溢出...记住,现在你需要进行模运算,以便在溢出时解决,而在处理器为我们做之前.
我还想补充一点,虽然你得到的东西可能很快就可以了,但请记住,作为一个bignum库gmp为你做了很多工作,比如内存管理.如果你正在使用mpz_你使用的抽象高于我在这里描述的抽象,对于初学者.最后,gmp使用手动优化的装配和展开的循环,几乎可以听到您听过的每个平台,还有更多.有一个很好的理由它与Mathematica,Maple等人一起发布.
现在,仅供参考,一些阅读材料.
为你总结:除法汇编指令很糟糕,所以人们通常会计算求逆并乘以,就像在模运算中定义除法时那样.存在的各种技术(参见MCA)主要是O(n).
编辑:好的,并非所有技术都是O(n).大多数称为div1的技术(除以不大于肢体的东西都是O(n).当你变大时,你最终会有O(n ^ 2)的复杂性;这很难避免.
现在,您可以将bigints实现为数字数组吗？是的,当然可以.但是,考虑一下这个想法
/* you wouldn't do this just before add, it's just to
show you the declaration.
*/
uint32_t* x = malloc(num_limbs*sizeof(uint32_t));
uint32_t* y = malloc(num_limbs*sizeof(uint32_t));
uint32_t* a = malloc(num_limbs*sizeof(uint32_t));
uint32_t m;
for ( i = 0; i < num_limbs; i++ )
{
m = 0;
uint64_t t = x[i] + y[i] + m;
/* now we need to work out if that overflowed at all */
if ( (t/somebase) >= 1 ) /* expensive division */
{
m = t % somebase; /* get the overflow */
}
}
/* frees somewhere */
这是您通过计划添加内容的粗略草图.所以你必须在基数之间进行转换.因此,您需要转换为基础的表示,然后在完成后返回,因为此形式在其他任何地方都非常慢.我们这里并没有谈论O(n)和O(n ^ 2)之间的区别,但是我们讨论的是每个肢体的昂贵的划分指令或者每次想要划分时的昂贵转换.看到这个.
接下来,您如何扩展您的一般案例部门的部门？通过这个,我的意思是当你想从上面的代码中划分这两个数字x和y.如果不采用昂贵的基于bignum的设施,你就不能这样做.见Knuth.取模数大于你的大小是不行的.
让我解释.尝试21979182173 mod 1099.为了简单起见,我们假设我们可以拥有的最大字段是三位数.这是一个人为的例子,但我所知道的最大字段大小是使用gcc扩展使用128位.无论如何,重点是,你:
21 979 182 173
将你的号码分成四肢.然后你取模数和求和:
21 1000 1182 1355
它不起作用.这是Avi正确的地方,因为这是一种铸造9或其适应性的形式,但它在这里不起作用,因为我们的字段已经溢出一开始 - 你使用模数来确保每个字段保持在它的肢体/野外大小.
那么解决方案是什么？将你的号码分成一系列大小合适的bignums？并开始使用bignum函数来计算你需要的一切？这将比任何现有的直接操作字段的方式慢得多.
现在也许你只是提出这个案例来划分一个肢体,而不是一个bignum,在这种情况下它可以工作,但hensel划分和预先计算的反转等没有转换要求.我不知道这个算法是否比hensel分区更快; 这将是一个有趣的比较; 这个问题伴随着bignum图书馆的共同表现.在现有的bignum库中选择的表示是出于我扩展的原因 - 它在组装级别上有意义,它首先完成.
作为旁注; 你不必uint32_t用来代表你的四肢.您可以使用理想大小的系统寄存器大小(例如uint64_t),以便您可以利用程序集优化的版本.因此,在64位系统上,adc rax, rbx如果结果超过2 ^ 64位,则仅设置溢出(CF).
tl;博士版:问题不是你的算法或想法; 这是在基数之间进行转换的问题,因为你的算法所需的表示不是在add/sub/mul等中执行它的最有效方式.用来解释knuth:这显示了数学优雅和计算效率之间的区别.