IntegerのgetCharsの52429の意味

Question

JavaのIntegerのgetCharsメソッドの52429の数字の意味が分かりません。
(※コードはjdk8から抜粋。)

static void getChars(int i, int index, char[] buf) {
        int q, r;
        int charPos = index;
        char sign = 0;

        if (i < 0) {
            sign = '-';
            i = -i;
        }

        // Generate two digits per iteration
        while (i >= 65536) {
            q = i / 100;
        // really: r = i - (q * 100);
            r = i - ((q << 6) + (q << 5) + (q << 2));
            i = q;
            buf [--charPos] = DigitOnes[r];
            buf [--charPos] = DigitTens[r];
        }

        // Fall thru to fast mode for smaller numbers
        // assert(i <= 65536, i);
        for (;;) {
            q = (i * 52429) >>> (16+3);//openjdk9
            r = i - ((q << 3) + (q << 1));  // r = i-(q*10) ...
            buf [--charPos] = digits [r];
            i = q;
            if (i == 0) break;
        }
        if (sign != 0) {
            buf [--charPos] = sign;
        }
    }

上記のコードの中にある、52429を導出する公式や原理を教えて頂きたいです。

Javaをご存知の方教えてください。

Comments

[swordone]

そもそもこれはどこのメソッドで何をするメソッドなのですか？「IntegerのgetChars」ということですが、java.lang.Integerクラスにはこのようなメソッドは存在しません。

[退会済みユーザー]

publicメソッドではないので、apiではありません。アクセスレベルもデフォルトです。そもそも、これがどこのメソッドでなにをするメソッドなのか分からないひとは、答えなくていいですよ。説明した所で答えられないでしょう。

Answer 1

「10で割る」ではなく、「0.1を掛ける」と考えてみましょう。
さらにシフト演算を利用すべく、「整数を掛けてシフトする」という計算をします。
その際の誤差を小さくするため、最初に掛ける整数の有効数字の桁数なるべく多くとります。
この作業の段階で対象の数字は16ビット以下なので、16ビットまでの整数であれば、
掛けても(符号なし整数の範囲で)オーバーフローしないということになります。
なので、整数部を16ビット取るように0.1の二進表記を変形します。

十進数の0.1は二進法では0.00011001100110011001100...(2)なので、
0.00011001100110011001100...(2)
=0.11001100110011001100...(2)*2^-3 (小数首位まで0を指数表記に移す)
=1100110011001100.1100...(2)*2^-(3+16) (16ビットの有効数字を取るため16桁分指数に移す)
となります。「*2^-(3+16)」の部分は(3+16)ビットだけ右シフトと考えられるので、
1100110011001100(2)を掛けて19ビット下げれば、結果的に10で割ったことになります。
ただし、1100110011001100(2)では0.1倍に満たず、10の倍数などの場合は切り捨てが起きて
0.1倍より1小さい値が出てしまう可能性があります。
そのため掛ける数を1増やし、1100110011001101(2)にしているのでしょう。
これを10進数に直すと、52429になります。

Comments

[退会済みユーザー]

swordoneさん、ご丁寧にご回答ありがとうございます。

しかし、この答えは本質ではありません。
例えば、何故、16+3だけ、左シフトさせることにしたのでしょうか。
swordoneさんの解説では、16+2や16+1でも、いいことになってしまいます。
しかし、意図時に52429を選択し、結果的に16+3シフトさせることになったと考えています。
ですので、52429の導出過程を知りたいのです。
コードにも参考論文がかいてあります。
Division by Invariant Integers using Multiplication
です。これを、必要な部分だけ抜き取り、公式だけでもいいのです。

どうか、教えてください。

[swordone]

>例えば、何故、16+3だけ、左シフトさせることにしたのでしょうか。
誤差をなるべく小さくするためと考えます。誤差を小さくするには、掛ける数の有効数字の桁数を多く取ることです。
回答中にも書きましたが、掛ける対象の数は最高で16ビットの可能性があるため、符号なし整数の範囲で考えれば16ビットまでの掛け算であればオーバーフローせず計算できることになります。
その最大限の16ビットを有効数字として取るため、16+3だけシフトすることにしたのです。
16+2ビット(私としては3+15ビット)とした場合は有効数字が15ビットとなるため、精度が落ちます。

[swordone]

最初に16ビット以下に抑える計算をしているのもおそらくこのためですね。
仮に17ビットの数で同じことをしようとすると、最大で15ビットの有効数字しか取れません。
掛け算によって16ビット目に誤差が生じるため、正確に10分の1できないのです。

[退会済みユーザー]

おかげ様で、大変良くわかりました。
腑に落ちました。

最後まで付き合って頂き
ありがとうございます。
勉強になりました。
また、お願い致します。

Answer 2

JDK 8までのIntegerクラスにて、
1994年の当時は有効であったであろう手動最適化コードです。

JDK-8136500にてコードの内容が修正済みです、openjdkのJava 9ではそのようなコードはなくなっています。

Comments

[退会済みユーザー]

親切に教えてくださり。ありがとうございます。

やはり、JVMが頭がよくなったからですかね。
aws Lambdaの実装中で、lambdaがJava8までしか対応していなく、
Java8のソースだということを忘れてしまってました。
質問を、ついでに修正しました。

Answer 3

http://techtipshoge.blogspot.jp/2013/09/integergetchars.html
こういうことらしいですね。

Comments

[退会済みユーザー]

この記事を理解されていたら、説明してくださいませんかね。
質問する前に、これ見たんですけど、理解できませんでした。

Answer 4

オーバーフロー対策

int i,q;
		
i = 30;
q = (i * 52429) >>> (16+3);
System.out.println(q); // 3

i = 323;
q = (i * 52429) >>> (16+3);
System.out.println(q); // 32

i = 3;
q = (i * 52429) >>> (16+3);
System.out.println(q);　// 0

Comments

[退会済みユーザー]

オーバーフロー対策にはなっていないですよね。

間違いなく、パフォーマンスを意識したコードをかいています。
除算を乗算に直すさいに如何にして、
52429
を導いたのかがわからないのです。
教えてください。