从左向右与从右向左的模幂算法的mathematica子函数
(*从左向右与从右向左的模幂算法的mathematica子函数*)(*底只能是正整数,而不能是矩阵!!!!!!!*)
Clear["Global`*"];(*Clear all variables*)
(*从左向右的模幂算法子函数*)
PowerModLR:=(*三个参量依次是:底\指数\模*)
Module[
{
base=Mod,
exponent=exponent0,
modulus=modulus0,
result,array,k (*局部变量*)
},
result=1;(*最终的求解的模幂的结果*)
array=IntegerDigits;(*把指数写成二进制的形式*)
Do[ result=Mod;
If]==1,result=Mod],
{k,1,Length@array}
];(*end of Do Loop*)
result
]
(*从右向左的模幂算法子函数*)
PowerModRL:=(*三个参量依次是:底\指数\模*)
Module[
{
base=base0,
exponent=exponent0,
modulus=modulus0,
result (*局部变量*)
},
result=1;(*最终的求解的模幂的结果*)
While[
exponent>0,
If[ Mod==1,
(*如果是奇数按照下列方式处理,以及处理指数*)
result=Mod;exponent=exponent-1,
(*如果是偶数,按照下列方式处理,以及处理指数*)
base=Mod;exponent=exponent/2
](*end of if*)
];(*end of while*)
result
]
a=10^25+4;
e=500!;
n=142*29^2000+1;
(*检验模幂算法子函数写的是否正确,与mathematica的PowerMod函数比较*)
PowerModLR-PowerMod
(*检验模幂算法子函数写的是否正确,与mathematica的PowerMod函数比较*)
PowerModRL-PowerMod
Print["从左向右的模幂函数的计算时间"]
b=Timing@PowerModLR;b[]
Print["从右向左的模幂函数的计算时间"]
b=Timing@PowerModRL;b[]
Print["mathematica本身的模幂函数计算时间"]
b=Timing@PowerMod;b[]
计算结果如下:
Out= 0
Out= 0
During evaluation of In:= 从左向右的模幂函数的计算时间
Out= 0.5
During evaluation of In:= 从右向左的模幂函数的计算时间
Out= 0.703
During evaluation of In:= mathematica本身的模幂函数计算时间
Out= 0.469
不知道为什么从左向右的要比从右向左的更节省时间????????? 代码文件,不过请不要用mathematica打开,
我都是用vim打开,然后复制粘贴到mathematica的notebook中 只能是整数为底,如果想要非指数为底,请自己改写函数! 在做模幂算法时，将指数从左至右扫描，比从右至左扫描，可以减少临时变量的复制。
这是早有研究并有定论的。 在做模幂算法时，将指数从左至右扫描，比从右至左扫描，可以减少临时变量的复制。
这是早有研究并有定论的。
gxqcn 发表于 2012-7-16 10:59 http://bbs.emath.ac.cn/images/common/back.gif
看来还是你研究的比较多一些.
不过我是今天才知道的! (*从左向右与从右向左的模幂算法的mathematica子函数*)
(*地址:http://bbs.emath.ac.cn/thread-4462-1-1.html*)
Clear["Global`*"];(*Clear all variables*)
(*从右向左的模幂算法子函数*)
PowerModRL:=(*三个参量依次是:底\指数\模*)
Module[
{
base=base0,
exponent=exponent0,
modulus=modulus0,
result,array,k (*局部变量*)
},
result=1;(*最终的求解的模幂的结果*)
array=IntegerDigits;(*把指数写成二进制的形式*)
Do[ If[ array[]==1,
(*如果是奇数按照下列方式处理,以及处理指数*)
result=Mod
];(*end of If*)
(*如果是偶数,按照下列方式处理,以及处理指数*)
base=Mod,
{k,Length@array,1,-1}
];(*end of Do*)
result
]
(*从左向右的模幂算法子函数*)
PowerModLR:=(*三个参量依次是:底\指数\模*)
Module[
{
base=Mod,
exponent=exponent0,
modulus=modulus0,
result,array,k (*局部变量*)
},
result=1;(*最终的求解的模幂的结果*)
array=IntegerDigits;(*把指数写成二进制的形式*)
Do[ result=Mod;
If]==1,result=Mod],
{k,1,Length@array}
];(*end of Do Loop*)
result
]
a=10^25+4;
e=500!;
n=142*69^2000+1;
(*检验模幂算法子函数写的是否正确,与mathematica的PowerMod函数比较*)
PowerModLR-PowerMod
(*检验模幂算法子函数写的是否正确,与mathematica的PowerMod函数比较*)
PowerModRL-PowerMod
Print["从左向右的模幂函数的计算时间"]
b=Timing@PowerModLR;b[]
Print["从右向左的模幂函数的计算时间"]
b=Timing@PowerModRL;b[]
Print["mathematica本身的模幂函数计算时间"]
b=Timing@PowerMod;b[]
为了便于比较,我重新把两个方法的代码改写了一下,改成差不多的形式
从左向右的,只有一个result变量在不断被赋值,
而从右向左的,却有两个变量result与base在不断被赋值!
因此从左向右的比较节省时间!!!!!!!! 我从下面的地方知道从左向右的
http://www.google.com.hk/url?sa=t&rct=j&q=Modular+Exponentiation+using+Parallel+Multipliers&source=web&cd=1&ved=0CFEQFjAA&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.132.7490%26rep%3Drep1%26type%3Dpdf&ei=h7EDULGeIa69iAfrxbXzBw&usg=AFQjCNGVl6QJakWWjvLEqf0oLrzC-_777w 论文的题目叫做
Modular Exponentiation using Parallel Multipliers 没想到从左向右与从右向左还是有很大差别的!!!!!!!! Efficient modular exponentiation algorithms
http://eli.thegreenplace.net/2009/03/28/efficient-modular-exponentiation-algorithms/
页:
[1]
2