0

THIS is most likely the longest answer ever on SO. I am trying to understand the custom implementation but stuck at the very start Why author is using 10^9 as base instead of 10? In this own words:

As you think the decimal conversion is most complicated part, let's stay in a decimal based mode. For efficiency, we'll store not real decimal digits, but work in base 1 000 000 000 = 10^9 < 2^30. This fits in a Java int (up to 2^31 or 2^32), and the product of two such digits fits nicely in a Java long.

Secondly I could not understand this step:

int decLen = decimal.length(); int bigLen = (decLen-1) /
BASE_DECIMAL_DIGITS + 1;

This strange formula is a Java int way of writing bigLen = ceil(decLen/BASE_DECIMAL_DIGITS). (I hope it is correct, we'll later test it.)

Community
  • 1
  • 1
Walt
  • 1,426
  • 2
  • 17
  • 30
  • 1
    It appears to me that using 10^9 as a base makes it easier to handle large numbers while taking up less space, kind of like how binary(base 2) is often represented in hexadecimal(base 2^4). No idea about that second part though. – DaaaahWhoosh Jan 15 '15 at 18:05
  • http://stackoverflow.com/a/5318896/763029 – Caffeinated Jan 15 '15 at 18:05

1 Answers1

1

Using what we would consider a natural base, such as 10, leads to lots of operations. Have you ever multiplied two 9-digit numbers? Using a method that we typically learn in school, that would involve 81 digit multiplications. However, Java would use one multiply instruction.

What about large numbers, such as 18-digit numbers? For us, that would involve 324 digit multiplications. Here, the implementation would use 2 ints, equivalent to multiplying 2-digit numbers for us. That would result in 4 multiplication instructions for Java.

Why not use a larger base in Java, to further reduce the number of operations? Because of multiplication. It is guaranteed that the result of multiplying two ints in Java will fit in a long, and 1 billion (10^9) is the largest power of 10 that fits in an int. These operations are still very easy for Java - just multiply instructions. It is possible to use a somewhat larger number, such as 2 billion, or Integer.MAX_VALUE (slightly over 2 billion), but that answer chose to use 1 billion, for human readability purposes. Anything larger than Integer.MAX_VALUE would require something with larger ranges, but that's what the answer is already trying to do.

Also, using less ints in the representation saves on memory usage.

The code

int decLen = decimal.length();
int bigLen = (decLen-1) / BASE_DECIMAL_DIGITS + 1;

attempts to determine how many ints are needed in the internal representation to store the incoming number as a String representation. It's 9 decimal digits per int. I would have used Math.ceil( (double) decLen / BASE_DECIMAL_POINTS).

rgettman
  • 176,041
  • 30
  • 275
  • 357
  • 1
    for your `ceil()` call to work, you have to first coerce one of the arguments to a double. – jtahlborn Jan 15 '15 at 18:14
  • Can you please explain the following part with an example ? What about large numbers, such as 18-digit numbers? For us, that would involve 324 digit multiplications. Here, the implementation would use 2 ints, equivalent to multiplying 2-digit numbers for us. That would result in 4 multiplication instructions for Java. – Walt Jan 16 '15 at 10:27
  • 1
    @Walt Consider 222,222,222,222,222,222 times 222,222,222,222,222,222 (18 2s each). For us, that would involve multiplying `2` by `2` 324 times (18^2) -- one for each `2` in the first number and for each `2` in the second number. But for this implementation, it would multiply 222,222,222 4 times (2^2), one for each of the two `222222222`s in the first number and for each of the two `222222222`s in the second number. – rgettman Jan 16 '15 at 17:39