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

Question

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

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）？

Answer 1

如果你的号码长度超过100000位，你需要使用快速傅立叶变换进行乘除：https://en.wikipedia.org/wiki/Multiplication_algorithm#Fourier_transform_methods。基本思想是将数字视为多项式，其中 x 是 10 的幂（如果需要二进制系统，则为 2 的幂）。使用快速傅立叶变换将多项式相乘，然后传播进位以从多项式中获取数字。 IE。如果我们需要将 19 乘以 19 并且我们使用 x = 10¹，我们将有 (1 * x + 9) * (1 * x + 9) = x² + 18 * x + 81。现在我们传播进位以将多项式转换回数字：x² + 18 * x + 81 = x² + (18 + 8) * x + 1 = x² + 26 * x + 1 = (1 + 2) * x² + 6 * x + 1 = 3 * x² + 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 模素数，请参阅此 post 以选择模数：http://petr-mitrichev.blogspot.com/2015/04/this-week-in-competitive-programming.html

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

slow int.big calculation and only on one thread

distributed-computing

biginteger

go