問題タブ [exponentiation]

Cで整数を別の整数で累乗する最も効率的な方法は何ですか?

.NETの組み込み関数は、基数を指数にMath.Pow()上げて結果を返します。doubledoubledouble

整数で同じことを行う最良の方法は何ですか?

追加: 結果を (int) にキャストできるようですがMath.Pow()、これは常に正しい数値を生成し、丸めエラーは発生しませんか?

これは実際にはプログラミングコンテストのためのものですが、私は本当に一生懸命に努力しましたが、これを行う方法についての最も微妙な手がかりさえも得ていません。

^{n m}の最初と最後のk桁を見つけます。ここで、nとmは非常に大きくなる可能性があります〜10^9。

最後のk桁については、べき乗剰余を実装しました。

最初のkについては、特定の累乗まで二項定理を使用することを考えましたが、階乗の計算が非常に多く、n ^ mを（x + y）として展開できる最適な点を見つける方法がわかりません。^m。

では、計算全体を実行せずに最初のk桁を見つける既知の方法はありますか？

更新1<=k <= 9であり、kは常にnmの<=桁になり^ます

さて、私はPHPスクリプトでいくつかの計算を行う必要があります。そして、私は間違った振る舞いをする1つの式を持っています。

出力10

出力0

出力1

1.000を出力します。

私はbcscale(100)BCMathの計算に使用しています。

ExcelとWolframMathematicaは答えを〜0,977237にします。

助言がありますか？

何かの二乗でフィルタリングしたい SPARQL クエリを作成しようとしていますが、数値 ( x ² ) を二乗する方法がわかりません (もちろん、それ自体を乗算することを除いて)。と呼ばれる平方根関数が機能すると推測しましたが、そのようなものは存在しmath:sqrt()ないようです。math:pow

SPARQL で何かの二乗を取得するにはどうすればよいですか? さらに重要なことに、それや SPARQL などの他の数学関数についてどこで読むことができmath:sqrtますか?

注: これは私の以前の質問に関連しています:逆ウィキペディア ジオタグ検索。

べき乗関数の何が問題になっていますか?

私の問題は(g^x) mod p、JavaScript ですばやく計算することです。^指数modはモジュロ演算です。すべての入力は非負の整数で、x約 256 ビットあり、p2048 ビットの素数であり、g最大 2048 ビットの場合があります。

JavaScript でこれを実行できるソフトウェアのほとんどは、JavaScript BigInt ライブラリ ( http://www.leemon.com/crypto/BigInt.html ) を使用しているようです。このライブラリでこのようなサイズの累乗を 1 回実行すると、遅いブラウザ (Firefox 3.0 と SpiderMonkey) で約 9 秒かかります。少なくとも 10 倍高速なソリューションを探しています。二乗と乗算 (二乗によるべき乗、http://en.wikipedia.org/wiki/Exponentiation_by_squaring ) を使用するという明白なアイデアは、2048 ビットの数値には遅すぎます: 最大 4096 の乗算が必要です。

ブラウザのアップグレードはオプションではありません。別のプログラミング言語を使用することはオプションではありません。番号を Web サービスに送信することはできません。

実装されているより高速な代替手段はありますか?

更新:以下の outis の回答に記載されている記事http://www.ccrwest.org/gordon/fast.pdfで推奨されているように、いくつかの追加の準備 (つまり、数百乗の事前計算) を行うことで、2048-最大で 354 のモジュラ乗算のみを使用するビット モジュラべき乗。(従来の平方乗算法は非常に遅く、最大 4096 の剰余乗算を使用します。) そうすることで、累乗剰余を Firefox 3.0 では 6 倍、Google Chrome では 4 倍高速化します。4096/354 の完全な高速化が得られない理由は、BigInt の累乗剰余アルゴリズムが、モンゴメリー削減 ( http://en.wikipedia.org/wiki/Montgomery_reduction )を使用するため、2 乗乗算よりも既に高速であるためです。 .

更新: BigInt のコードから始めて、手動で最適化された (およびインライン化された) カラツバ乗算 ( http://en.wikipedia.org/wiki/Karatsuba_algorithm ) の 2 つのレベルを実行する価値があるように思われ、その後でベース 32768 O( n^2) 乗算は BigInt で実装されます。これにより、2048 ビット整数の乗算が 2.25 倍高速化されます。残念ながらモジュロ演算は速くなりません。

更新: http://www.lirmm.fr/arith18/papers/hasenplaugh-FastModularReduction.pdf で定義されている修正された Barrett リダクションと、からつばの乗算と事前計算の累乗 ( http://www.ccrwest.org/gordon/で定義されている) を使用します。 fast.pdf )、Firefox 3.0 では、1 回の乗算に必要な時間を 73 秒から 12.3 秒に短縮できます。これは私ができる最善のようですが、それでも遅すぎます。

更新: Flash Player の ActionScript 2 (AS2) インタープリターは、Firefox 3.0 の JavaScript インタープリターよりも遅いように見えるため、使用する価値がありません: Flash Player 9 の場合は 4.2 倍遅く、Flash Player の場合は10、2.35倍遅いようです。数値計算における ActionScript2 と ActionScript3 (AS3) の速度の違いを知っている人はいますか?

更新: Flash Player 9 の ActionScript 3 (AS3) インタープリターは、JavaScript int Firefox 3.0 とほぼ同じ速度であるため、使用する価値はありません。

更新: Flash Player 10 の ActionScript 3 (AS3) インタープリターは、 の代わりに を使用し、intの代わりに を使用すると、Firefox 3.0 の JavaScript インタープリターよりも最大 6.5 倍高速になります。少なくとも、2048 ビットの大きな整数の乗算では 2.41 倍高速でした。そのため、可能な場合は Flash Player 10 で実行して、AS3 でべき乗剰余を実行する価値があるかもしれません。これは、Google Chrome の JavaScript インタープリターである V8 よりもまだ遅いことに注意してください。さまざまなプログラミング言語と JavaScript の実装の速度比較については、http://ptspts.blogspot.com/2009/10/javascript-and-actionscript-performance.htmlを参照してください。NumberVector.<int>Array

Update: There is a very fast Java solution, which can be called from the browser's JavaScript if the Java plugin is installed. The following solution is about 310 times faster than the pure JavaScript implementation using BigInt.

Can anyone translate this code to Silverlight (C#)?

特定のブロックで、実数を約 3*500*500 倍する必要があるアプリケーションを作成しています。exp(y*log(x)) アルゴリズムを使用すると、プログラムが著しく遅くなります。データ型の操作に基づいた別のアルゴリズムを使用すると大幅に高速になりますが、そのアルゴリズムはあまり正確ではありませんが、シミュレーションにはまともな結果が得られ、速度に関してはまだ完全ではありません。

exp(y*log(x)) よりも高速な実数の累乗の正確な累乗アルゴリズムはありますか?

前もって感謝します。

私はハスケルを使用してオイラープロジェクトの問題99を解決しています。ここでは、基本指数ペアのリストから最大の結果を見つける必要があります。

私はこれを思いついた：

番号の形式は次のとおりです。

なぜこれが機能しないのですか？数字の形式を変更する必要がありますか？より効率的なべき乗の方法のように、私が考えていない単純な最適化がここにありますか？

なぜこれが機能するのですか：

そして、これはスタックオーバーフローの例外を与えますか?