Menu
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
758
In Python, value of an integer is not restricted by the number of bits and can expand to the limit of the available memory (Sources : this and this). Thus we never need any special arrangement for storing large numbers (Imagine doing above arithmetic in C/C++).
Type int(x) to convert x to a plain integer. Type long(x) to convert x to a long integer.
Python, however, doesn't use a fixed number of bit to store integers. Instead, Python uses a variable number of bits to store integers. For example, 8 bits, 16 bits, 32 bits, 64 bits, 128 bits, and so on. The maximum integer number that Python can represent depends on the memory available.
Python integers are arbitrary-precision integers, also known as bignums. This means that they can be as large as we want, and their sizes are only limited by the amount of available memory. Bignums are handy to work with because we don't need to worry about such things as integer overflows and underflows.
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.
Say you want to add 100 to 901. You start with the two numbers as arrays:
[0, 1, 0, 0]
[0, 9, 0, 1]
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.
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.
Real implementations use full words, so the modulus is really some large power of two, but the concept is the same.
There's a very good section on this in Knuth.
140
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
