ぎるばーとのノート

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

逆正弦乱数

数学・統計学

physnotes.jp

　逆正弦分布（アークサイン分布）という確率分布があるのを、高校物理の備忘録さんの記事で知りました。記事の後半の逆正弦法則の話もとても興味深いです。

　振り子の速度は最低点で最大、両端では0になります。なので、最低点付近にいる時間は短く、両端付近にいる時間が長くなり、ランダムなタイミングでチラッと見たときの位置は逆正弦分布に従います。

Arcsine distribution - Wikipedia, the free encyclopedia
　逆正弦分布(0,1)は、ベータ分布の特別な場合（α=β=0.5）の別名です。この分布の乱数を生成する方法（用途はまったく不明、、）を書き記しておきます。

　Wikipediaにある通り、一様乱数U \sim \text{Uniform}(-\pi,\pi)から、(\sin U)^2とすればいいわけですが、サイン関数を使わずに計算する方法もあります。正規乱数でおなじみのMarsaglia法を応用します。

double randomArcsine() {
    double u, v, s;
    do {
        u = Math.random();
        v = Math.random();
        s = u * u + v * v;
    } while (s >= 1.0 || s == 0.0);
    
    return (u * u) / s;
}

　第1象限で単位円内の点をランダムに選んで、原点からの距離で割ると円周上に分布します。座標を一つとって二乗すると目的の乱数が得られますね。正規乱数の場合のように二つ独立に作れるわけではないのに注意！　(\sin x)^2 + (\cos x)^2 = 1なので……。

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。）