
Go语言big包:对整数的高精度计算
发布时间:2022-12-18 15:20:05
实际开发中,对于超出 int64 或者 uint64 类型的大数进行计算时,如果对精度没有要求,使用 float32 或者 float64 就可以胜任,但如果对精度有严格要求的时候,我们就不能使用浮点数了,因为浮点数在内存中只能被近似的表示。
Go语言中 math/big 包实现了大数字的多精度计算,支持 Int(有符号整数)、Rat(有理数)和 Float(浮点数)等数字类型。
这些类型可以实现任意位数的数字,只要内存足够大,但缺点是需要更大的内存和处理开销,这使得它们使用起来要比内置的数字类型慢很多。
在 math/big 包中,Int 类型定义如下所示:
type Int struct {
neg bool // sign
abs nat // absolute value of the integer
}
生成 Int 类型的方法为 NewInt(),如下所示:
func NewInt(x int64) *Int {
return new(Int).SetInt64(x)
}
注意:NewInt() 函数只对 int64 有效,其他类型必须先转成 int64 才行。
Go语言中还提供了许多 Set 函数,可以方便的把其他类型的整形存入 Int ,因此,我们可以先 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 is: ", big1)
big2 := big1.Uint64()
fmt.Println("big2 is: ", big2)
}
运行结果如下:
big1 is: 1000
big2 is: 1000
除了上述的 Set 函数,math/big 包中还提供了一个 SetString() 函数,可以指定进制数,比如二进制、十进制或者十六进制等!
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
}
// entire string must have been consumed
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 is: ", big1)
big2 := big1.Uint64()
fmt.Println("big2 is: ", big2)
}
运行结果如下
big1 is: 1000
big2 is: 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 = 100 //求第100位的斐波那契数列
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("数列第 %d 位: %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
}
运行结果如下:
数列第 1 位: 1
数列第 2 位: 1
数列第 3 位: 2
数列第 4 位: 3
数列第 5 位: 5
数列第 6 位: 8
数列第 7 位: 13
数列第 8 位: 21
数列第 9 位: 34
数列第 10 位: 55
数列第 11 位: 89
数列第 12 位: 144
数列第 13 位: 233
数列第 14 位: 377
数列第 15 位: 610
数列第 16 位: 987
数列第 17 位: 1597
数列第 18 位: 2584
数列第 19 位: 4181
数列第 20 位: 6765
数列第 21 位: 10946
数列第 22 位: 17711
数列第 23 位: 28657
数列第 24 位: 46368
数列第 25 位: 75025
数列第 26 位: 121393
数列第 27 位: 196418
数列第 28 位: 317811
数列第 29 位: 514229
数列第 30 位: 832040
数列第 31 位: 1346269
数列第 32 位: 2178309
数列第 33 位: 3524578
数列第 34 位: 5702887
数列第 35 位: 9227465
数列第 36 位: 14930352
数列第 37 位: 24157817
数列第 38 位: 39088169
数列第 39 位: 63245986
数列第 40 位: 102334155
数列第 41 位: 165580141
数列第 42 位: 267914296
数列第 43 位: 433494437
数列第 44 位: 701408733
数列第 45 位: 1134903170
数列第 46 位: 1836311903
数列第 47 位: 2971215073
数列第 48 位: 4807526976
数列第 49 位: 7778742049
数列第 50 位: 12586269025
数列第 51 位: 20365011074
数列第 52 位: 32951280099
数列第 53 位: 53316291173
数列第 54 位: 86267571272
数列第 55 位: 139583862445
数列第 56 位: 225851433717
数列第 57 位: 365435296162
数列第 58 位: 591286729879
数列第 59 位: 956722026041
数列第 60 位: 1548008755920
数列第 61 位: 2504730781961
数列第 62 位: 4052739537881
数列第 63 位: 6557470319842
数列第 64 位: 10610209857723
数列第 65 位: 17167680177565
数列第 66 位: 27777890035288
数列第 67 位: 44945570212853
数列第 68 位: 72723460248141
数列第 69 位: 117669030460994
数列第 70 位: 190392490709135
数列第 71 位: 308061521170129
数列第 72 位: 498454011879264
数列第 73 位: 806515533049393
数列第 74 位: 1304969544928657
数列第 75 位: 2111485077978050
数列第 76 位: 3416454622906707
数列第 77 位: 5527939700884757
数列第 78 位: 8944394323791464
数列第 79 位: 14472334024676221
数列第 80 位: 23416728348467685
数列第 81 位: 37889062373143906
数列第 82 位: 61305790721611591
数列第 83 位: 99194853094755497
数列第 84 位: 160500643816367088
数列第 85 位: 259695496911122585
数列第 86 位: 420196140727489673
数列第 87 位: 679891637638612258
数列第 88 位: 1100087778366101931
数列第 89 位: 1779979416004714189
数列第 90 位: 2880067194370816120
数列第 91 位: 4660046610375530309
数列第 92 位: 7540113804746346429
数列第 93 位: 12200160415121876738
数列第 94 位: 19740274219868223167
数列第 95 位: 31940434634990099905
数列第 96 位: 51680708854858323072
数列第 97 位: 83621143489848422977
数列第 98 位: 135301852344706746049
数列第 99 位: 218922995834555169026
数列第 100 位: 354224848179261915075