ぎるばーとのノート

もっともっと遠くへ行きたい　空が広く見える場所まで

Javaの知られざる構文〜幻のfor-while文

コンピュータ Java

【この記事はジョーク記事です！】

　この件に関連して……。

　あまり知られていないのだけど、初期のJavaに、for文とdo-while文を組み合わせたfor-while文というのがありました。いつ頃からか、言語規定に載らなくなりましたが、最新版でもコンパイル・実行が可能です。

// for-while文の例
int i;
for (i = 0; i < 5; i++) {
    System.out.println(i);
} while (i < 5);

　iはメモリに記憶されますが、ループ判定のタイミングでCPU内のレジスタに読み込まれます。

　宇宙空間や過酷な放射線環境下で使用する機器では、メモリは放射線対策していることが多いですが、CPUは特に何でもないものを使ったりするそうです。そこで、CPU内のビット反転に対する耐性を高めたい場合に使用できる構文ということだったのですが……。
　うーん、可読性や保守性が悪すぎたのか……。幻の構文となってしまいました。





　……信じましたか？(^^;

　「種明かし」しましょう。上のコードは、for文の後ろに「中身が空っぽ」のwhile文が続いているだけです。つまり、

// for-while文の例
int i;
// for文
for (i = 0; i < 5; i++) {
    System.out.println(i);
}
// while文
while (i < 5)
    ;

　まあ、いくら何でもそんな変な構文あるわけないですね！（信じてしまった方は、悪意の人間に騙されないよう気をつけて……。）

Stirlingの近似式

数学・統計学

　Stirlingの近似式は、大きな数の階乗を見積もることができます。
\ln n! \simeq n \ln n - n \tag{1}
　この式は「両辺の比が1に収束する」という意味です。もっと強く、「両辺の差が0に収束する」近似式は次の通り。
\ln n! \simeq n \ln n - n + \frac{1}{2} \ln 2\pi n \tag{2}

　ところで、階乗の定義域を実数に広げたものはガンマ関数で、
\Gamma(x) = \int_0^\infty t^{x-1}e^{-t} dt
\Gamma(n + 1) = n! = 1 \times 2 \times 3 \times \cdots \times n
　ガンマ関数の対数をとって微分するとディガンマ関数になります。
\psi(x) = \frac{d}{dx} \ln \Gamma(x) = \frac{\Gamma'(x)}{\Gamma(x)}
　ディガンマ関数は調和級数の拡張版といったところ。nが非負整数なら、
\psi(n + 1) = -\gamma + H_n = -\gamma +1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}
　式中の\gammaは有名なEulerの定数です。これも語りたいことはあるけれど、また別の機会に……。（たぶん

　話を元に戻しまして、Stirlingの式(1)の両辺をnで微分してみます。
　左辺は、
\frac{d}{dn} \ln n! = \frac{d}{dn} \ln \Gamma(n + 1) = \psi(n + 1)
　右辺は、
\frac{d}{dn} (n \ln n - n) = \ln n
　ディガンマ関数と対数関数が出てきました！　この二つは興味深い関係がたくさんありますが、発散する速さに注目すると、
\lim_{n \to \infty} \{\psi(n + 1) - \ln n\} = 0
　つまり同じ速さで発散します。（1を任意の実数\alphaに変えても同じ。）

　下の図はディガンマ関数と対数関数のグラフです。
f:id:zwxadz:20151001214330p:plain

　まとめると、Stirlingの式が示しているのは「階乗の対数（ディガンマ関数の積分）を対数関数の積分で近似できるよ！」ということになります。

超越関数？

数学・統計学

　超越関数にちゃんとした（広く通じる）定義はあるのか、という話。

　なんとなく「代数的数係数の多項式で表せない関数」ぐらいに考えていたけれど、そうすると、
f(x) = \pi x \tag{1}
は超越関数ということに？　それはちょっと違うような気が……。

　日本語版ウィキペディアから調べてみます。
超越関数 - Wikipedia

超越関数（ちょうえつかんすう、英: Transcendental Function）とは、係数が多項式であるような多項式で表せない関数である。より正確に言えば、1変数の関数が超越的であるのは、その変数について代数的独立性がある場合である。

　うーん。「係数が多項式であるような多項式」の意味が分かりません。どういう人向けの説明なんだろう？

　続いて英語版へ。
Transcendental function - Wikipedia, the free encyclopedia

A transcendental function is an analytic function that does not satisfy a polynomial equation, in contrast to an algebraic function. (The polynomials are sometimes required to have rational coefficients.) In other words, a transcendental function "transcends" algebra in that it cannot be expressed in terms of a finite sequence of the algebraic operations of addition, multiplication, and root extraction.

　こちらの方は明快！　超越関数とは多項式を満たさない解析関数で、時々その多項式は有理数係数のものに限定される。
　この定義だと、(1)は文脈によって超越関数に分類してもそうでないとしてもよさそうです。

　次はWolfram Mathworld。
Transcendental Function -- from Wolfram MathWorld

A function which is not an algebraic function. In other words, a function which "transcends," i.e., cannot be expressed in terms of, algebra. Examples of transcendental functions include the exponential function, the trigonometric functions, and the inverse functions of both.

　超越関数とは代数関数でない関数のことで、言い換えると、超越的な関数は代数的に表せない。……これは同語反復じゃないの？？
　ちなみに代数関数は、
Algebraic Function -- from Wolfram MathWorld

An algebraic function is a function f(x) which satisfies p(x,f(x))=0, where p(x,y) is a polynomial in x and y with integer coefficients. Functions that can be constructed using only a finite number of elementary operations together with the inverses of functions capable of being so constructed are examples of algebraic functions. Nonalgebraic functions are called transcendental functions.

　代数関数f(x)は、整数係数の多項式p(x, y)によって、p(x, f(x)) = 0を満たす。
　整数係数は意味的に有理数係数と等価で、もともとの考えに近いです。そして、(1)がはっきり超越関数の側に分類されます。

　どうなんだろうね、これは……。

GCD(0, 0) = ?

数学・統計学

　前回わざと触れなかったところ。

　最大公約数は普通正の数に対して考えますが、実は片方が0でもOKです。
　「すべての整数は0の約数（0を割り切る）」と考えれば、0でないnと0の最大公約数はnになります。
　では、両方とも0の場合はどうすればいいでしょうか？

  • 案A：∞とする

　すべての整数に最大値はないので、∞。または定義しない。
　論理的にはこれが正しいような……。

  • 案B：0とする

　こちらは実用上の便利さを考慮すると捨てがたい案。
　3つ以上の数（うち1つ以上は0でない）の最大公約数を、例えばGCD(a, b, c) = GCD(GCD(a, b), c)として求めることができます。

　案Aは元の定義を重視して、案Bは結合的な二項演算の再定義という感じ？
　コンピュータ用なら、案Bを採用するのが無難かなーと思います。
　（参考：JavaのBigInteger、Commons Math、Guavaなどは案B。）

Binary GCD

コンピュータ Java

　GCDは最大公約数。計算方法としてはユークリッドの互除法が有名です。
　別なやり方もあって、例えばBinary GCDアルゴリズムなんかおもしろいと思うのですが、なぜか日本語での解説が少ない……。
　なら自分で書いて残しておこうかと思ったり。

　Binary GCDアルゴリズムでは次の3つの定理が基本になります。

  1. nとmが両方とも偶数なら、GCD(n, m) = 2*GCD(n/2, m/2)
  2. nが偶数でmが奇数なら、GCD(n, m) = GCD(n/2, m)
    同じようにnが奇数でmが偶数なら、GCD(n, m) = GCD(n, m/2)
  3. nとmが共に奇数でn > mなら、GCD(n, m) = GCD(n - m, m)
    同じようにnとmが共に奇数でn < mなら、GCD(n, m) = GCD(n, m - n)

　証明は略。（面倒……

　アルゴリズムの本体を文章に直して書くと次の通り。

  1. nとmのどちらかが奇数になるまで2で割る（回数kを記録しておく）
  2. 残りの側も奇数になるまで2で割る（定理2）
  3. 以下、n = mになるまでくり返し
    • n > mのとき、
    1. nにn - mを代入（定理3）
    2. nが奇数になるまで2で割る（定理2）
    • n < mのとき、
    1. mにm - nを代入（定理3）
    2. mが奇数になるまで2で割る（定理2）
  4. 最後にnに2kを掛けて終わり！（定理1）

　互除法と比べると、特に任意精度整数（BigInteger）で除算を避けられる*1のがメリットらしいです。（それなら、CPUで除算できる普通の整数型では大差ないのかも？）

　Javaで書くとこうなります。ちょっとトリッキーな部分あり。

public static int gcd(int n, int m) {
    // 負の数はダメ
    if (n < 0 || m < 0) throw new ArithmeticException();
    // GCD(0, m) = m; GCD(0, 0) = 0
    // GCD(n, 0) = n
    if (n == 0 || m == 0) return n + m;
    // ここから
    int k = Integer.numberOfTrailingZeros(n | m);
    n >>= Integer.numberOfTrailingZeros(n);
    m >>= Integer.numberOfTrailingZeros(m);
    while (n != m) {
        if (n > m) {
            n -= m;
            n >>= Integer.numberOfTrailingZeros(n);
        }
        else {
            m -= n;
            m >>= Integer.numberOfTrailingZeros(m);
        }
    }
    return n << k;
}

（最初から最後までnumberOfTrailingZerosだらけ！）

*1:2で割るのはシフト演算で済むから。