Go 言語ビッグ パッケージ: 整数の高精度計算

実際の開発では、int64 型や uint64 型を超える大きな数値を計算する場合、精度の要求がなければ float32 や float64 を使用できますが、精度の要求が厳しい場合は浮動小数点数が使用できないため、浮動小数点数は使用できません。数値はメモリ内でしか表現できません。

 

Go 言語の math/big パッケージは、大きな数値の多精度計算を実装し、Int (符号付き整数)、Rat (有理数)、Float (浮動小数点数) などのデジタル型をサポートします。

これらの型は、メモリが十分に大きい限り、任意の桁数の数値を実装できますが、欠点は、より多くのメモリと処理のオーバーヘッドを必要とするため、組み込みの数値型よりも使用が大幅に遅くなるということです。

math/big パッケージでは、Int 型の定義は次のようになります。

 // Int型は、符号付き多倍長整数を表します。
// Int型のゼロ値は0を表します。
type Int struct {
    neg bool // 符号
    abs nat  // 整数の絶対値
} 

以下に示すように、Int 型を生成するメソッドは NewInt() です。

 // NewIntはxに設定された新しいIntを割り当てて返します。
func NewInt(x int64) *Int {
    return new(Int).SetInt64(x)
} 

注: NewInt() 関数は int64 に対してのみ有効です。他の型は最初に int64 に変換する必要があります。

Go 言語には、他の型の整数を Int に簡単に格納できる多くの Set 関数も用意されています。したがって、最初に new(int) を実行してから Set 関数を呼び出すことができます。Set 関数は次のとおりです。

 // SetInt64関数はzをxに変換し、zを返します。
func（z * Int）SetInt64（x int64）* Int {
    neg：= false
    if x <0 {
        neg = true
        x =-x
    }
    z.abs = z.abs.setUint64（uint64（x））
    z.neg = neg
    return z
}

// SetUint64関数はzをxに変換し、zを返します。
func（z * Int）SetUint64（x uint64）* Int {
    z.abs = z.abs.setUint64（x）
    z.neg = false
    return z
}

// Set関数はzをxに変換し、zを返します。
func（z * Int）Set（x * Int）* Int {
    if z！= x {
        z.abs = z.abs.set（x.abs）
        z.neg = x.neg
    }
    return z
} 

サンプルコードは次のとおりです。

package main

import (
    "fmt"
    "math/big"
)

func main() {
    big1 := new(big.Int).SetUint64(uint64(1000))
    fmt.Println("big1は：", big1)

    big2 := big1.Uint64()
    fmt.Println("big2は：", big2)
} 

操作の結果は次のようになります。

big1 は：  1000
big2 は： 1000

上記の Set 関数に加えて、math/big パッケージには、2 進数、10 進数、16 進数などの基数を指定できる SetString() 関数も提供されています。

 // SetStringは、与えられた基数で解釈されたsの値をzに設定し、成功の真偽値と共にzを返します。成功するには、文字列全体（プレフィックスだけでなく）が有効である必要があります。SetStringが失敗した場合、zの値は未定義ですが、返される値はnilです。
//
//基数引数は0または2以上MaxBase以下の値でなければならず、基数が0の場合、文字列プレフィックスが実際の変換基数を決定します。 "0x"または "0X"のプレフィックスは基数16を選択します。 "0"プレフィックスは基数8を選択し、 "0b"または "0B"プレフィックスは基数2を選択します。それ以外の場合、選択された基数は10です。
//
func (z *Int) SetString(s string, base int) (*Int, bool) {
    r := strings.NewReader(s)
    if _, _, err := z.scan(r, base); err != nil {
        return nil, false
    }
    // 文字列全体が消費される必要があります
    if _, err := r.ReadByte(); err != io.EOF {
        return nil, false
    }
    return z, true // err == io.EOF => scan consumed all of s
} 

サンプルコードは次のとおりです。

package main

import (
    "fmt"
    "math/big"
)

func main() {
    big1, _ := new(big.Int).SetString("1000", 10)
    fmt.Println("big1 は: ", big1)

    big2 := big1.Uint64()
    fmt.Println("big2 は: ", big2)
} 

操作の結果は次のようになります。

big1 は：1000
big2 は：1000

Go は演算子のオーバーロードをサポートしていないため、すべての大きな数値型には Add() や Mul() などのメソッドがあります。

Add メソッドは次のように定義されます。

func (z *Int) Add(x, y *Int) *Int

このメソッドは、z を x + y に変換し、z を返します。

[例] 1000番目のフィボナッチ数列を計算します。

package main

import (
    "fmt"
    "math/big"
    "time"
)

const LIM = 1000 // フィボナッチ数列の1000番目の値を求める

var fibs [LIM]*big.Int // 計算済みのフィボナッチ数列を配列に保存する

func main() {
    result := big.NewInt(0)
    start := time.Now()
    for i := 0; i < LIM; i++ {
        result = fibonacci(i)
        fmt.Printf("Number at %d position: %d\n", i+1, result)
    }
    end := time.Now()
    delta := end.Sub(start)
    fmt.Printf("完了。実行時間: %s\n", delta)
}

func fibonacci(n int) (res *big.Int) {
    if n <= 1 {
        res = big.NewInt(1)
    } else {
        temp := new(big.Int)
        res = temp.Add(fibs[n-1], fibs[n-2])
    }
    fibs[n] = res
    return
} 

操作の結果は次のようになります。

Number at 1 position:: 1
Number at 2 position:: 1
Number at 3 position:: 2
Number at 4 position:: 3
Number at 5 position:: 5
…

Number at 1000 position: 4346655768693745643568852767504062580256466051737178040248172908953655541794905189040387984007925516
92959225930803226347752096896232398733224711616429964409065331879382989696499285160037044761377951668
49228875
完了。実行時間: 6.945ms