How to convert int to bigint in golang?

huangapple go评论91阅读模式
英文:

How to convert int to bigint in golang?

问题

我正在尝试实现快速双倍斐波那契算法,如这里所描述的:

// 快速双倍斐波那契算法
package main

import "fmt"

// (公共) 返回 F(n)。
func fibonacci(n int) int {
    if n < 0 {
        panic("未实现负数参数")
    }
    fst, _ := fib(n)
    return fst
}

// (私有) 返回元组 (F(n), F(n+1))。
func fib(n int) (int, int) {
    if n == 0 {
        return 0, 1
    }
    a, b := fib(n/2)
    c := a * (b*2 - a)
    d := a*a + b*b
    if n%2 == 0 {
        return c, d
    } else {
        return d, c + d
    }
}

func main() {
    fmt.Println(fibonacci(13))
    fmt.Println(fibonacci(14))
}

这对于小数值的输入效果很好;然而,当输入的数值变大时,程序返回错误的结果。因此,我尝试使用 math/big 包中的 big.Int

// 快速双倍斐波那契算法
package main

import (
    "fmt"
    "math/big"
)

// (公共) 返回 F(n)。
func fibonacci(n int) big.Int {
    if n < 0 {
        panic("未实现负数参数")
    }
    fst, _ := fib(n)
    return fst
}

// (私有) 返回元组 (F(n), F(n+1))。
func fib(n int) (big.Int, big.Int) {
    if n == 0 {
        return *big.NewInt(0), *big.NewInt(1)
    }
    a, b := fib(n/2)
    c := *big.NewInt(0).Mul(&a, big.NewInt(2)).Sub(big.NewInt(0).Mul(&b, &b), &a)
    d := *big.NewInt(0).Add(big.NewInt(0).Mul(&a, &a), big.NewInt(0).Mul(&b, &b))
    if n%2 == 0 {
        return c, d
    } else {
        return d, *big.NewInt(0).Add(&c, &d)
    }
}

func main() {
    fmt.Println(fibonacci(123))
    fmt.Println(fibonacci(124))
}

然而,go build 报错:

无法将 0 (类型 int) 转换为 big.Int 类型

如何解决这个问题?

英文:

I'm trying to implement fast double Fibonacci algorithm as described here:

// Fast doubling Fibonacci algorithm
package main

import &quot;fmt&quot;

//  (Public) Returns F(n).
func fibonacci(n int) int {
	if n &lt; 0 {
		panic(&quot;Negative arguments not implemented&quot;)
	}
	fst, _ := fib(n)
	return fst
}

// (Private) Returns the tuple (F(n), F(n+1)).
func fib(n int) (int, int) {
	if n == 0 {
		return 0, 1
	}
	a, b := fib(n / 2)
	c := a * (b*2 - a)
	d := a*a + b*b
	if n%2 == 0 {
		return c, d
	} else {
		return d, c + d
	}
}

func main() {
	fmt.Println(fibonacci(13))
	fmt.Println(fibonacci(14))
}

This works fine for small numbers; however, when the input number get larger, the program returns a wrong result. So I tried to use bigInt from math/big package:

// Fast doubling Fibonacci algorithm
package main

import (
	&quot;fmt&quot;
	&quot;math/big&quot;
)

//  (Public) Returns F(n).
func fibonacci(n int) big.Int {
	if n &lt; 0 {
		panic(&quot;Negative arguments not implemented&quot;)
	}
	fst, _ := fib(n)
	return fst
}

// (Private) Returns the tuple (F(n), F(n+1)).
func fib(n int) (big.Int, big.Int) {
	if n == 0 {
		return big.Int(0), big.Int(1)
	}
	a, b := fib(n / 2)
	c := a * (b*2 - a)
	d := a*a + b*b
	if n%2 == 0 {
		return c, d
	} else {
		return d, c + d
	}
}

func main() {
	fmt.Println(fibonacci(123))
	fmt.Println(fibonacci(124))
}

However, go build complains that

cannot convert 0 (type int) to type big.Int

How to mitigate this problem?

答案1

得分: 17

使用big.NewInt()代替big.Int()big.Int()只是类型转换。
你需要查看big包的文档
你应该主要使用形式为func (z *T) Binary(x, y *T) *T // z = x op y的方法。
要乘以两个参数,你需要提供结果变量,然后调用Mul方法。例如,要得到2*2的结果,你需要:
big.NewInt(0).Mul(big.NewInt(2), big.NewInt(2))

你可以在<kbd>Go playground</kbd>上尝试工作示例。

你还可以创建扩展函数,例如:

func Mul(x, y *big.Int) *big.Int {
    return big.NewInt(0).Mul(x, y)
}

以使代码更易读:

// 快速倍增斐波那契算法
package main

import (
    "fmt"
    "math/big"
)

// (公共)返回F(n)。
func fibonacci(n int) *big.Int {
    if n < 0 {
        panic("未实现负数参数")
    }
    fst, _ := fib(n)
    return fst
}

// (私有)返回元组(F(n),F(n+1))。
func fib(n int) (*big.Int, *big.Int) {
    if n == 0 {
        return big.NewInt(0), big.NewInt(1)
    }
    a, b := fib(n / 2)
    c := Mul(a, Sub(Mul(b, big.NewInt(2)), a))
    d := Add(Mul(a, a), Mul(b, b))
    if n%2 == 0 {
        return c, d
    } else {
        return d, Add(c, d)
    }
}

func main() {
    fmt.Println(fibonacci(123))
    fmt.Println(fibonacci(124))
}

func Mul(x, y *big.Int) *big.Int {
    return big.NewInt(0).Mul(x, y)
}
func Sub(x, y *big.Int) *big.Int {
    return big.NewInt(0).Sub(x, y)
}
func Add(x, y *big.Int) *big.Int {
    return big.NewInt(0).Add(x, y)
}

在<kbd>Go playground</kbd>上试一试。

英文:

Use big.NewInt() instead of big.Int(). big.Int() is just type casting.
You need to check out documentation of big package
You should mostly use methods with form func (z *T) Binary(x, y *T) *T // z = x op y
To multiply 2 arguments you need to provide result variable, after it call Mul method. So, for example, to get result of 2*2 you need to:
big.NewInt(0).Mul(big.NewInt(2), big.NewInt(2))

You can try working example on the <kbd>Go playground</kbd>

Also you can create extension functions like:

func Mul(x, y *big.Int) *big.Int {
    return big.NewInt(0).Mul(x, y)
}

To make code more readable:

// Fast doubling Fibonacci algorithm
package main

import (
	&quot;fmt&quot;
	&quot;math/big&quot;
)

//  (Public) Returns F(n).
func fibonacci(n int) *big.Int {
	if n &lt; 0 {
		panic(&quot;Negative arguments not implemented&quot;)
	}
	fst, _ := fib(n)
	return fst
}

// (Private) Returns the tuple (F(n), F(n+1)).
func fib(n int) (*big.Int, *big.Int) {
	if n == 0 {
		return big.NewInt(0), big.NewInt(1)
	}
	a, b := fib(n / 2)
	c := Mul(a, Sub(Mul(b, big.NewInt(2)), a))
	d := Add(Mul(a, a), Mul(b, b))
	if n%2 == 0 {
		return c, d
	} else {
		return d, Add(c, d)
	}
}

func main() {
	fmt.Println(fibonacci(123))
	fmt.Println(fibonacci(124))
}

func Mul(x, y *big.Int) *big.Int {
	return big.NewInt(0).Mul(x, y)
}
func Sub(x, y *big.Int) *big.Int {
	return big.NewInt(0).Sub(x, y)
}
func Add(x, y *big.Int) *big.Int {
	return big.NewInt(0).Add(x, y)
}

Try it on the <kbd>Go playground</kbd>

huangapple
  • 本文由 发表于 2015年11月12日 11:37:50
  • 转载请务必保留本文链接:https://go.coder-hub.com/33664041.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定