c - （n-乗算）vs（n /2-乗算+2加算）どちらが良いですか？

Question

n回の乗算（n回の反復による単一の乗算）を持つCプログラムがあり、（1回の乗算+ 2回の加算）のn/2回の反復を持つ別のロジックを見つけました。私は両方がO（n）であるという複雑さについて知っています。しかし、CPUサイクルの観点から。どちらが速いですか？

Answer 1

コンピューターでテストします。または、プロセッサの仕様を見て推測してください。

古いロジックは適用されなくなりました。最新のプロセッサでは、整数の乗算は非常に安価である可能性があります。一部の新しい Intel プロセッサでは、3 クロック サイクルです。これらの同じプロセッサでは、加算は 1 サイクルです。ただし、最新のパイプライン化されたプロセッサでは、データの依存関係によって作成されるストールにより、追加に時間がかかる場合があります。

私の推測では、折り畳み型の操作を行っている場合、N 個の加算 + N/2 個の乗算は N 個の乗算よりも遅く、マップ型の操作の場合は逆になると思います。しかし、これは推測にすぎません。

真実を知りたければテストしてください。

ただし、この単純なアルゴリズムのほとんどはメモリに依存しており、どちらも同じ速度になります。