last day (15 days later) » 

19:57
0
Q: java BigInteger - How does destructiveMulAdd convert a number to big endian magnitude?

ng.newbieI am doing this side project where I try to understand the internal implementation of some of the widely used utility classes in Java. I want to know how BigInteger store's the number internally. What I found was that it is using an int[] for storing the magnitude of a number in "big-endian" form...

This is an algorithm that you learned in elementary school, maybe you are confusing yourself with the implementation details but the algorithm itself is trivial. How do you multiply 123456 by 8? With this algorithm, probably. Multiply 6 by 8, write down an 8, carry the 4.. that's what's happening here but with a higher base.
Could you please go into more detail ? The internal representation of 12345678901234567890123456789012345678901234567890 looks like [8, 1920951145, -1426572127, 1344697466, -121114218, -834729262]. Could you please show an example with a higher base ? How does the internal representation correlate to the actual number ?
@harold I am unable to ascertain how this is just a simple multiplication.
Just as 123 means 3 * 10^0 + 2 * 10^1 + 1 * 10^2, here int[] { 1, 2, 3 } would mean 3 * (2^32)^0 + 2 * (2^32)^1 + 1 * (2^32)^2. Limbs with their highest bit set will be presented as being negative, but you're supposed to interpret them as unsigned values, which the code does by bitwise-ANDing them with LONG_MASK
@harold Ok maybe I am beginning to understand a bit. The base of the number is 10^9, right? Each digit can have 0 - 10^9-1 symbols, right? Each digit is an element in the int[] array, right? So just like in decimal to add a digit to its correct position I multiply the partial number I have then add the digit to that, I am multiplying by 10^9 as that is the base we are using. So its y*10^9 + z, correct ?
@harold But then I have a confusion about the way the multiplication is being done. Why is it multiplying each digit with the radix ? That's not how the algorithm works right ? You are supposed to take the entire number as it is now right ?
The base of the number in the int[] is 2^32, the base of the number being parsed is effectively 10^9 (by pulling out 9 digits and parsing them to an int first). We multiply the number in the int[] by 10^9, because that's the base of the number being parsed (effectively), but that multiplication happens in a representation that is base 2^32.
19:57
@harold Why not just convert base 10 to base 10^9 ? Why convert to base 2^32 ? Keeping it as 10^9 wont even have to change the representation. Each base 10^9 block can be one element in the mag[] array. It seems so much easier. Where am I going wrong ?
Absolutely, that would be much easier - for conversion to and from a (decimal) string. It would be less efficient to implement arithmetic on that representation, but it's possible and sometimes done that way. Java's BigInteger doesn't do it that way.
@harold Why do the comments in the code say that the magnitude is stored in big-endian format ? Shouldn't it be little endian as it parses the number from left to right but stores in the array from right to left ?
The most significant part of the number is stored at the lowest index, which is similar to big-endian although I normally only use that terminology for a byte order. That's why the loops for multiplication and addition are "backwards".
@harold How is implementing arithmetic on 2^32 easier than 10^9 ?
@harold When you say "lowest index" do you mean len -1 index or 0 index ?
For the purposes of eg addition and multiplication: if you use base 2^32 you never have to use annoying operations such as modulo by 10^9 or divide by 10^9, just truncation and shift. Even worse, for the purposes of eg bitCount, shiftRight, xor, having a non-power-of-two base would be very annoying. By "lowest index" I just mean zero.
19:57
@harold Ok, I am unable to understand how the most significant part of the number is in 0 index. For example, take the number 1234567890123456789, the implementation (verified via debugger) will take 12345 from the left and then put it in the len - 1 index of the mag array. So it is taking the most significant part of the number and placing it in highest index ie. len - 1. And isn't that little endian ? Where am I going wrong ?
It just looks that way. If you look at the final result, or at how the arithmetic works, you will see that it's not so. The number in the int[] is iteratively changed by multiplying it by 10^9 and adding a chunk from the string. The first part of the string that gets added to it, starts at the least significant end of the int[] indeed, but then it gets multiplied by 10^9 the most times so it ends up in the most significant part eventually. Try parsing "340282367079394788547243514857164636165"
 
1 hour later…
21:05
@harold Yes you are absolutely right. It lead to the following calculations: imgur.com/a/se5Eoo2. However I am still confused as to how this algorithm works. Let me tell you what I know about converting from one base to another, ie. converting from 10^9 to 2^32. I would use this classical technique: math.stackexchange.com/a/111158/407302
the way BigInteger(String val, int radix) does the base conversion is essentially the opposite: it starts by extracting the most significant digits from the input (which is easy with a string, the linked algorithm isn't so string focused). It's like this, but with a larger base: for (int i = 0; i < str.length; i++) number = number * 10 + (str[i] - '0');
sorry I got that reversed for a moment, numbers in strings being conventionally big-endian gets me every time
@harold as you can see in the classical method it starts at the "little end first", ie. little endian. Hence, I have never done the conversion in "big-endian style" before. I am particularly confused as to how the last mag[len-1] "bubbles up" to the first index.
@harold We always multiply from right to left, then intuitively last mag should be the most significant. Let me give an example : 123, we take the first digit ( as you have shown above) we multiply it by (0 * 10 + 1), next step -> (1 * 10 + 2) next step -> (12 * 10 + 3) => 123. Is this what you mean by starting MSB ?
21:22
right that's what happens, the advantage I suppose is that the multiplication is always just by the base (working the other way, we'd have to multiply by successive powers of the base)
the base of the input that is, not the base in which the result is represented
21:50
@harold I can't seem to get my head around it. I think I need a simpler concrete example. Could you give me the break-up of how Java BigInteger would convert (1200)base3 to (45)base10. The mag[] array needs to contain [4,5] but it needs to start from filling up from the end and not the beginning. Could you please give me a breakup ? I really don't understand how this is working.
well it doesn't convert to base 10, but we can pretend, right?
@harold Of course we can pretend. I just need to understand how the "bubble-up" is working. Never seen that before in my life.
start with [0, 0], we add 1 to it, and we get [0, 1] (because `mag` is oddly reversed, that's the effect of it being big-endian)
Then multiply it by 3 (the base) and add 2, so we get [0, 5]
Multiply by 3, add 0: [1, 5]
Multiply by 3, add 0: [4, 5]

last day (15 days later) »