☰

指数が増加しないように、各反復で指数を減らす指数関数をどのようにスクリプトできますか？

tag-icon • tag-icon bash shell-script bc math
指数が増加しないように、各反復で指数を減らす指数関数をどのようにスクリプトできますか？

Linuxに初めてアクセスし、このスクリプトを実行する際に問題があります。

多数を取り、残り（モジュロ）を使用して結果を保存する（メモリを節約するため）、いくつかの方法を研究してきました。

bashシェルを使用して78390 ^ 91025（mod 180577）を計算しようとしているので、基本78290を91025の累乗として使用し、モジュロ180577を適用します。

私は次のロジックを取得したいと思います：y = base for i = 1の指数

これにより、正しい結果を得ながらメモリと記憶領域を節約できます。

コードに触れていますが、今は実行できません。どこで台無しになりましたか？

#!/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)ます。最も簡単な方法は、実際に疑似コードに示されているようにbase（）に累算器を繰り返し掛けることです。これを行うBash関数は次のとおりです。k=78390x=91025n=180577k

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が提供するもの.)

a0 インデックスは、デフォルト（k^0 = 1、何でも）ではなく1を返す必要があるため、デフォルトではない1に初期化する必要がありますk。

代替実装bc:

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

当然、bcBashよりも速いです。

単純なループの代わりに、よりスマートな方法は次のとおりです。二乗乗算アルゴリズム。上記とは異なり、log2(x)操作のみを使用するため、はるかに高速ですx。

バッシュから：

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*18057764ビットに適しているので大丈夫です。）

ハードコーディングされた制限なしにオーバーフローを検出する簡単な方法は思い出せないので、どのような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（シェル関数内で呼び出しを維持することは容易ではありません。）

関連情報