英文:
Dealing with large numbers with GMP-style performance in Go
问题
我正在学习Go语言，并开始使用math/big包来处理任意长度的整数。
我编写了一个计算第n个斐波那契数的程序：（删除了import部分）：
func main() {
imax, _ := strconv.Atoi(os.Args[1])
var a, b, c big.Int
a.SetUint64(0)
b.SetUint64(1)
for i := 0; i < imax; i++ {
c.Set(&b)
b.Add(&b, &a)
a.Set(&c)
}
fmt.Println(a.String())
}
以下是C程序的代码：
int main(int argc, char** argv)
{
int imax = atoi(argv[1]);
mpz_t a, b, c;
mpz_inits(a, b, c, NULL);
mpz_set_ui(a, 0);
mpz_set_ui(b, 1);
int i = 0;
for (i = 0; i < imax; i++) {
mpz_swap(a, b);
mpz_add(b, a, b);
}
char* astr = NULL;
astr = mpz_get_str(NULL, 10, a);
printf("%s\n", astr);
return EXIT_SUCCESS;
}
Go程序在0.1秒内计算出第100,000个斐波那契数（平均值），而使用GMP库的C等效程序仅需0.04秒。这慢了两倍。
有没有办法在我的Go程序中获得相同的性能？
英文:
I'm learning Go and I started using the math/big package to deal with arbitrary-length integer.
I wrote this program that computes the n-th Fibonacci number : (removed the imports) :
func main() {
imax, _ := strconv.Atoi(os.Args[1])
var a, b, c big.Int
a.SetUint64(0)
b.SetUint64(1)
for i := 0; i < imax; i++ {
c.Set(&b)
b.Add(&b, &a)
a.Set(&c)
}
fmt.Println(a.String())
}
Here's the code for the C program :
int main(int argc, char** argv)
{
int imax = atoi(argv[1]);
mpz_t a, b, c;
mpz_inits(a, b, c, NULL);
mpz_set_ui(a, 0);
mpz_set_ui(b, 1);
int i = 0;
for (i = 0; i < imax; i++) {
mpz_swap(a, b);
mpz_add(b, a, b);
}
char* astr = NULL;
astr = mpz_get_str(NULL, 10, a);
printf("%s\n", astr);
return EXIT_SUCCESS;
}
The Go program computes the term 100,000 in 0.1 second (average), while the C equivalent, using the GMP lib, runs in 0.04 second only. That's two times slower.
Is there a way to get the same performance in my Go program ?
答案1
得分: 2
不要将结果打印到标准输出，这样会很慢。对于这段代码，你得到了什么结果？
package main
import (
"math/big"
"os"
"strconv"
)
func main() {
max, err := strconv.Atoi(os.Args[1])
if err != nil {
panic(err)
}
a, b := big.NewInt(0), big.NewInt(1)
for i := 0; i < max; i++ {
a.Add(a, b)
a, b = b, a
}
}
Go语言不是手工编写的汇编代码。
你的100,000的值对于可靠的基准测试来说太小了。使用1,000,000或者至少运行十秒的其他值。
英文:
Don't print to stdout, it's slow. What result do you get for this code?
package main
import (
"math/big"
"os"
"strconv"
)
func main() {
max, err := strconv.Atoi(os.Args[1])
if err != nil {
panic(err)
}
a, b := big.NewInt(0), big.NewInt(1)
for i := 0; i < max; i++ {
a.Add(a, b)
a, b = b, a
}
}
Go is not hand crafted assembler code.
Your value of 100,000 is too small for a reliable benchmark. Use 1,000,000 or another value that runs for at least ten seconds.
答案2
得分: 1
通常情况下，GMP更快，因为它专为性能而设计。在底层，你可能会发现它部分是用汇编语言编写的，这减少了函数调用的开销，并且可能利用了一些CPU指令，比如ADX等。
如果你关心性能，你可以使用mpz_fib_ui函数，它会更快，因为它利用了一些数学技巧。
直接回答你的问题，可能是使用一些Go语言的GMP绑定。
英文:
In general, GMP is faster because it's crafted for performance. Under the hood, you may find that it is partly written in assembly, which reduces functions' call overhead, may utilize some CPU instructions like ADX and so on.
If you care about performance, then you could use mpz_fib_ui routine, that would be even faster, as it gains from some math trickery.
The direct answer to your question is probably to use some Go's binding for GMP.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论