Zenn
📝

Go言語における多倍長整数 bigint の覚え書き

2020/10/15に公開
Go
bigint
tech

はじめに

某コンテストで Go 言語の多倍長整数を触る機会がありました。
今後のためにも忘れないように備忘録として書いていこうと思います。

(この記事は これ の移植です。)

そもそも多倍長整数って？

多倍長整数とは

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() のようにも使えます。

ここ違うよーとかご意見等ありましたらコメントにてよろしくお願いします。

最後までありがとうございました。

Discussion