今日から学会.僕の発表は木曜日の最終セッション(の最後).みんな疲れてそう.
Golangで多倍長整数を扱うとき,標準に実装されてるものを使うならmath/bigintになるわけだが,こいつの中身がどうなってるのか気にしたことがなかったので調べてみた.
参照したのはここ.
多分2021年1月時点で最新.
Int型を使うことで,メモリ管理を気にすることなく多倍長整数の四則演算ができる(四則演算用の関数(メソッド?)が用意されてるのでそれを使う).
src/math/big/int.go
type Int struct { neg bool // sign abs nat // absolute value of the integer }
negは正負の管理,nat型のabsが具体的な値. natってなんだろうなつってnat.go見てたらあった.
src/math/big/nat.go
type nat []Word
Word型ってなんだよつって調べてたらあった.
src/math/big/arith.go
type Word uint
natはuint配列のtypedefというわけ(厳密にはスライスか). uintは符号無し64ビット.
Int型が保持できる最大値ってなんだろうね.コンピュータリソースが許す限りってのは曖昧だしな.Golangが管理できる配列の最大値とかあるなら,具体的に数値出せるかな.
乗算はKaratsubaとgrade school?を使い分けるらしい. GMPはどうだっけな.2000ビットくらいまではKaratsubaで,2000ビットを超えたら乗算アルゴリズムを切り替えてたはず. GolangはKaratsubaしか使わないのかも.要検証. grade-schoolがWikipediaにあった Long multiplication
2000ビット以上の整数の乗算はあまりなさそうだけど,本来ならアルゴリズムを切り替えるべきなのにKaratsuba使ってるわけだし速度に難ありっぽい.