改进的蒙哥马利算法，性能提升高达50%。它利用了低阶乘法和模B^n-1算法的特殊性，减少了计算次数。我已经用CL编写了这段代码，如果有人对这个算法感兴趣，我会添加相应的测试和详细解释。
| 名称 | old time/op | new time/op | delta |
|---|---|---|---|
| ExpLarge/100-4 | 137ms ± 3% | 190ms ±15% +38.67% (p=0.004 n=6+5) | |
| ExpLarge/200-4 | 987ms ± 0% | 999ms ± 3% ~ (p=0.662 n=6+5) | |
| ExpLarge/400-4 | 7.87s ± 3% | 6.02s ± 2% -23.55% (p=0.003 n=7+5) | |
| ExpLarge/600-4 | 26.8s ± 1% | 16.7s ± 3% -37.62% (p=0.004 n=6+5) | |
| ExpLarge/800-4 | 63.6s ± 2% | 35.4s ± 1% -44.33% (p=0.003 n=7+5) | |
| ExpLarge/1000-4 | 123s ± 0% | 64s ± 0% -48.39% (p=0.036 n=3+5) |
1条答案
按热度按时间bxgwgixi1#
https://golang.org/cl/256257提到了这个问题：
math/big: a fast expNN algorithm when n is large