缓慢的 int.big 计算且仅在一个线程上

小伙伴们对Golang编程感兴趣吗？是否正在学习相关知识点？如果是，那么本文《缓慢的 int.big 计算且仅在一个线程上》，就很适合你，本篇文章讲解的知识点主要包括golang。在之后的文章中也会多多分享相关知识点，希望对大家的知识积累有所帮助！

问题内容

我在测试中使用以下代码：

package main

import "fmt"
import "math/big"

func main() {
    input := "3333333333333333333.......tested with 100'000x3 , tested with 1'000'0000x3, tested with 10'000'000x3"
    bi := big.NewInt(0)
    if _, ok := bi.SetString(input, 10); ok {
        fmt.Printf("number = %v\n", bi)

        testval := new(big.Int)
        testval.SetString("3", 10)

        resultat, isGanzzahl := myDiv(bi, testval)
        fmt.Printf("isGanzzahl = %v, resultat = %v\n", isGanzzahl, resultat)
    } else {
        fmt.Printf("error parsing line %#v\n", input)
    }
}

func myDiv(minuend *big.Int, subtrahend *big.Int) (*big.Int, bool) {
    zerotest := big.NewInt(0)

    modulus := new(big.Int)
    modulus = modulus.Mod(minuend, subtrahend)

    if zerotest.Cmp(modulus) == 0 {
        res := big.NewInt(0)
        res.Quo(minuend, subtrahend)
        return res, true
    } else {
        return big.NewInt(0), false
    }
}

• 100'000 x 3 / 3 == 甚至不到四分之一秒
• 1'000'000 x 3 / 3 == 9.45 秒
• 10'000'000 x 3 / 3 == 16.1 分钟

我正在寻找一种方法来使这种情况发生得更快。如果我想在 go 中执行此多线程操作，我如何使用 go-routines 执行此操作？有没有更快的方法来进行更大数字的除法？

由于这只是为了测试，我计划使用 100'000'000 - 1'000'000'000 位范围内的数字（这将是 1GB 的 ram 使用量）。但是 10 亿位是行不通的，因为它需要数年才能完成。

如果它是 N / M 会发生什么？其中 N=10 亿位，M=1000 万位。这在功能强大的家用电脑上是否可行？

它看起来如何/或者我必须改变什么才能将这项工作分发到多台小型计算机（例如 AWS）？

正确答案

如果您的号码长度超过 100000 位，则需要使用快速傅里叶变换进行乘除：https ://en.wikipedia.org/wiki/Multiplication_algorithm#Fourier_transform_methods 。基本思想是将数字视为多项式，其中 x 是 10 的幂（如果需要二进制系统，则为 2 的幂）。使用快速傅里叶变换将多项式相乘，然后传播进位以从多项式中获取一个数字。即如果我们需要将 19 乘以 19 并且我们使用 x = 10 1，我们将有 (1 * x + 9) * (1 * x + 9) = x 2 + 18 * x + 81。现在我们将进位传播到将多项式转换回数字： x 2 + 18

• x + 81 = x 2 + (18 + 8) * x + 1 = x 2 + 26 * x + 1 = (1 + 2) * x2 + 6 * x

• 1 = 3 * x 2 + 6 * x + 1 = 361。诀窍是多项式可以使用快速傅里叶变换有效地相乘（O(N*log(N) 时间）。乘积多项式大于数字，因此您需要仔细选择 x 以避免整数溢出或精度问题。

不太可能有一个 golang 库，所以你需要自己编写它。以下是一些可以用作起点的简短 FFT 实现：

http://codeforces.com/contest/632/submission/16449753 http://codeforces.com/contest/632/submission/16445979 http://codeforces.com/contest/632/submission/16449040 http://codeforces .com/contest/632/submission/16448169

如果您决定使用 FFT 模素数，请参阅这篇文章以获得模数的好选择：http: [//petr- mitrichev.blogspot.com/2015/04/this-week-in-competitive- programming.html](http://petr-mitrichev.blogspot.com/2015/04/this-week-in- competitive-programming.html)

以上就是《缓慢的 int.big 计算且仅在一个线程上》的详细内容，更多关于golang的资料请关注golang学习网公众号！