我想知道BigInt和其他类似的东西是如何实现的.我试图查看JAVA源代码,但对我来说全是希腊文和拉丁文. 您能不能用语言解释我的算法-无需代码,这样我就能理解当我使用JAVA API中的某些东西时我实际上正在使用什么. 问候
I wanted to know how the BigInt and other such stuff are implemented. I tried to check out JAVA source code, but it was all Greek and Latin to me. Can you please explain me the algo in words - no code, so that i understand what i am actually using when i use something from the JAVA API. regards
推荐答案从概念上讲,这与手工处理任意大小的算术相同.您将拥有一个值数组,以及用于该数组的各种操作的算法.
Conceptually, the same way you do arbitrary size arithmentic by hand. You have something like an array of values, and algorithms for the various operations that work on the array.
说您想将100添加到901.您将从两个数字开始作为数组:
Say you want to add 100 to 901. You start with the two numbers as arrays:
[0, 1, 0, 0] [0, 9, 0, 1]添加时,添加算法从右开始,取0+1,给出1,0+0,给出0,然后-现在棘手的部分-9+1得到10 ,但现在我们需要携带,因此我们在下一列中加1,然后将(9+1)%10放入第三列.
When you add, your addition algorithm starts from the right, takes 0+1, giving 1, 0+0, giving 0, and -- now the tricky part -- 9+1 gives 10, but now we need to carry, so we add 1 to the next column over, and put (9+1)%10 into the third column.
当您的数字足够大时(在此示例中大于9999),那么您就必须以某种方式分配更多的空间.
When your numbers grow big enough -- greater than 9999 in this example -- then you have to allocate more space somehow.
当然,如果按反向顺序存储数字,则此方法会有所简化.
This is, of course, somewhat simplified if you store the numbers in reverse order.
实际的实现使用完整的单词,因此模数确实是2的大乘方,但是概念是相同的.
Real implementations use full words, so the modulus is really some large power of two, but the concept is the same.
在Knuth中有一个很好的章节.
There's a very good section on this in Knuth.
更多推荐
BigNums实现如何工作?
发布评论