☰

如何编写一个指数函数脚本，该函数每次迭代都会减少指数值以使指数不会增长？

tag-icon • tag-icon bash shell-script bc math
如何编写一个指数函数脚本，该函数每次迭代都会减少指数值以使指数不会增长？

Linux 新手，运行此脚本时遇到问题。

一直在研究一些方法来获取大量数字并使用余数（模数）来存储结果（以节省内存）。

使用 bash shell 我试图计算 78390^91025(mod 180577) 因此使用基数 78290 的 91025 的幂并应用 180577 的模数。

我希望获得以下逻辑： y=base for i = 1 to the exponent-1 y := (y*base) mod 'modulus' next i print y

这样做时，我希望节省内存和存储空间，同时仍然获得正确的结果。

我一直在修改代码，现在无法让它运行..我在哪里搞砸了？

#!/bin/bash

#   k^x (mod n)
#   with k=78390, x=91025, n=180577 ?
#   Script runs but no output, 
#   pretty sure it is close

powmod() {
 let "a=1"
 let "k=$1"
 let "x=$2"
     let "n=$3"
     while (( x )); do
       if (( x % 2 )); then
            (( a = a*k % n ))
            (( x = x-1 ))
       fi
          (( k = k*k % n ))
            (( x = x/2 ))
     done
     echo $a;
    }

答案1

好吧，你想k^x (mod n)用k=78390, x=91025,来计算n=180577。最简单的方法确实是将基数 ( k) 重复乘以累加器，如伪代码所示。这是一个执行此操作的 Bash 函数：

powmod() { 
    local a=1 k=$1 x=$2 n=$3;
    for (( ; x; x-- )) { 
        (( a=a*k % n ));
    };
    echo $a;
}

现在，powmod 78390 91025 180577打印125. （结果符合Wolfram Alpha 给出了什么.)

请注意，您需要初始化a为 1，而不是基数，因为零指数应返回 1，而不是基数（k^0 = 1，无论k）。

替代实施bc：

k=78390
x=91025
n=180577
a=1
while (x > 0) {
    a=a*k % n
    x=x-1
}
a

毫不奇怪，bc比 Bash 更快。

除了简单的循环之外，更聪明的方法是使用平方乘算法。它的速度要快得多，因为它只使用log2(x)操作，而不是x像上面那样。

在 Bash 中：

powmod2() { 
    local a=1 k=$1 x=$2 n=$3;
    while (( x )); do 
        if (( x % 2 )); then
            (( a = a*k % n ))
            (( x = x-1 ))
        fi
        (( k = k*k % n ))
        (( x = x/2 ))
    done
    echo $a;
}

对于这种大小的数字来说，这是相当快的，但请注意，如果临时值（a*k或k*k，在模数之前）大于 Bash 可以处理的值，您会遇到静默失败。 （这里的数字很好，因为180577*180577适合 64 位。）

我无法想出一种在没有硬编码限制的情况下检测溢出的简单方法，因此您可能希望bc在任何情况下使用：

k=78390 
i=91025         
n=180577
a=1     
while (i > 0) {
        if (i % 2) {
                a=a*k % n
                i=i-1
        }
        k=k*k % n
        i=i/2
}    
a

bc（在 shell 函数中坚持调用应该是微不足道的。）

相关内容