数学」カテゴリーアーカイブ

代数構造の「マグマ」と、定義の動機づけ

マグマ

「マグマ」という代数構造がある。

マグマとは、集合とその上の二項演算の組である。

普通の代数構造だと、二項演算について結合法則や単位元の存在など、なんらかの法則を課すことが多いが、マグマは何の法則も課さない。

続きを読む

整数除算を浮動小数点演算でエミュレートできるか

古典的な(BigInt以前の)JavaScriptは数値型が倍精度浮動小数点数のみでした。5.2までのLuaも同様です。

このような言語で整数除算を行いたい場合は、浮動小数点演算を経由して行うことになります。例えばJavaScriptで32ビット整数の除算をやるならこんな感じです:

// x, yは整数値とする
function Int_div(x, y) {
    return Math.floor(x / y);
}
function Int_quot(x, y) {
    return Math.trunc(x / y);
}
// 0除算やオーバーフローはここでは無視する

さて、浮動小数点演算と言えば誤差です。この「浮動小数点演算による整数除算のエミュレート」は誤差の影響を受けないのでしょうか?

続きを読む

2^53+1 は素数か

ふと \(2^{53}+1\) が素数かどうか気になりました。

短い答え:No

Linuxだと factor コマンドで素因数分解できます。

$ factor $((2**53+1))
9007199254740993: 3 107 28059810762433

macOSだとHomebrewやMacPortsでcoreutilsを入れる必要があります。

筆者のMacには factor コマンドは入っていなかったので、最初はMaximaで確認しました:

$ maxima    
Maxima 5.45.1 https://maxima.sourceforge.io
using Lisp SBCL 2.2.9
Distributed under the GNU Public License. See the file COPYING.
Dedicated to the memory of William Schelter.
The function bug_report() provides bug reporting information.
(%i1) factor(2^53+1);
(%o1)                        3 107 28059810762433

というわけで、 \(2^{53}+1\) は\[2^{53}+1=3\times 107\times 28059810762433\]と素因数分解でき、素数ではありません。

暗算でもできるのでは?

今回調べたいのは \(2^{53}+1\) という形の数です。ちょっと頭を使えば、この数が3で割り切れることがわかります:\begin{align*}2^{53}+1&=2^{53}-(-1)^{53}\\&=(2-(-1))(2^{52}+\cdots+2^{52-i}\cdot(-1)^i+\cdots+(-1)^{52})\end{align*}と因数分解できます。

一般化すると、\(2^{2m+1}+1\)の形の整数はすべて3で割り切れることがわかります。つまり、\(m\neq 0\)で\(2^{2m+1}+1\)が3よりも大きくなる場合はこの形の数はすべて合成数です。

もっと一般化

もっと一般に、\(2^n+1\)の形の整数が素数となるのは\(n=0\)または\(n=2^k\ (k\geq 0)\)の場合に限られます。

\(n=2^k(2m+1)\)とおくと、\begin{align*}2^n+1&=2^{2^k(2m+1)}+1\\&=\left(2^{2^k}\right)^{2m+1}+1\\&=\left(2^{2^k}\right)^{2m+1}-(-1)^{2m+1}\\&=\left(2^{2^k}-(-1)\right)\left(\left(2^{2^k}\right)^{2m}+\cdots+\left(2^{2^k}\right)^{2m-i}\cdot(-1)^i+\cdots+(-1)^{2m}\right)\\
&=\left(2^{2^k}+1\right)\left(\left(2^{2^k}-1\right)\left(2^{2^k}\right)^{2m-1}+\cdots+\left(2^{2^k}-1\right)\left(2^{2^k}\right)^{2(m-i)+1}+\cdots+\left(2^{2^k}-1\right)\cdot 2^{2^k}+1\right)\\
&=\left(2^{2^k}+1\right)\left(\sum_{i=0}^{m-1} \left(2^{2^k}-1\right)\left(2^{2^k}\right)^{2i+1}+1\right)\end{align*}と因数分解できます。

\(k\geq 0\)なので、\(2^{2^k}+1\geq 3\)であり、最初の因数は非自明です。そして、2番目の因数に登場する\(2^{2^k}-1\)は1以上で、\(m\geq 1\)ならば2番目の因数も非自明です。

よって、\(2^{2^k(2m+1)}+1\)の形の数が素数となるのは\(m=0\)の場合に限ることがわかりました。

フェルマー数

\(2^{2^k}+1\)の形の数はフェルマー数と呼ばれています。\(k=0,1,2,3,4\)の場合はこれは素数となり、フェルマー素数と呼ばれています。

ところでなんで \(2^{53}+1\) を調べたかったのか

一部のプログラミング言語では、倍精度浮動小数点数型を唯一の数値型として提供しています。BigInt以前のJavaScriptや、5.2までのLuaなど。

こういう言語では、絶対値が\(2^{53}\)以下の整数は正確に表現できます。そして演算結果の絶対値がそれを超えると、丸めが発生して正しい答えが返ってきません。JavaScriptで試してみましょう:

$ node
Welcome to Node.js v17.9.1.
Type ".help" for more information.
> 2**53 - 1
9007199254740991
> 2**53
9007199254740992
> 2**53 + 1
9007199254740992
> 2**53 + 2
9007199254740994
> 2**53 + 3
9007199254740996

2**53 + 1 を表現できておらず、「表現可能な最も近い値のうち、仮数部の末尾が偶数な方」が表示されています(最近接偶数丸め)。

では、演算結果が「正確に表現できる範囲」を超えたかどうかはどうやったらわかるでしょうか?まず、演算結果の絶対値が\(2^{53}+2\)以上であれば間違いなく超えています。

では、演算結果の絶対値が\(2^{53}\)以下なら結果は正確と言えるでしょうか?否ですね。2**53 + 1 の演算結果は\(2^{53}\)以下であるにも関わらず、不正確です。

一方、演算結果の絶対値が\(2^{53}-1\)以下であれば結果は正確であることが保証されます。この範囲、\([-(2^{53}-1),2^{53}-1]\)はJavaScript界隈ではsafe integerと呼ばれています。

さて、筆者が作っているStandard ML処理系、LunarMLでもsafe integerに相当する整数型を提供できると便利です。提供するとするとビット数は符号ビットも含めて54ビット、 Int54 みたいなものになります。

ですが、Standard MLの固定長整数は2の補数表現を仮定しており、表現できる範囲は\([-2^n,2^n-1]\)の形である必要があります。これとsafe integerを比べると、\(-2^{53}\)がはみ出ます。

なので、LunarMLで Int54 を提供するには、演算結果が\(-(2^{53}+1)\)の場合を何らかの方法で検出し、オーバーフロー例外を起こさなければなりません。この時、\(2^{53}+1\)が素数だったなら乗算の場合に演算結果が\(-(2^{53}+1)\)になる可能性を考慮しなくてよかったのに、現実は残酷でした、という話です。

最速のフィボナッチ数計算を考える

Qiitaにこういう記事を書いた:

Haskellでフィボナッチ数列 〜Haskellで非実用的なコードを書いて悦に入るのはやめろ〜

↑の記事ではメモ化しない計算法が遅いこと、Haskellには遅延評価の罠があって正格にすると早くなること、「n番目のフィボナッチ数」をピンポイントで計算する場合は(行列またはQ(√5)の)冪乗を使う方法が早いこと、一般項(ビネの公式)をその辺の浮動小数点数で計算するのは使い物にならないこと、などを述べた。

まあ、「Haskellでは fib 0 = 0; fib 1 = 1; fib n = fib (n-1) + fib (n-2) でフィボナッチ数が計算できます!」に対する注意喚起としてはこれで十分すぎる内容なのだが、「n番目のフィボナッチ数をピンポイントで計算する方法」についてはもっと深掘りできる。

この記事では、数学的な考察も交えて、「n番目のフィボナッチ数をピンポイントで計算する方法」をより高速化してみたい。(計算量としてはどっちみち O(log n) くらいなのだが、定数倍の部分で高速化する)

なお、記事タイトルには「最速の」と書いたが、この記事で紹介するアルゴリズムが最速だと主張するわけではない(筆者の知らない、もっと早いアルゴリズムが存在するかもしれない)。 続きを読む

圏論の入門書(2018年版)

以前(2014年ごろ)このブログに「圏論の本」という記事を書いたが、あれ以降いろいろな本が出てきたようだ。特に、和書が増えた。

というわけで、この記事では2018年時点で手に入る圏論の本を独断と偏見で紹介する。ここで紹介するのは入門書、和書が中心となり、より専門的な話題に特化した本は省く。

圏論の入門書と一口に言っても、書き方や内容は著者によって様々である。読者にも代数学をやりたい人、プログラミングやロジックをやりたい人、色々いるだろうが、読者のバックグラウンドや興味の方向によって読むべき本は変わる。

読者が適切な本を選択する為に、この記事が(十分なガイドとまではならなくとも)なんらかのヒントを提供できれば幸いである。

適宜、Web上で他の方が書いた書評にリンクを貼る。 続きを読む