問題タブ [exponentiation]

http://en.wikipedia.org/wiki/Exponentiation_by_squaringを二乗することにより、累乗を使用してバイナリを少しずつ処理する独自の pow() をロールしようとしています。これがこの問題について考えるのに役立つかどうか、この分野でいくつかの質問がありました。

Python でのフロートの組み込み pow() と math.pow() の違いは?

Python の ** および % 演算子の大きな数値での動作

自作 pow() c++

私はPythonを独学しているので、単純な間違いかもしれません。

出力は 31,21,12 で正しく、5,2,8 で間違っています。

これがどこで悲劇的に間違ったのかわかりません。

主要なテストのためにフェルマーの小定理を実装しようとしています。ここに私が書いたコードがあります：

注:a(<=n-1) asの値を取りました2。

現在、数 n は まで大きくすることができます10^18。これは、 variableexpが に近い値に到達できることを意味します10^18。これは、エクスプレッションがオーバーフローを引き起こす(exp*exp)ほど高くなる可能性があることをさらに意味します。10^36どうすればこれを回避できますか。

これをテストしたところ、 まで問題なく動作しました10^9。私はC++を使用しています

X基数とN指数の2 つのベクトルがあります。各inおよびinのすべての値の行列を取得したいと考えています。e = xnxXnN

たとえば、次の入力:

生成する必要があります:

ループせずにこれを取得する方法はありますか (列ごとの行積を使用して x×n のすべての値を取得できるように)?

SO に関する他のトピックでは、Brickell らによる論文「<a href="http://www.ccrwest.org/gordon/fast.pdf" rel="nofollow">Fast Exponentiation with Precomputation」について言及しました。 2 進数に対応する累乗の事前計算という単純な概念とともに、「巡回シフトによる累乗」に関する記述がありました (私の理解する限りでは)。残念ながら、論文のその部分は非常に一般的な形で表現されていたので、彼らが 2**n 以外の基数で洗練されたものになるような明白なことを話しているのか、それとも他のべき乗法が実際に存在するのか、私にはわかりません。乗算（二乗）よりも？

たとえば、あるとしましょうx = 5(これ00101は 2 進数です)。ビットシフトとおそらくいくつかの追加のみを使用して、 y = 5 * 5（バイナリで）最終的にどのようにすることができますか？11001もちろん、アルゴリズムは乗算よりも効果的である必要があります — 「ビットシフトと加算の束によって各乗算をエミュレートすることができます」という答えy = (5 << 2) + (5 << 0)はカウントされません。まあ、まばらな数が普通なら数えることはできますが、それは一般的なシナリオではなく、正確なビット母集団の数を決定するのにも時間がかかるので、数が非常にまばらでない限り、試す価値はありません。二乗するたびに、新しい評価が必要です。

寸法が 512 x 683 のマトリックスがあり、それを .8 と 1.2 に別々に上げてガンマ変換しようとしています。明らかに、非正方行列を累乗することはできないため、行列の各要素を .8 乗および 1.2 乗にするにはどうすればよいか考えていました。

ありがとう

ある関数で A を計算し、別の関数で B を計算している (A div B ) mod C を実行する方法は?