INT速度慢。运算量大，且仅在一个线程上 [英] slow int.big calculation and only on one thread

问题描述

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

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
", bi)

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

        resultat, isGanzzahl := myDiv(bi, testval)
        fmt.Printf("isGanzzahl = %v, resultat = %v
", isGanzzahl, resultat)
    } else {
        fmt.Printf("error parsing line %#v
", 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-例程来做这件事？有没有更快的方法来做更大数字的除法？

由于这只是为了测试，我计划使用100‘000’000-1‘000’000‘000位数字(这将是1 GB的内存使用量)。但10亿位数字不起作用，因为它需要数年时间才能完成。

如果是N/M，会发生什么情况？其中N=10亿位，M=1000万位。在功能强大的家用计算机上实现这一点吗？

要将此工作分发到多台小型计算机(例如AWS)，我需要做些什么更改？

推荐答案

如果您的数字长度超过100000位，则需要使用快速傅立叶变换进行乘除：https://en.wikipedia.org/wiki/Multiplication_algorithm#Fourier_transform_methods。其基本思想是将数字视为x为10的幂的多项式(如果您想使用二进制，则x为2的幂)。使用快速傅立叶变换将多项式相乘，然后传播进位以从多项式中获得一个数字。也就是说，如果我们需要用19乘以19，并且我们使用x=10¹，我们将得到(1*x+9)*(1*x+9)=x²+18*x+81。现在我们传播进位以将多项式转换回数字：x 2+18*x+81=x 2+(18+8)*x+1=x 2+26*x+1=(1+2)*x+1=3*x+1=3*x+2+6*x+1=361。诀窍在于，多项式可以使用快速傅立叶变换有效地相乘(O(N*log(N)次))。乘积多项式的系数大于数字，因此需要仔细选择x以避免整数溢出或精度问题。

不太可能有这样的Golang库，所以您需要自己编写它。以下是您可以作为起点的几个简短的FFT实现：

http://codeforces.com/contest/632/submission/16449753http://codeforces.com/contest/632/submission/16445979http://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

这篇关于INT速度慢。运算量大，且仅在一个线程上的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！