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 180577
imprime 125
. (El resultado concuerda con lo que da Wolfram Alpha .)
Tenga en cuenta que debe inicializar a
a 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 bc
sea 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 x
como 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*k
o 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*180577
cabe 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 bc
en 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 bc
en una función de shell debería ser trivial.)
Поскольку вы упомянули bash, другой вариант — его оператор сопоставления с образцом=~
:
if [[ $process =~ ^cmd[[:space:]].*name([[:space:]]|$) ]]
then
_name_ was found as an argument to _cmd_
fi
Это проверяет, начинается ли содержимое переменной с cmd
, за которым следует пробел, за которым следует что-либо -или -ничего, за которым следует name
, за которым следует :пробел или конец линии.