はじめに
これは Wanoグループ Advent Calendar 2017 の 3 日目の記事です.
某コンテストで Go 言語の多倍長整数を触る機会がありました。
今後のためにも忘れないように備忘録として書いていこうと思います。
そもそも多倍長整数って？
[多倍長整数とは] (http://d.hatena.ne.jp/keyword/%C2%BF%C7%DC%C4%B9%C0%B0%BF%F4)
CPUの影響を受けない整数型。このため、32ビットや64ビットを超えた巨大な整数を扱うことができる。bigint 型, bignum 型などと呼ばれる。
超簡単に書くと大きい数字が扱えるってことです。
Go言語の Int64 型の場合 9223372036854775807 まで扱えます。逆にこれ以上大きい数字を扱うことができません。
試しに int64NumOverFlow := 9223372036854775808 と書くと constant 9223372036854775808 overflows int と言われて怒られます。
それ以上の数を扱うために多倍長整数を使う必要があります。
Go 言語での多倍長整数
Go 言語では big というパッケージがあるのでこれを使用します。
import "math/big" で使用できるようになります。
使い方
big パッケージの Int 型に関する使い方をまとめました。
NewInt()
bigNum := big.NewInt(9223372036854775807)
引数は Int64 で表現できる範囲である必要があります。
Int64 の範囲を超える数を引数にするとオーバーフローします。
func NewInt(x int64) *Int {
return new(Int).SetInt64(x)
}
実装をみると SetInt64(x) で x が Int64 になってるためオーバーフローするみたいです。
四則演算
ADD
9223372036854775807 + 2 = 9223372036854775809
bigNum := big.NewInt(9223372036854775807)
bigTwo := big.NewInt(2)
bigNum.Add(bigNum, bigTwo)
9223372036854775809
Int64 の範囲超えても出力されてますね。
SUB
9223372036854775807 -2 = 9223372036854775805
bigNum := big.NewInt(9223372036854775807)
bigTwo := big.NewInt(2)
bigNum.Sub(bigNum, bigTwo)
9223372036854775805
MUL
9223372036854775807 * 2 = 18446744073709551614
bigNum := big.NewInt(9223372036854775807)
bigTwo := big.NewInt(2)
bigNum.Mul(bigNum, bigTwo)
18446744073709551614
Int64 の範囲超えても出力ｓ(
DIV
9223372036854775807 / 2 = 4611686018427387903
bigNum := big.NewInt(9223372036854775807)
bigTwo := big.NewInt(2)
bigNum.Div(bigNum, bigTwo)
4611686018427387903
剰余演算
MOD
9223372036854775807 % 2 = 1
bigNum := big.NewInt(9223372036854775807)
bigTwo := big.NewInt(2)
bigNum.Mod(bigNum, bigTwo)
1
DivMod() という余り付きの除算もあります。
これを使うと商と余りが同時に求まります。
累乗演算
EXP
これ以降わかりやすくするために値を簡単にします。
10 ^ 2 = 100
bigNum := big.NewInt(10)
bigTwo := big.NewInt(2)
bigNum.Exp(bigNum, bigTwo, nil)
100
第 3 引数に値を代入するとその値で mod をとります。
(10 ^ 2) % 3 = 1
bigNum := big.NewInt(10)
bigTwo := big.NewInt(2)
bigNum.Exp(bigNum, bigTwo, big.NewInt(3))
1
論理演算
AND
00001010 & 00000010 = 00000010
bigNum := big.NewInt(10)
bigTwo := big.NewInt(2)
bigNum.And(bigNum, bigTwo)
2
ANDNOT
00001010 &^ 00000010 = 00001000
bigNum := big.NewInt(10)
bigTwo := big.NewInt(2)
bigNum.AndNot(bigNum, bigTwo)
8
OR
00001010 | 00000010 = 00001010
bigNum := big.NewInt(10)
bigTwo := big.NewInt(2)
bigNum.Or(bigNum, bigTwo)
10
NOT
^00001010 = 11110101
bigNum := big.NewInt(10)
bigNum.Not(bigNum)
-11
XOR
00001010 ^ 00000010 = 00001010
bigNum := big.NewInt(10)
bigTwo := big.NewInt(2)
bigNum.Xor(bigNum, bigTwo)
8
比較演算
Cmp
10 > 2
bigNum := big.NewInt(10)
bigTwo := big.NewInt(2)
compares := bigNum.Cmp(bigTwo)
1
x が y より小さいと -1 、 等しいと 0 、大きいと 1 が返ってきます。
Sign
10 > 0
bigNum := big.NewInt(10)
sign := bigNum.Sign()
1
x が 0 より小さいと -1 、 等しいと 0 、大きいと 1 が返ってきます。
平方根
SQRT
√16 = 4
bigTwo := big.NewInt(2)
bigSixteen := big.NewInt(16)
sqrt := bigTwo.Sqrt(bigSixteen)
4
算術シフト
LSH
00000010 -> 00001000
bigTwo := big.NewInt(2)
bigTwo.Lsh(bigTwo,2)
8
第 2 引数で指定したビット数だけ左算術シフトします。
RSH
0000 0010 -> 0000 0000
bigTwo := big.NewInt(2)
bigTwo.Rsh(bigTwo,2)
0
第 2 引数で指定したビット数だけ右算術シフトします。
終わりに
普段 Go 言語を書いていてあまり使うことのない多倍長整数ですが、せっかく使ってみたのでまとめてみました。
演算はつなげて num.Add().Sub() のようにも使えます。
ここ違うよーとかご意見等ありましたらコメントにてよろしくお願いします。
最後までありがとうございました。