大数除法 [英] Division with really big numbers
问题描述
我只是想知道在处理大数字时,有什么不同的划分策略.大数字是指约50位数字.
I was just wondering what different strategies there are for division when dealing with big numbers. By big numbers, I mean ~50 digit numbers .
例如 9237639100273856744937827364095876289200667937278/8263744826271827396629934467882946252671
e.g. 9237639100273856744937827364095876289200667937278 / 8263744826271827396629934467882946252671
当两个数字都很大时,长除法似乎失去了它的作用...
When both numbers are big, long division seems to lose its usefulness...
我认为一种可能性是计算除数的乘积,直到获得除数为止,但是如果是上面示例中的除数除以小数,例如4,那么这是大量的计算工作.
I thought one possibility is to count through multiplications of the divisor until you go over the dividend, but if it was the dividend in the example above divided by a small number, e.g. 4, then that's a huge amount of calculations to do.
那么,有没有简单,干净的方法可以做到这一点?
So, is there simple, clean way to do this?
推荐答案
您使用哪种语言/平台?这很可能已经解决,因此您无需从头开始实施.例如. Haskell具有Integer
类型,Java具有java.math.BigInteger
类,.NET具有System.Numerics.BigInteger
结构,等等.
What language / platform do you use? This is most likely already solved, so you don't need to implement it from scratch. E.g. Haskell has the Integer
type, Java the java.math.BigInteger
class, .NET the System.Numerics.BigInteger
structure, etc.
如果您的问题确实是理论上的问题,建议您阅读Knuth,《计算机编程的艺术》,第2卷,第4.3.1节.您要查找的内容在那里称为算法D".这是该算法的C实现,并附有简短说明: http://hackers-delight.org.ua/059.htm
If your question is really a theoretical one, I suggest you read Knuth, The Art of Computer Programming, Volume 2, Section 4.3.1. What you are looking for is called "Algorithm D" there. Here is a C implementation of that algorithm along with a short explanation: http://hackers-delight.org.ua/059.htm
这篇关于大数除法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!