从左向右与从右向左的模幂算法的mathematica子函数

mathematica

其中有一句话:Relative performance
As I’ve noted in the previous article, the RL method does a worse job of keeping its multiplicands low than the LR method. And indeed, for smaller n, RL is somewhat faster than LR. For larger n, RL is somewhat slower.

What’s obvious is that now the built-in pow is superior to both hand-coded methods [4]. My tests show it’s anywhere from twice to 10 times as fast.

Why is pow so much faster? Is it only the efficiency of C versus Python? Not really. In fact, pow uses an even more sophisticated algorithm for large exponents [5]. Indeed, for small exponents the runtime of pow is similar to the runtime of the implementations I presented above.

mathematica

在做模幂算法时，将指数从左至右扫描，比从右至左扫描，可以减少临时变量的复制。
这是早有研究并有定论的。
gxqcn 发表于 2012-7-16 10:59

看来你也经历过失败,然后发现从左向右的比从右向左的快!

mathematica

从左向右的,只有一个result变量在不断被赋值,
而从右向左的,却有两个变量result与base在不断被赋值!
因此从左向右的比较节省时间!!!!!!!!

mathematica 发表于 2012-7-16 14:09

gxqcn,我的这个解释正确吗?????????

wayne

可以类比 循环语句里的  i++ 与 ++i 的区别

mathematica

http://www.freewl.com/gb/index.asp?user=emath
留言板！！！！！！！！！

mathematica

顶！！！！！！！！