缓慢的 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学习网公众号!
-
439 收藏
-
262 收藏
-
193 收藏
-
188 收藏
-
500 收藏
-
139 收藏
-
204 收藏
-
325 收藏
-
477 收藏
-
486 收藏
-
439 收藏
-
- 前端进阶之JavaScript设计模式
- 设计模式是开发人员在软件开发过程中面临一般问题时的解决方案,代表了最佳的实践。本课程的主打内容包括JS常见设计模式以及具体应用场景,打造一站式知识长龙服务,适合有JS基础的同学学习。
- 立即学习 542次学习
-
- GO语言核心编程课程
- 本课程采用真实案例,全面具体可落地,从理论到实践,一步一步将GO核心编程技术、编程思想、底层实现融会贯通,使学习者贴近时代脉搏,做IT互联网时代的弄潮儿。
- 立即学习 507次学习
-
- 简单聊聊mysql8与网络通信
- 如有问题加微信:Le-studyg;在课程中,我们将首先介绍MySQL8的新特性,包括性能优化、安全增强、新数据类型等,帮助学生快速熟悉MySQL8的最新功能。接着,我们将深入解析MySQL的网络通信机制,包括协议、连接管理、数据传输等,让
- 立即学习 497次学习
-
- JavaScript正则表达式基础与实战
- 在任何一门编程语言中,正则表达式,都是一项重要的知识,它提供了高效的字符串匹配与捕获机制,可以极大的简化程序设计。
- 立即学习 487次学习
-
- 从零制作响应式网站—Grid布局
- 本系列教程将展示从零制作一个假想的网络科技公司官网,分为导航,轮播,关于我们,成功案例,服务流程,团队介绍,数据部分,公司动态,底部信息等内容区块。网站整体采用CSSGrid布局,支持响应式,有流畅过渡和展现动画。
- 立即学习 484次学习