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

# はじめに

これは [Wanoグループ Advent Calendar 2017](https://qiita.com/advent-calendar/2017/wano-group) の 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](https://golang.org/pkg/math/big/) というパッケージがあるのでこれを使用します。
`import "math/big"` で使用できるようになります。


# 使い方
[big](https://golang.org/pkg/math/big/) パッケージの Int 型に関する使い方をまとめました。

## NewInt()

```go
bigNum := big.NewInt(9223372036854775807)
```
引数は Int64 で表現できる範囲である必要があります。
Int64 の範囲を超える数を引数にするとオーバーフローします。

```int.go
func NewInt(x int64) *Int {
	return new(Int).SetInt64(x)
}
```
実装をみると `SetInt64(x)` で x が Int64 になってるためオーバーフローするみたいです。

## 四則演算

### ADD

9223372036854775807 + 2 = 9223372036854775809

```go
bigNum := big.NewInt(9223372036854775807)
bigTwo := big.NewInt(2)

bigNum.Add(bigNum, bigTwo)
```
```
9223372036854775809
```
Int64 の範囲超えても出力されてますね。

### SUB

9223372036854775807 -2 = 9223372036854775805

```go
bigNum := big.NewInt(9223372036854775807)
bigTwo := big.NewInt(2)

bigNum.Sub(bigNum, bigTwo)
```
```
9223372036854775805
```

### MUL

9223372036854775807 * 2 = 18446744073709551614

```go
bigNum := big.NewInt(9223372036854775807)
bigTwo := big.NewInt(2)

bigNum.Mul(bigNum, bigTwo)
```
```
18446744073709551614
```

Int64 の範囲超えても出力ｓ(

### DIV

9223372036854775807 / 2 = 4611686018427387903

```go
bigNum := big.NewInt(9223372036854775807)
bigTwo := big.NewInt(2)

bigNum.Div(bigNum, bigTwo)
```
```
4611686018427387903
```

## 剰余演算

### MOD

9223372036854775807 % 2 = 1

```go
bigNum := big.NewInt(9223372036854775807)
bigTwo := big.NewInt(2)

bigNum.Mod(bigNum, bigTwo)
```
```
1
```

`DivMod()` という余り付きの除算もあります。
これを使うと商と余りが同時に求まります。

## 累乗演算

### EXP
これ以降わかりやすくするために値を簡単にします。

10 ^ 2 = 100

```go

bigNum := big.NewInt(10)
bigTwo := big.NewInt(2)

bigNum.Exp(bigNum, bigTwo, nil)
```
```
100
```

第 3 引数に値を代入するとその値で mod をとります。
(10 ^ 2) % 3 = 1

```go
bigNum := big.NewInt(10)
bigTwo := big.NewInt(2)

bigNum.Exp(bigNum, bigTwo, big.NewInt(3))
```
```
1
```

## 論理演算

### AND
00001010 & 00000010 = 00000010

```go
bigNum := big.NewInt(10)
bigTwo := big.NewInt(2)

bigNum.And(bigNum, bigTwo)
```
```
2
```

### ANDNOT
00001010 &^ 00000010 = 00001000

```go
bigNum := big.NewInt(10)
bigTwo := big.NewInt(2)

bigNum.AndNot(bigNum, bigTwo)
```
```
8
```

### OR
00001010 | 00000010 = 00001010

```go
bigNum := big.NewInt(10)
bigTwo := big.NewInt(2)

bigNum.Or(bigNum, bigTwo)
``` 
```
10
```

### NOT
^00001010 = 11110101

```go
bigNum := big.NewInt(10)

bigNum.Not(bigNum)
``` 
```
-11
```

### XOR
00001010 ^ 00000010 = 00001010

``` go
bigNum := big.NewInt(10)
bigTwo := big.NewInt(2)

bigNum.Xor(bigNum, bigTwo)
``` 
```
8
```

## 比較演算

### Cmp
10 > 2

```go
bigNum := big.NewInt(10)
bigTwo := big.NewInt(2)

compares := bigNum.Cmp(bigTwo)
```
```
1
```

x が y より小さいと -1 、 等しいと 0 、大きいと 1 が返ってきます。

### Sign

10 > 0

```go
bigNum := big.NewInt(10)

sign := bigNum.Sign()
```
```
1
```
x が 0 より小さいと -1 、 等しいと 0 、大きいと 1 が返ってきます。

## 平方根

### SQRT
√16 = 4

```go
bigTwo := big.NewInt(2)
bigSixteen := big.NewInt(16)

sqrt := bigTwo.Sqrt(bigSixteen)
```
```
4
```

## 算術シフト

### LSH
00000010 -> 00001000

```go
bigTwo := big.NewInt(2)

bigTwo.Lsh(bigTwo,2)
```
```
8
```

第 2 引数で指定したビット数だけ左算術シフトします。

### RSH
0000 0010 -> 0000 0000

```go
bigTwo := big.NewInt(2)

bigTwo.Rsh(bigTwo,2)
```
```
0
```

第 2 引数で指定したビット数だけ右算術シフトします。

# 終わりに

普段 Go 言語を書いていてあまり使うことのない多倍長整数ですが、せっかく使ってみたのでまとめてみました。
演算はつなげて `num.Add().Sub()` のようにも使えます。

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

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