How does the getChar function work?
private static char[] getChars(int i) {
char buf[] = new char[32];
int q;
for (int j = 31; j >= 0; j--) {
q = (i * 52429) >>> (19);
int r = i - ((q << 3) + (q << 1));
buf[j] = (char) (r + '0');
i = q;
if (i == 0)
break;
}
return buf;
}
The above code is based on the java.lang.Integer.getChars (int) part. How did the developers come up with this "magic" number 52429. What is the math behind this? After entering 81920, this function does not work. does this magic number only for a certain range of inputs, if so why?
+3
source to share
1 answer
If you are looking for the source code, you will find a second instance of this number:
// I use the "invariant division by multiplication" trick to // accelerate Integer.toString. In particular we want to // avoid division by 10. // // The "trick" has roughly the same performance characteristics // as the "classic" Integer.toString code on a non-JIT VM. // The trick avoids .rem and .div calls but has a longer code // path and is thus dominated by dispatch overhead. In the // JIT case the dispatch overhead doesn't exist and the // "trick" is considerably faster than the classic code. // // TODO-FIXME: convert (x * 52429) into the equiv shift-add // sequence. // // RE: Division by Invariant Integers using Multiplication // T Gralund, P Montgomery // ACM PLDI 1994 //
So, the answer to your question can be found in the book Pruning by Invariant Integers Using Multiplication by TGralund, Montgomery, R.
+5
source to share