我正在考虑一个大数除法的算法:用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.算法(可能更加优化)会像这样.我希望没有很多错别字.