控えめに言って完動した - 思うだけで学ばない日記 2.0

きみは知っているか？
$2^{64}$ 以上の直近10個の素数は

[   1] 1152921504606847009 is prime number.
[   2] 1152921504606847067 is prime number.
[   3] 1152921504606847081 is prime number.
[   4] 1152921504606847123 is prime number.
[   5] 1152921504606847127 is prime number.
[   6] 1152921504606847189 is prime number.
[   7] 1152921504606847201 is prime number.
[   8] 1152921504606847229 is prime number.
[   9] 1152921504606847253 is prime number.
[  10] 1152921504606847291 is prime number.

だ。

$2^{128}$ 以上だと

[   1] 340282366920938463463374607431768211507 is prime number.
[   2] 340282366920938463463374607431768211537 is prime number.
[   3] 340282366920938463463374607431768211621 is prime number.
[   4] 340282366920938463463374607431768211729 is prime number.
[   5] 340282366920938463463374607431768211841 is prime number.
[   6] 340282366920938463463374607431768211877 is prime number.
[   7] 340282366920938463463374607431768211919 is prime number.
[   8] 340282366920938463463374607431768212029 is prime number.
[   9] 340282366920938463463374607431768212081 is prime number.
[  10] 340282366920938463463374607431768212213 is prime number.

だ。

これがさらに $2^{512}$ 以上とかになると、

[   1] 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171 is prime number.
[   2] 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084241 is prime number.
[   3] 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084381 is prime number.
[   4] 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084823 is prime number.
[   5] 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006085201 is prime number.
[   6] 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006085243 is prime number.
[   7] 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006085369 is prime number.
[   8] 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006086839 is prime number.
[   9] 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006087273 is prime number.
[  10] 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006088009 is prime number.

だったりする*1、

以上は、多倍長整数テンプレートクラスBigNum<桁数>を作成したのでデモンストレーションとして素数判定を行ってみたものだ。
$2^{128}$ 以下なら瞬殺だ。
$2^{512}$ 以上は、さすがに1分かかったorz

大量の桁の表現にはいくばくかのメモリーが要る。
やりたい計算に対して用意した配列では足りなかった場合はこうだ↓

■ 配列4要素で $2^{64}$ 以上の素数判定をしようとして128 bit＋αの積の結果を格納できないとわかったケース：

(sz=4)          +0          +1          +0          +0
ERROR: Overflow.

 0x2d094641 0x2a2980b2 0x211f93eb 0x2bb7e9a8 0x00000000
y=907995832759952054134265850490340929
(sz=4)  +733473192  +555717611  +707362994  +755582529

t=1152921504606846982
(sz=4)          +0          +1          +0          +6

オーバーフローとアンダーフローのチェックは四則演算全てで行われ、いったんオーバーフローかアンダーフローが起きたらその結果は無効な数となる。
さらに無効な数を用いた演算結果もまた無効な数となり*2、最終的に必ずエラーとして検知できる。

以上のしくみは以下のネ申のｳｪﾌﾞﾍﾟｰｼﾞ↓の情報にもとづき繰り上げ算方式*3の多倍長整数演算を固定長配列行うように実装したものである。
■ 超高速！多倍長整数の計算手法【前編：大きな数の四則計算を圧倒的な速度で！】
ttps://qiita.com/square1001/items/1aa12e04934b6e749962

これを有理数クラスに組み込むことにより、精度リッチで比較的高速に動き、オーダー上もn個のベクトルの線形分離完了（または線形分離不能と判定）が大概のケースで $O(n^{3})$ ぐらいで解ける線形分離エンジンが完成すた、

だがタッチの差で完成が遅かった、、、

今日わ、昨年よりちょっと進歩しましたよという風を装った動きをする機能を対戦プログラムにこれから組み込まねばならない|||｡n_

*1:ミラー–ラビン素数判定法で100回づつ回したので多分間違い無い……

*2:これは算術演算か論理演算かを問わず全てでそのように伝搬する。

*3:これが論理回路ならルックアヘッドキャリー方式で多数桁のキャリーを物量に訴えて並列計算するところだが、ソフトウェアーというものは逐次処理しかできないために古式ゆかしいリップルキャリー式のキャリー伝搬の必要性がどこかしら出てくるが、繰り上げ算copy_and_fix()によりそれを極力後回し・必要最小限な回数に減らすことができる。これはメモリーの冗長な使用というコストを支払うことによって、アセンブラの動作速度（キャリーフラグ等を使って毎回リップルキャリーする多倍長超加算器を構成した場合）をも凌駕し得る。知らんけど。