登录
首页 >  Golang >  Go问答

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

来源:Golang技术栈

时间:2023-03-10 12:41:53 382浏览 收藏

小伙伴们对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学习网公众号!

声明:本文转载于:Golang技术栈 如有侵犯,请联系study_golang@163.com删除
相关阅读
更多>
最新阅读
更多>
课程推荐
更多>
评论列表