Como criar um script de uma função exponencial que diminui o valor do expoente a cada iteração para que o expoente não cresça?

Question

Novo no Linux e tendo problemas para executar esse script.

Estou trabalhando em algo para pegar números grandes e usar o restante (módulo) para armazenar o resultado (para economizar memória).

Usando o shell bash, estou tentando calcular 78390 ^ 91025 (mod 180577) Então, usando a base 78290, o poder de 91025 e aplicando o módulo de 180577.

Desejo obter a seguinte lógica:  y = base  para i = 1 para o expoente-1  y: = (y * base) mod 'módulo'  proximo eu  imprimir y

Ao fazer isso, espero economizar memória e armazenamento enquanto ainda obtém o resultado correto.

Eu tenho mexido com o código e agora não consigo executá-lo. Onde estou bagunçando?

#!/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;
    }

    

Answer 1

OK, você deseja calcular k^x (mod n) com k=78390 , x=91025 , n=180577 . A maneira mais simples é, na verdade, multiplicar repetidamente a base ( k ) para um acumulador, como seu pseudo-código apresenta. Aqui está uma função Bash para fazer isso:

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

Agora, powmod 78390 91025 180577 imprime 125 . (O resultado concorda com o que o Wolfram Alpha dá .)

Note que você precisa inicializar a para um, não para a base, pois um expoente de zero deve retornar um, não a base ( k^0 = 1 , independentemente de k ).

Implementação alternativa em bc :

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

Não surpreendentemente, bc é mais rápido que o Bash.

Em vez do loop simples, uma maneira mais inteligente seria usar o algoritmo square-and-multiply . É significativamente mais rápido, já que usa apenas log2(x) de operações, em vez de x como o acima.

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

Isso é bastante rápido com números desse tamanho, mas observe que você obtém falhas silenciosas se os valores temporários ( a*k ou k*k , antes do módulo) ficarem maiores do que o Bash pode manipular. (Os números aqui estão bem, já que 180577*180577 cabe em 64 bits.)

Não consigo encontrar uma maneira trivial de detectar o estouro, sem codificar um limite, por isso, talvez você queira usar bc em qualquer 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

_{(Colocar a chamada em bc em uma função shell deve ser trivial.)}