Как написать сценарий экспоненциальная функция, которая уменьшает значение показателя на каждой итерации, чтобы показатель не увеличивался?

Bien, quieres calcular k^x (mod n)con k=78390, x=91025, n=180577. De hecho, la forma más sencilla es multiplicar repetidamente la base(k)por un acumulador, como presenta su pseudo código -. Aquí hay una función Bash para hacer eso:

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

Ahora, powmod 78390 91025 180577imprime 125. (El resultado concuerda con lo que da Wolfram Alpha .)

Tenga en cuenta que debe inicializar aa uno, no a la base, ya que un exponente de cero debe devolver uno, no la base (k^0 = 1, independientemente dek).

Implementación alternativa enbc:

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

No es sorprendente que bcsea más rápido que Bash.

En lugar del bucle simple,una forma más inteligente sería usar el cuadrado -y -algoritmo de multiplicación . Es significativamente más rápido, ya que solo usa operaciones log2(x), en lugar de xcomo lo hace el anterior.

En Golpe:

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;
}

Eso es bastante rápido con números de este tamaño, pero tenga en cuenta que obtiene fallas silenciosas si los valores temporales(a*ko k*k, antes de que el módulo )sean más grandes de lo que Bash puede manejar. (Los números aquí están bien, ya que 180577*180577cabe en 64 bits.)

No puedo pensar en una forma trivial de detectar el desbordamiento, sin codificar -un límite, por lo que es posible que desee usar bcen cualquier caso:

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

_{(Pegar la llamada a bcen una función de shell debería ser trivial.)}