《编程原本 》一3.2 计算乘幂

简介: 本节书摘来自华章出版社《编程原本 》一书中的第3章,第3.2节,作者(美)斯特潘诺夫(Stepanov, A.),(美)麦克琼斯(McJones, P.),更多章节内容可以访问云栖社区“华章计算机”公众号查看

3.2 计算乘幂

对可结合运算op计算an的算法以a,n和op为参数,这里a的类型是op的定义域,n必须属于某个整数类型.如果没有可结合性假设,可以用两个算法分别完成从左到右或从右到左的计算:

template<typename I, typename Op> 
requires(Integer(I) && BinaryOperation(Op)) Domain(Op) power left associated(Domain(Op) a, I n, Op op) { 
// 前条件: n> 0 
if (n == I(1)) return a; 
return op(power left associated(a, n -I(1), op), a); } 
template<typename I, typename Op> 
requires(Integer(I) && BinaryOperation(Op)) Domain(Op) power right associated(Domain(Op) a, I n, Op op) { 
// 前条件: n> 0 
if (n == I(1)) return a; 
return op(a, power right associated(a, n -I(1), op)); }

这两个算法都应用相应的运算n.1次.对于非可结合的运算,它们可能返回不同结果.作为例子,请考虑减法运算的1到3次幂的结果.
当a和n都是整数而运算是乘法时,这两个算法给出的都是乘幂;运算是加法时两个算法做的都是乘法.古埃及人早已发现了更快的乘法算法,可以将其推广到计算任意可结合运算的幂.1
可结合性使人可以自由地将运算分组,由此可得
image

template<typename I, typename Op> 
requires(Integer(I) && BinaryOperation(Op)) 
Domain(Op) power 0(Domain(Op) a, I n, Op op) 
{ 
//前条件:associative(op)∧n>0
if (n == I(1)) return a; 
if (n % I(2) == I(0)) 
return power 0(op(a, a), n / I(2), op); 
return op(power 0(op(a, a), n / I(2), op), a); 
}

现在对指数n算一下power0执行运算的次数.递归调用的次数是.log2 n..令v为n的二进制表示里1的个数.每次递归调用执行一次运算求a的平方,还需要v.1次额外的运算调用,所以总运算次数是

.log2 n. +(v . 1) . 2.log2 n.

对于n = 15, .log2 n. =3,其表示中有4个1,公式给出的是6次运算.另一不同分组方式是a15 =(a 3)5 , 这里a 3 做2 次运算而a 5 做3次,总数为5.对另外一些指数也存在更快的分组方式,例如对23,27,39和43.2
powerleftassociated需要做n.1次运算,而power0最多做2.log2 n. 次运算.很明显,对于较大的n,power0总是快得多.但事情也不都这样.例如,要是做具有任意精度整数系数的一般多项式的乘法,powerleftassociated会更快些.3 还有,即使对这样的简单算法,我们也不知道如何精确描述一种复杂性需求,使之可用于确定两者中哪个更好.
power0能处理很大的指数,如10300 , 这使它在密码学中非常重要.

相关文章
|
1月前
|
编译器 C++
我的C++奇迹之旅:值和引用的本质效率与性能比较1
我的C++奇迹之旅:值和引用的本质效率与性能比较
|
1月前
|
存储 分布式计算 安全
我的C++奇迹之旅:值和引用的本质效率与性能比较2
我的C++奇迹之旅:值和引用的本质效率与性能比较
|
1月前
|
Java 程序员
揭秘编程世界的构造块:一文教你理解方法的本质与运用
揭秘编程世界的构造块:一文教你理解方法的本质与运用
12 0
|
监控 JavaScript Java
函数计算是如何工作的|学习笔记
快速学习 函数计算是如何工作的
145 0
【挑战】计算48种依次泛化的假设情况下,总共有多少种不可再简化的析合范式?
一种可行的算法: 由于属性泛化后,一个泛化的假设可以对应多个具体假设。 把所有假设按三属性泛化,二属性泛化,一属性泛化,具体属性排序(这样可以保证排在后面的假设不会包含前面的任何一个假设,所以省略了一些包含判断),进行循环枚举,按顺序遍历所有假设组合248种可能(当然绝大部分都提前结束了,不会是那么夸张的量级,虽然也不低): 使用栈来实现非递归,如果当前假设还有没被析合式所包含的具体假设,则认为可以入栈,并当前栈大小的长度计数加1,并继续扫描。
1084 0
|
程序员
《编程原本 》一1.4 过程
本节书摘来自华章出版社《编程原本 》一书中的第1章,第1.4节,作者(美)斯特潘诺夫(Stepanov, A.),(美)麦克琼斯(McJones, P.),更多章节内容可以访问云栖社区“华章计算机”公众号查看
912 0
|
人工智能 JavaScript C++
《编程原本 》一3.4 处理特殊情况的过程
本节书摘来自华章出版社《编程原本 》一书中的第3章,第3.4节,作者(美)斯特潘诺夫(Stepanov, A.),(美)麦克琼斯(McJones, P.),更多章节内容可以访问云栖社区“华章计算机”公众号查看
1129 0
《编程原本 》一2.6 总结
本节书摘来自华章出版社《编程原本 》一书中的第2章,第2.6节,作者(美)斯特潘诺夫(Stepanov, A.),(美)麦克琼斯(McJones, P.),更多章节内容可以访问云栖社区“华章计算机”公众号查看
766 0
|
机器学习/深度学习 人工智能 JavaScript
《编程原本 》一3.3 程序变换
本节书摘来自华章出版社《编程原本 》一书中的第3章,第3.3节,作者(美)斯特潘诺夫(Stepanov, A.),(美)麦克琼斯(McJones, P.),更多章节内容可以访问云栖社区“华章计算机”公众号查看
1161 0
《编程原本 》一1.8 总结
本节书摘来自华章出版社《编程原本 》一书中的第1章,第1.8节,作者(美)斯特潘诺夫(Stepanov, A.),(美)麦克琼斯(McJones, P.),更多章节内容可以访问云栖社区“华章计算机”公众号查看
883 0