日記」カテゴリーアーカイブ

ECMAScriptでのいくつかの数学関数の実装

C言語をはじめとする多くのプログラミング言語には、exp, log, sqrt などの指数、対数、平方根の関数や、 cos, sin, tan などの三角関数、cosh, sinh, tanh などの双曲線関数が備わっている。これらの数学関数はECMAScript (JavaScript)からは、Mathオブジェクト経由で Math.expMath.cos などのようにアクセスできる(が、現状ECMAScriptには双曲線関数はない)。

さて、C99でこれらに加えて、acosh, asinh, atanh などの逆双曲線関数や、expm1log1p などの「精度を意識した」関数などが追加された(expm1は\(\exp x-1\), log1p は \(\log(1+x)\) を計算する関数である)。これらの関数をECMAScriptで使うにはどうすればいいか?

ECMAScriptの次期標準であるECMAScript 6では、双曲線関数 Math.(cosh|sinh|tanh) や、C99で追加された関数に対応する Math.(acosh|asinh|atanh)Math.expm1, Math.log1p が入るらしい(Firefoxなどでは既に実装されている)。しかし、ECMAScript 6に非対応の環境では、これらの関数は自前で実装するしかない。

幸い、双曲線関数は指数関数で書ける。よって、例えば Math.sinh はECMAScriptに既に存在する Math.exp 関数を使って次のように書ける:

[sourcecode lang=”js”]
Math.sinh = Math.sinh || function(x) {
return (Math.exp(x)-Math.exp(-x))/2;
};
[/sourcecode]

Mozillaのサイトにも代替コード(Polyfill)として同じようなコードが載っている。めでたしめでたし。

といいたいところだが、精度を気にする場合はそうはいかない。例えば、\(x\) にとても小さい数、例えば \(x=10^{-20}\) を代入してみるとどうなるだろうか。\(\sinh\) のテーラー展開\[
\sinh x=x+\frac{x^3}{3!}+\cdots
\]を考えると(\(x^3\) は微小なので無視して)値はおおよそ \(x=10^{-20}\) と一致するはずである。この場合、ECMAScriptの「数」はIEEE754の64bit浮動小数点数で、精度は53bitしかないため、\(x\) が十分に小さければ \(x+\frac{x^3}{3!}+\dots\) は完全に \(x\) と一致する。

一方、指数関数のテーラー展開は\[
\exp x=1+x+\frac{x^2}{2!}+\cdots
\]で、今書いたのと同じ理由で Math.exp(x)Math.exp(-x) は完全に 1 と等しくなる。従って、さっき実装したオレオレ Math.sinh は0を返す。情報落ちだか桁落ちだか忘れたが、なんかそういう現象が起こっている。これは理想的とはいえない。ちなみに、C言語の sinh はこの場合「正しい」 \(10^{-20}\) を返す。

同様に、Math.expm1 を次のように愚直に実装しても、同じ問題が発生する。

[sourcecode lang=”js”]
Math.expm1 = Math.expm1 || function(x) {
return Math.exp(x)-1;
};
[/sourcecode]

では、どうすれば \(x\) が小さい時でも「正しい」答えを出す expm1 関数を作れるか?(双曲線関数よりも指数関数の方が単純なので、以後こちらを議論する)

まあ単純な答えとしては、 \(x\) が小さいときに関数のテイラー展開を使って多項式として計算してやれば良い。さっきのように \(x=10^{-20}\) とかだと1次近似で \(x\) そのものを返してやればよかったが、この近似は \(x\) がどのぐらい小さければ問題ないのか?あるいは、近似の次数をどのぐらい増やしてやれば誤差はどれぐらい小さくなるか?

仮に、\(\exp x\) を \(n\) 次の多項式で近似するとしよう。すると、真の値(無限級数で表される)との差は\[
\left\lvert(\text{差})\right\rvert=\left\lvert\exp x-1-\sum_{k=1}^{n}\frac{x^k}{k!}\right\rvert=\left\lvert\sum_{k=n+1}^{\infty}\frac{x^k}{k!}\right\rvert
\]となる。これを適当に評価してやれば良い。実際にやってみると、例えば次のようになる。\begin{align*}
\left\lvert(\text{差})\right\rvert=\left\lvert\sum_{k=n+1}^{\infty}\frac{x^k}{k!}\right\rvert
&\le\sum_{k=n+1}^{\infty}\frac{\lvert x\rvert^k}{k!} \\
&=\frac{\lvert x\rvert^{n+1}}{(n+1)!}\sum_{k=0}^{\infty}\frac{\lvert x\rvert^k}{(n+2)\cdot\dots\cdot(n+k+1)} \\
&\le\frac{\lvert x\rvert^{n+1}}{(n+1)!}\sum_{k=0}^{\infty}\frac{1}{(n+2)^k} \quad (\left\lvert x\right\rvert <1\text{を仮定}) \\
&\le\frac{\left\lvert x\right\rvert^{n+1}}{(n+1)!}\frac{1}{1-\frac{1}{n+2}} \\
&\le\frac{\left\lvert x\right\rvert^{n+1}}{(n+1)!}\frac{n+2}{n+1}=\frac{(n+2)\left\lvert x\right\rvert^{n+1}}{(n+1)(n+1)!}
\end{align*}
では、どういうときに \(n\) 次の多項式近似の値を使ってよいかというと、近似値 \(\sum_{k=1}^{n}\frac{x^k}{k!}\) の大きさに対してこの \(\left\lvert(\text{差})\right\rvert\) の大きさが(精度が53bitの浮動小数点数の場合は) \(2^{-53}\) よりも小さければ確実に問題ない(十分条件)。つまり\begin{align*}
\left\lvert\frac{(\text{差})}{\sum_{k=1}^{n}\frac{x^k}{k!}}\right\rvert<2^{-53}
\end{align*}だ。この左辺をもうちょっと分かりやすい形で評価すると
\begin{align*}
\left\lvert\frac{(\text{差})}{\sum_{k=1}^{n}\frac{x^k}{k!}}\right\rvert&\le\left\lvert\frac{(\text{差})}{x}\right\rvert \\
&=\left\lvert\frac{1}{x}\frac{(n+2)\left\lvert x\right\rvert^{n+1}}{(n+1)(n+1)!}\right\rvert \\
&=\frac{(n+2)\left\lvert x\right\rvert^n}{(n+1)(n+1)!}
\end{align*}
となる(書いた後に気付いたが、最初の行の評価が \(x<0\) のときにマズい気がする)。つまり、\(n\) 次近似を使っても良い十分条件として\[
\frac{(n+2)\left\lvert x\right\rvert^n}{(n+1)(n+1)!}<2^{-53},
\]すなわち\[
\left\lvert x\right\rvert<\sqrt[n]{\frac{(n+1)(n+1)!}{n+2}2^{-53}}
\]が得られる。

例えば、\(n=3\) として右辺を計算すると \(1.286976\ldots\times 10^{-5}\) が得られるので、さっきのオレオレ Math.expm1 の実装は

[sourcecode lang=”js”]
Math.expm1 = Math.expm1 || function(x) {
if (Math.abs(x) <= 1.28e-5) {
return x*(1+x/2*(1+x/3));
} else {
return Math.exp(x)-1;
}
};
[/sourcecode]

のように改良できる。

まあ、改良したと言っても所詮お遊びで、実際のC言語のライブラリの実装はこんな適当なコードよりもちゃんとやっているので、真面目にやりたい人はC言語のライブラリの実装を移植しよう。

Math.expm1 の他に、Math.log1p, Math.sinh, Math.tanh, Math.asinh, Math.atanh あたりの関数を実装する時にも同じような(小手先の)テクニックが使える。

ところで、MDNに載っている Math.tanh のPolyfillに問題があるのを見つけた。MDNのPolyfillでは xInfinity かどうかを関数の最初でチェックしているが、xInfinity でなくても Math.exp(x)Infinity になる場合を考慮していない。その結果、Math.tanh(x) に 1 を返してほしいのに実際には NaN が返ってくる場合がある。

最後に全く関係ない話だが、プログラミング言語Luaは標準ライブラリに math.sinh などの双曲線関数を計算する関数(中ではC言語のライブラリ関数を呼び出す)を持っている。しかし、どうやら将来的にはこれらの双曲線関数を標準ライブラリから外すようだ(次期バージョン5.3でdeprecated扱い)。理由として作者は「あまり使われていない」「必要なら mathx などの外部ライブラリを使えば良い」としている(この記事に書いた理由により、「math.exp で実装できる」は理由にならない)。ECMAScript と Lua はよく似ていると言われる事が多いが、一方がWebの世界のアセンブラとなるべく数学関数・浮動小数点数関係の関数を追加しようとしているのに対し、もう一方はそれを削減しようとしているのは対照的だと思った。(まあ筆者自身はLuaを活発に触っていたのは5.1時代の事で、5.2が出て以降はあまり触っていないので、ぶっちゃけどうでもいいのだが)

八元数について

最近、八元数を勉強しなければならないという電波を受信したので、とりあえず八元数のさわりだけ勉強する事にした。

複素数をさらに拡張したような数の体系として、八元数の前に四元数がある。四元数は3次元や4次元の回転(特殊直交行列; \(SO(3)\),\(SO(4)\))と深い関わりがあるので、以前から(高校生の頃に)勉強して知っていた。四元数の積はノルムを保つため、単位四元数の積によって3次元球面 \(S^3\) にリー群の構造が入る。

八元数も、積がノルムを保つように定義されている。しかし積が結合的ではないため、群にはならない。いまいち勉強するモチベーションが起こらなかったのもその辺に理由がある気がする。

今参照している本はJohn H. ConwayとDerek A. SmithのOn Quaternions and Octonions: Their Geometry, Arithmetic, and Symmetryという本である。

複素数は1個(\(i\))、四元数は3個(\(i,j,k\))の直交する虚数単位があったが、八元数にはそれが7個ある。それを \(i_0,\dots,i_6\) で表す事にしよう。これに、「実数方向」の基底 \(1\) を加えると、八元数の \(\mathbf{R}\) 上線形空間としての基底 \(1,i_0,\dots,i_6\) ができる。

この基底を使うと、任意の八元数 \(x\) は次のように書ける:\[x=x_\infty+x_0i_0+x_1i_1+x_2i_2+x_3i_3+x_4i_4+x_5i_5+x_6i_6\]ただし、\(x_*\) は実数である。ノルムは普通の実数のノルム\[\left\lVert x\right\rVert^2=x_\infty^2+\sum_{n=0}^6 x_n^2\]とする。八元数の乗法をうまいこと定めてやると、2つの八元数 \(x\),\(y\) の積がノルムを保つ\[\left\lVert x\cdot y\right\rVert=\left\lVert x\right\rVert\cdot\left\lVert y\right\rVert\]ようにできる。どう定めるかというと、1以外の基底 \(i_n\) について\begin{align*}
i_n^2&=-1, \\
i_{n+1}i_{n+2}&=i_{n+4}=-i_{n+2}i_{n+1}, \\
i_{n+2}i_{n+4}&=i_{n+1}=-i_{n+4}i_{n+2}, \\
i_{n+4}i_{n+1}&=i_{n+2}=-i_{n+1}i_{n+4}
\end{align*}となるようにするらしい。ここで、\(n\) は整数を動き、添字は0から6に収まるように適宜 mod 7 で考える。

ということなのだが、この積の定義で本当にいいのか?本の記述を読み違えたとかいう可能性はないか?不安なので、積がノルムを保存することを確かめることにしよう。

続きを読む

ベクトル束のテンソル積

ベクトル束のテンソル積には2種類ある。

一つ目。\(E\to M\), \(F\to N\) をそれぞれ \(K\)-ベクトル束とする。このとき、\[\bigsqcup_{(x,y)\in{M\times N}} {E_x\otimes F_y}\]は \(M\times N\) 上のベクトル束となる。底空間は直積 \(M\times N\) となる。

二つ目。\(E\to M\), \(F\to M\) をそれぞれ \(K\)-ベクトル束とする。一つ目の場合は底空間が異なる場合も許したが、ここでは底空間は同じものを考えることに注意しよう。このとき、\[\bigsqcup_{x\in M} {E_x\otimes F_x}\]は \(M\) 上のベクトル束となる。底空間は \(M\) のままである。

最初に読んだ本では二つ目のやつを \(E\otimes F\) で表していたが、今読んでいる本は一つ目のやつを \(E\otimes F\) と書いて、二つ目のやつは \(E\mathop{\hat{\otimes}}F\) で書いていた。これに気づかないで読み進めたためにひどい目にあった(ちゃんと注意して読めという話だが)。

個人的には、二つ目の方を \(\otimes\) で書くのがいいかなあと思うが(この分野の最近の傾向を知らないのでアレだが)、じゃあ一つ目のテンソル積を書く必要があるときはどうするの、という話だ。どうしよう。

MyOPACの使い勝手を上げるGreasemonkeyスクリプト

東大図書館のMyOPACというサービスがあるが、このログインページも良くない作りをしていて、良くない。

IDとパスワードの入力欄でリターンキーでログインできるのはUT-mateよりも優秀と言えるのだが、この挙動をサブミットボタンではなくてJavaScriptでイベントを捕捉することにより実装しているため、

  1. ブラウザが補完候補を表示
  2. 表示された候補をリターンキーで確定しようとする
  3. フォームのサブミットが行われる(正確には、サブミット前に行われるチェックで、パスワード欄が空白だというエラーが出る)

という、ブラウザの補完機能に頼っている人にとっては微妙に使い勝手が悪いことになる。UT-mateの時も思ったが、こういうフロントエンドを作ってる人は頭が悪いのか。ログインボタンは普通にHTMLのサブミットボタンで書いて、JavaScriptを使うのはフォームの検証にとどめておけばいいものを…。

というわけで、この挙動を修正するGreasemonkeyスクリプトを書いた→Better_MyOPAC.user.js

GreasemonkeyをインストールしたFirefoxを使っている人ならば、上のリンクをクリックすることでインストールできる。

今はログインページの修正だけだが、今後他のページもいじりたくなったら機能を追加するかもしれない。

関連:UT-mateの使い勝手を上げるGreasemonkeyスクリプト

Five LemmaのダイアグラムチェースをするWebページを作った

最近、Webの標準技術であるSVGとMathMLを組み合わせて、Webページ上で数学の図式などを表現できないかと考えている。

このブログでもたまに図式や証明図を載せているが、今までのは画像として貼り付ける形だった。静的なコンテンツならこれでもいいのだが、JavaScriptを使ってインタラクティブなコンテンツを作ろうとした時に、画像では動的に内容を変えるというようなことがやりにくい。そこで考えられるのが、Web標準技術のSVGやMathMLといった、HTMLやJavaScriptと相性のいい技術を使って数学の図式を記述するということである。

SVGは基本的に図を記述する言語で、MathMLは数式を記述する言語だが、ブラウザが対応していれば、SVGの図の中にMathMLを埋め込むことは難しくない。だが、数式の幅、高さを見ながら図のレイアウトを決めてやるのは正直楽しい作業ではない。JavaScriptを使えば、ブラウザがレンダリングした数式の大きさを見て適切に位置を合わせるということができるだろう。また、JavaScriptを使えば、ユーザーのクリックに反応して数式を変えたり、色を変えたりできるだろう。

SVGは最近のブラウザならだいたい対応しているが、MathMLのブラウザ側の対応はまちまちである。Firefoxはかなり昔からMathMLに対応していた。Safariは最近対応したようだが、筆者はあまり触っていない。Chromeは、数年前に見聞きした話では対応する意思がないらしい。

という感じで、とりあえず作る時はFirefoxで表示させることを優先させる。Safariは余力があれば対応させたい。Chromeは知らん。

というわけで、そういうのを実験的に実装してみた。このページは、みなさんお世話になっているであろう圏論的な直積の図式を表現している。

直積の図式を表示てきたはいいものの、これは動きがない。ユーザーの操作によって表示が変わるようなものを作ろう。というわけで、Five Lemmaのダイアグラムチェースによる証明(真ん中の射がmonicであることを示す)をするページを作った。クリックするとダイアグラムチェースが進む。かなりやっつけな書き方をしているので、例えばAndroid上のFirefoxでは表示が崩れた。Safariでは文字が途切れる。JavaScriptのソースコードもかなり汚い。改善の余地は大きいだろう。

演算子オーバーロードのないJavaScriptであまり複雑なことをしても記述性が悪い。例えばHaskellのような言語で記述してJavaScriptにコンパイルするという手順を取ると良いのかもしれない。

The middle 3×3 lemma

先週に続いて、Categories for the Working MathematicianのAbelian Categoriesの章で勉強している。

ExercisesのThe middle 3×3 lemmaを証明しようとしたのだが、どうにも証明できそうにない。Nine lemma 1問題文曰く、上の図式の全ての列、それに第一行と第三行が短完全列ならば第二行も短完全列であることを証明せよ、だそうだ。与えられた短完全列の両端に0を付加すると次の図式になる。
Nine lemma 2

手始めに、真ん中の行の2つの射を合成すると0となることを証明しようとしたが、どうにも方法が浮かばない。先週は勘違いでさんざん悩んだので、これはもしや成り立たないのではないか、と思って、調べてみることにした。(反例を考えるのは面倒くさかった)

手持ちの別の本を参照したところ、真ん中の行の2つの射を合成すると0となることは仮定しなければならないそうである。反例もあった。ググって出てきたnLabの項にも書かれていた。

アーベル圏を勉強している

せっかく作ったブログをいつまでも放置するのもアレなので、最近勉強していることを書くことにする。

先学期の授業で登場したけど全然理解しないまま終わったホモロジーとかを理解したくて、どうせやるならと思ってアーベル圏の勉強をしている。本はCWMの、アーベル圏の章を進めている。

アーベル圏というのはどういう圏のことを言うのかというと、単純なものから順に定義を書いておくと

Preadditive category (前加法圏)

各 hom-set にアーベル群の構造が入っていて、射の合成が bilinear になっている圏を preadditive category という。CWMでは Ab-category と呼んでいる。

Kernel, cokernel や biproduct などの概念を定義することができる(kernel, cokernel は preadditive category でなくても、ゼロ射さえあれば定義できる)。

Additive category (加法圏)

Preadditive category であって、ゼロ対象と biproduct (直和) をもっている圏を additive category という。

Abelian category (アーベル圏)

Additive category であって、全ての射が kernel と cokernel を持っていて、全ての monic 射が kernel であり、全ての epi 射が cokernel である圏を abelian category という。

Abelian category では、射の image や coimage の概念を定義することができる。また、完全列の概念も定義できる。

…という風になる。

アーベル圏で完全列を定義できるということは、five lemma とか snake lemma を定式化できるということである。この辺のレンマの証明は、CWMではアーベル圏の章のセクション4に書かれている。

このセクションの最初の方にアーベル圏 A の短完全列の圏 Ses A が加法圏であるとさらっと書かれているが、最初に読んだときに Ses A もアーベル圏なんだと勘違いして証明を考えるのに数週間費やしてしまった。おかげで図式の扱いには慣れた気がするし、短完全列の射のカーネル、コカーネルがどうなるのかという話はスネークレンマに繋がってくるとはいえ、とんだ時間の浪費だった。

アーベル圏を勉強する前は、授業などでこれらの補題の証明にいわゆる “diagram chase” を使っているのを見て(加群の圏上ではあったが)、
「元を取ってdiagram chaseなんてしたら圏論的な証明にならないのでは!?」
と思っていたが、蓋を開けてみたら、一般のアーベル圏上で「元」に相当する概念を定義して、その「元」に対して monic や epi がそれぞれ普通の単射、全射と同じような振る舞いをすることを証明し、five lemma や snake lemma などの補題の証明では元を取って証明していたのだった。もちろん、圏論的な証明であるから、「dual を取って証明の半分を省略する」というようなことはできる。

UT-mateの使い勝手を上げるGreasemonkeyスクリプト

東大の後期課程や大学院に在籍する人は必ずお世話になるであろうUT-mateだが、その使い勝手はお世辞にも良いとは言えない。まず、ログイン画面でEnterキーを押してもログインできない。他にもいろいろある。

さて、世の中のWebブラウザには、ユーザー側でWebページの見た目とか使い勝手をいじくれるものがある。Firefoxの場合はGreasemonkeyという拡張機能をインストールすれば、そういう”user script”を導入できるようになる。つまり、Greasemonkeyを導入したFirefoxであれば、user scriptによってUT-mateのページを構成するHTMLとかをいじることができ、使い勝手を向上させられる可能性があるということだ。(他のブラウザは筆者はあまり使っていないのでこの記事では扱わない)

というわけで私が書いたuser scriptがこれ→Better UT-mate.user.jsになる。Greasemonkeyを導入済みであれば、このリンクをクリックすることでこのuser scriptをインストールできるはずだ。ソースを見れば分かる通り、至極簡単なスクリプトであって、怪しい動作はしない。

現在のところ、実装している機能は

  • Enterキーでログインできるようにする
  • 「シラバス参照」で、Enterキーで「授業科目決定」ボタンや「検索開始」ボタンを押せるようにする
  • 【2014年9月30日更新】タイムアウトを阻止

である。気が向いたらさらに機能を追加するかもしれない。

【2015年9月3日】GitHubに公開。user scriptへのリンクをGitHubのものへと変更。