1

乗算と除算 O(1) は、最も一般的に使用されているコンピューター アーキテクチャで実装されている方法ですか?

たとえば、x86 と ARM では、乗算と除算は O(1) ですか? Java の BigInteger クラスを使用して、BigInteger の 2 つのインスタンスを乗算または除算するとどうなりますか? これは明らかに O(1) ではないかもしれませんが、複雑さは何ですか?

4

2 に答える 2

3

BigIntegerOracle JDK では、乗算とBigDecimal除算の両方で O(M*N) です。

于 2013-09-22T03:53:43.137 に答える
1

任意の大きなオペランドの場合、複雑さが一定に保たれる可能性は非常に低いようです。それに追従する任意の大きなハードウェアを用意できない限り（そして、おそらく直線的に成長しないでしょう）。

あなたの質問に答えるには：システムや言語によって異なります。

ただし、「通常の」サイズの int については、ARM ドキュメントを参照してください。

たとえば、ARM アセンブリの乗算命令には、さまざまなサブセクションが含まれています。アセンブリ言語と特定の ARM プラットフォームを想定すると、公式ドキュメントを掘り下げることができます。これにより、乗算を実行するために必要なサイクル数が得られます。ARM は RISC マシンなので、そのようにすると便利です。次に、それをベンダーのチップ周波数と比較します。

たとえば、ARM7 プロセッサの場合。

また、ウィキペディアの Multiplication_algorithmもご覧ください。

于 2013-09-22T04:02:26.747 に答える