問題タブ [exponentiation]

編集 - 明確化

ラグランジュと中国剰余定理を使用して、Java でべき乗剰余を実装しようとしています。

たとえば、素因数 5 と 11 が与えられた場合、N が 55 の場合、ファイは 40 です。したがって、55 未満の N に互いに素な数が 40 あることがわかります。 、5 と 11 を法とする数回の乗算と、両方の結果を結合するための CRT」

私の問題は、これらの数値をどのように計算するかです。計算を完了するためにそれらを中国の剰余定理に入れる必要がありますが、結果として phi(n) を使用して N を循環させる賢い方法は思いつきません。N は非常に大きな数になり、少なくとも 1024 ビットになります。ここで間違った方向に進んでいる可能性があります。これらすべての素数が必要ですか?

答えは拡張されたユークリッド関数に関連していると思われます。これはすでにコーディングしているので、その結果を使用する必要がある場合は問題ありません。

How many numbers below N are coprimes to N?のコードがわかりません。私にとってはあまり役に立ちませんし、私が見ている数学の論文を理解するのは非常に難しいと思います.合計と積のタイプの表記法は私を少し困惑させます. また、一部の回答では、実際には BigInteger のオプションではない平方根とログを使用しています (間違っている場合は修正してください)。

だれか平易な英語で答えてくれませんか??

コードを見せても問題ありません。提出する回答はモンゴメリーを使用しているため、これは学習課題です。(ええ、知っています。数学の公式からモンゴメリーを計算できるのは奇妙ですが、このラグランジュと CRT には完全に困惑しています)

私はこれまで、私が見つけた例に取り組みました。素因数は 7 と 5 であるため、35 の phi は 24 です (私は有効な Euler totient 関数を持っています)。

これは、Scheme を使用して教えられたプログラミング入門クラスの個人的な課題ですが、Python の例も同様に満足しています。

次のように、スキームで剰余累乗のバイナリメソッドを既に実装しています。

Chez スキームには python の pow (base expo modu) に似た実装がないため、これが必要です。

現在、剰余乗算を解くモンゴメリー法を実装しようとしています。例として、私は持っています：

RR' - NN' = 1 の解き方を理解しようとしています。R' の答えは 64 であり、N' は 81 である必要がありますが、ユークリッド アルゴリズムを使用してこの答えを得る方法がわかりません。 .

非常に大きな累乗モジュロ (2^32) を計算する必要があります。つまり、次の結果が必要です。

Javaでこれを効率的に行うための秘訣はありますか?

それとも、n回の反復でループでそれを行うことに固執していますか?

剰余累乗のコードに何か問題があり、疑似コードの 2 つの異なるソースを使用して 3 回書いたにもかかわらず、問題を見つけることができません。SE 上の C++ での累乗剰余に関する他の質問を読みましたが、役に立ちませんでした。これが私の最後のコードで、私が思うより単純だが最適ではない方法で書かれています:

ある数のn乗[A^n = A * A ^（n-1）]を再帰的に見つけ、ショートカットA ^（2n）= A ^ n * A^nを使用する述語を書き込もうとしています。

これがこれまでの解決策です。

ここで、この末尾再帰を作成します。階乗やパワーなどの単純なケースでは、ショートカットなしで（アキュムレータを追加することで）テールを実行できますが、これは困難です。

どんな助けでも大歓迎です！

Prolog プログラムを使用して級数の和を求めたい。この目的のために、次のプログラムを作成しました。

次のシリーズの合計を見つけたい：

私の考えでは、上記のコードは正しいです。しかし、プログラムを実行すると、出力 "No" が表示されます。なんで ？いろいろ試しましたが、期待通りの結果が得られませんでした。

いくつかの16進数を読み取った後、それらを基数2^64に変換したいと思います。残念ながら、この数値はintに格納できないため、GMPにはこの問題の解決に役立つ関数がないようです。

私が完全に欠けているこれを行う別の方法はありますか？

（プログラムはCです）

累乗を含むJavaScriptでいくつかの計算があります。

この文が値 1 を返す理由を誰か教えてください。

ありがとう

Rで文字列の行列を操作する関数を定義しようとしています.

{+,*} 行列の乗算

次元 nの 2 つの正方行列AとBの {+,*} 積は、次の要素で定義される 行列Cです: C _i,j = Sum _k=1,...,n A _i,k * B _{k, j} .

たとえば、行列を考えてみましょう M <- matrix(c(a,b,0,0,c,d,0,0,e),3,3)。M かける M は M <- matrix(c(a^2,a*b+b*c,b*d,0,c^2,c*d+d*e,0,0,e^2),3,3)です。

{c(,),paste0(,)} 行列の乗算

私が実装したいこの操作のルールは、前に述べた乗算と同じですが、合計は連結であり、積はペーストでなければならないという本質的な変更があります。言い換えると、前の式で が見つかっa+bた場合、出力は "c(a,b)" になるはずであり、 が見つかった場合はa*b、これを と読む必要がありますpaste0(a,b)。

通常のプロパティのいくつか、つまり分配プロパティと 0 要素プロパティを尊重する必要があります。したがって、ifa <- c("q",0,"w")およびb <- c("e")then a*b <- c("qe",0,"we")(そして、計算に影響しないため、0 要素を自由に削除する必要があります。

さらに、等次元行列を乗算しているため、各要素 C _i,j = Sum _k=1,...,n A _i,k * B _k,jは として読み取られることになります c("A[i,1]B[1,j]",...,"A[i,n]B[n,j]")。

簡単にするために、 Bは常に単純な行列であると考えてみましょう。つまり、その各要素は文字列の連結ではなく、アトミック文字列であることを意味します (一般化は後続のステップです)。

例を挙げましょう。A <- matrix(c("a","b",0,0,"c","d",0,0,"e"),3,3)、そしてmult(A,A) = matrix(c("aa",c("ab","bc"),"bd",0,"cc",c("cd","de"),0,0,"ee"),3,3) 、としましょう mult(mult(A,A),A) = matrix(c("aaa",c("aab","abc","bcc"),c("abd","bcd","bde"),0,"ccc",c("ccd","cde","dee"),0,0,"eee"),3,3)。

部分的な (動作しない) 実装

0 または文字列の配列 c( s ₁ , s ₂ ,...) をi,j要素とするnxn 行列M , Nのペアを入力として考えます。出力として、乗算がシンボリック乗算と同様に定義される行列MN = M x Nが必要です。

Ｍ ｉ，ｊ の場合、 Ｍ_ｉ，ｊ＝０である_。またはN _.,jは 0 MN _i,j = paste( M _i,. , N _.,j ) それ以外の場合 ( の分配特性を使用)
paste()

ベースの行/列の貼り付け機能の（間違って、ゼロを適切にチェックしません）定義を次のように与えました

行列内に挿入したい要素 Mij が正しい次元ではないため、このステップから乗算関数の適切な定義に進むことができませんでした。したがって、number of items to replace is not a multiple of replacement lengthエラーが発生します。私の現在の実装は次のとおりです。

コードが機能しません。おそらく行列を多次元配列に変更できますが、出力をさらに乗算するための行列として使用できるようにしたいと思います (たとえば、(MxN)xC を定義するため)。

どのようにできるのか？

ありがとうございました！

PS簡単なサンプルマトリックスを使用してコードをテストできます

そして走っている

を計算しようとしています。a^(1/n)ここで、^べき乗を示します。

ただし、次のとおりです。

を返す1.0代わりに を返し2.0ます。

何故ですか？