void dec_exp(Decimal *result, const Decimal *a, unsigned int b)
{
Decimal tmp, power = *a;
dec_parse(result, "1");
while (b)
{
if (b & 1)
{
tmp = *result;
dec_mul(result, &tmp, &power);
}
if (b >>= 1)
{
tmp = power;
dec_mul(&power, &tmp, &tmp);
}
}
}其中，Decimal是包含十进制值的结构变量，它的长度和小数点所在的位置。
在函数中传递了参数：a为基值，b为幂，result将存储计算后的值a^b。dec_parse(Decimal &x,string y)将y解析为十进制，并提取小数点位置等信息，修剪前导零和尾随零，并将字符串转换为Decimal结构变量。dec_mul(Decimal result, Decimal &x, Decimal &y)将x和y相乘，并将相乘后的值存储在result中。
我只想知道两个“if条件”在while循环中是如何工作的，while循环何时终止，以及代码段的时间复杂度。
2条答案
按热度按时间deikduxw1#
这是在
b是非负整数的特殊情况下计算(*a)。变量
result初始化为1（注意a0对于所有a都是1）并且power被初始化为a的内容。如果b为奇数，则result乘以power（第一个if）。第二个if将b右移一位（也就是说，除以2），如果它仍然是正的，它就平方power。换句话说，power包含(*a)2n的逐渐增大的值。这是一个相当有效且容易实现的（但不是最优的）算法，用于计算ab。最优算法是NP难的，并且（潜在地）需要大量内存。该算法易于编码，并且需要最少的内存。
忽略多余的乘1运算，此算法在
b=0到b=14的情况下是最优的，在a15的情况下是次优的。此算法的计算公式为a15a*a2*a4*a8，最佳计算（对decimal的调用次数最少的计算）是a3=a*a*a;a15 =a3 *（（a3）2）2，或者五个乘法。这个算法的另一个名字是从右到左二进制取幂。
b的位（1位），并逐渐作用于b的更高有效位。换句话说，从右到左。从左到-右二进制取幂在x1M35 N1 x的最高有效位开始，并且逐渐地在x1M36 N1 x的较低有效位上工作。在将多余的乘法消除一次之后，两种算法使用完全相同的乘法次数。这不是“最优”算法，其中最优意味着“最少的乘法次数”。例如，从右到左和从左到右的二进制取幂算法计算x15和x31为
但是，由于15=（4+1）3，31=152+1=（（4+1）3）2+1和31=74+3=（32+1）*4+3，我们还可以写：
与二进制求幂相比，所有这些都需要少一个乘法运算。（最后的表达式需要缓存中间结果x3，以避免计算两次。）我不知道我的x31的表达式是否是最优的。即使对于很小的数字，也很难找到最优表达式。您必须查看xn的所有不同表达方式，请记住，一般的中间结果只需要计算一次。如上所述，这是NP难的。实际上，二进制取幂虽然不是最优的，但已经足够好了。
ogsagwnx2#
b & 1测试B是否为奇数。如果是，则将result设置为tmp * power。b >>= 1将B除以2。如果结果不为零，则将tmp设置为power，并将power设置为tmp * tmp。最后，
b被2除得太多以至于达到0，这结束了while循环。该算法是所谓的“Russian Peasant multiplication“的推广，称为“Exponentiation by squaring“。相同的基本过程可用于取幂而不是乘法，通过对中间结果求平方（我们在第二个
if测试中看到）而不是加倍。时间复杂度与
b中的最高置位成正比;如果b中的最高设置位是bit K，则循环将迭代 K 次。也就是说，时间复杂度与b的以2为底的对数成比例。