CODEWITHSUNDEEP
javaalgorithmbinary
user282909
user282909

Reputation: 135

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 a part of java.lang.Integer.getChars(int). How did the developers come up with this "magic" number 52429. What is the math behind it? After 81920 as input this function doesn't work. does this magic number only work for a certain range of inputs, if so why?

Upvotes: 3

Views: 311

Answers (1)

Andreas
Andreas

Reputation: 159086

If you search the source code, you'll find a second instance of that 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 Division by Invariant Integers using Multiplication by T Gralund, P Montgomery.

Upvotes: 5

Related Questions