複数のプロセッサを使用して (大きな) 定数を法として大きな整数を乗算するための時間の複雑さについて知りたいと思っています。要するに、除算と剰余は乗算を使用して実装することもできるため、基本的には単なる整数乗算です (例:逆数乗算またはバレット削減)。
現在知られている整数乗算アルゴリズムの実行時間は、下限によっておおまかに制限されていることを知っていますo(n * log n)。私の調査では、これがシングル コアまたはマルチ コア マシン用であるかどうかを確認できませんでした。ただし、アルゴリズムは分割統治法を使用しているように見えるため、これはシングルコアマシン用であると考えています。
m私の質問は、コアに実装された並列整数乗算アルゴリズムの時間計算量の現在知られている下限は何ですか? o(n)十分なコアが与えられた場合、下限以下の時間計算量を達成できますか? (つまり ifは ?mに依存しnます) ここでo(n)は、手元にある整数の入力サイズについて説明します。
これまでの私の研究では、並列 FFT 乗算を使用した高速化を主張するいくつかの論文を読みました。残念ながら、これらは経験的な高速化 (たとえば、「これこれのコンピューターで 6 コアを使用して 56% の速度向上」) を主張するだけであり、時間の複雑さの境界で表される理論的な高速化を説明できません。
「最速」の整数乗算アルゴリズムがまだ見つかっていないことは承知しています。これはコンピューター サイエンスの未解決の問題です。私は単に、そのような並列アルゴリズムの現在知られている範囲について調べているだけです。
更新 #1 : ユーザー @delnan がNC 複雑性クラスに関する wiki ページにリンクしました。そのwikiページでは、整数乗算はNCにあると述べています。つまり、プロセッサにO((log n)^c)アルゴリズムが存在します。O(n^k)これは、答えに近づくのに役立ちます。今のところ答えられていない部分は、整数乗算のcおよびk定数とは何か、またどの並列アルゴリズムがこの目的に適しているかということです。
更新 #2 :コーネル大学のコンピューター サイエンス コースのこの PDF ファイルの 12/15 ページによると、NC 複雑度クラスの整数乗算はプロセッサでO(log n)時間がかかります。O(n^2)また、これを行う方法についてのアルゴリズムの例についても説明します。この質問に対する適切な回答をすぐに書きます。
私の好奇心を満たすための最後の質問: "just"またはプロセッサの現在知られている時間の複雑さについて何か知っている人はいO(n)ますか?O(sqrt(n))O(log n)