Q
快速求幂的实现
2
A
回答
13
除非这是家庭作业,否则您可能不想推出自己的任意精确求幂的实现。计算你描述的类型的大指数是复杂的 - 除了性能。
我会推荐使用existing arbitrary precision arithmetic libraries, like GMP之一 - 其中大部分都有库从C#访问它们。
F#支持使用BigInt类的任意精度算法(如果您导入它所在的程序集,您也可以从C#访问)。但是,我不知道BigInt指数是如何优化的。
如果您只是想了解指数运算的高效算法,您可能需要查看指数运算的Square-And-Multiply算法。
0
查看结果:IntX适用于LARGE整数。你可能必须编写自己的权力实现,但由于支持乘法,所以这不应该太难。
由280Z28编辑:另一个包含fast Pow,ModPow和素数测试的实现是BigInteger实现(代码项目),我过去曾在Project Euler问题上使用过 - 尽管我现在使用.NET 4.0并使用它的System.Numerics.BigInteger实现。
+0
如果计算结果非常重要,我会建议使用比IntX更成熟的库。为任意精度编写正确的库比看起来更难 - 许多小型项目还没有机会检测和解决困扰大多数实现的各类问题。 – LBushkin 2009-10-27 15:02:41
2
相关问题
- 1. horner算法 - 快速求幂
- 2. 快速矩阵求幂
- 3. Maple中的快速模幂运算
- 4. 快速排序python实现
- 5. 快速存储桶实现
- 6. 实现快速排序
- 7. 快速排序实现
- 8. 快速实现发现的人数
- 9. 如何避免快速模幂溢出
- 10. 实现AWS竞价实例请求的幂等性
- 11. C++:实现模幂运算
- 12. C++库中的快速渐变实现?
- 13. 蟒蛇中的快速车实现
- 14. ArrayIndexOutOfBoundsException异常的快速排序实现
- 15. 快速排序实现中的ArrayIndexOutofBound
- 16. 快速排序实现中的问题
- 17. C++中的快速排序实现
- 18. Go中的快速排序实现
- 19. 在Linux中快速实现“GetCurrentThreadId”
- 20. 帮助实现快速排序
- 21. 快速排序:用Python实现
- 22. 3路快速排序(C实现)
- 23. Haskell二叉树快速实现
- 24. 快速随机森林算法实现
- 25. 使用SOAP实现快速结账(PayPal)
- 26. 将游戏实现为快速游戏
- 27. 在C++中快速实现MD5
- 28. 失败快速迭代器实现
- 29. 实现快速查看QLPreviewController动画
- 30. 并行快速排序C实现
优秀的答案。 – 2009-10-27 15:13:21
+1。很有意思。 – RichardOD 2009-10-30 16:34:44