C++における除算と乗算の速度比較

除算は他の演算と比べて重い処理だそうです。
今回は素数を求めるプログラムを例に検証してみたいと思います。

C++を使いますが、他の言語でも概ね同じことが言えると思います。
また、プログラムに穴がありますが話を単純にするためということでご容赦ください。

検証方法

以下のランダムに生成した19桁の素数を使って実行速度の平均を比較します。
素数の生成はこちらのサイトで行いました。
素数ジェネレータおよび素数チェッカー

8764234445678654651
1000000007650000061
9865445665456543571
4324677654356765473
2579997656754323467

まずは除算から

#include <iostream>
#include <ctime>
using namespace std;

void Judge_primeNum(unsigned long int i);

int main() {

    unsigned long int num = 0;
    cin >> num;

    clock_t start = clock();    //計測開始

    Judge_primeNum(num);

    clock_t end = clock();     //計測終了

    cout << (double)(end - start) / CLOCKS_PER_SEC << " sec." << endl;

    return 0;
}

void Judge_primeNum(unsigned long int num){
    for(int i = 2; num >= (num/ i) >= i; i++) {    //除算
        if(num % i == 0 && num != i){
            cout << "not prime" << endl;
            return;
        }
    }
    cout << "prime" << endl;
    return;
}
実行結果

8764234445678654651 : 32.504 sec.
1000000007650000061 : 15.1937 sec.
9865445665456543571 : 32.5616 sec.
4324677654356765473 : 31.4624 sec.
2579997656754323467 : 24.1967 sec.
Average : 27.18368 sec.

続いて乗算

#include <iostream>
#include <ctime>
using namespace std;

void Judge_primeNum(unsigned long int i);

int main() {

    unsigned long long int num = 0;
    cin >> num;


    clock_t start = clock();

    Judge_primeNum(num);


    clock_t end = clock();

    cout << (double)(end - start) / CLOCKS_PER_SEC << " sec." << endl;

    return 0;
}

void Judge_primeNum(unsigned long int num){
    for(int i = 2; num >= i * i; i++) {          //乗算
        if(num % i == 0 && num != i){
            cout << "not prime" << endl;
            return;
        }
    }
    cout << "prime" << endl;
    return;
}
実行結果

8764234445678654651 : 0.001361 sec.
1000000007650000061 : 0.001269 sec.
9865445665456543571 : 0.001403 sec.
4324677654356765473 : 0.001302 sec.
2579997656754323467 : 0.000562 sec.
Average : 0.0011794 sec.


うーん、とてつもない速さですね。
除算が遅いってのは割と常識な話みたいですね、知りませんでした。
最近のハードは昔と違って高性能なので、普段コーディングする際は
あまり意識することはないかもしれませんが、もの凄い回数のループを
回す時なんかはかなりパフォーマンスに差が出そうですね。



ちなみに実行環境は以下の通りです。
f:id:noiu:20170620205322p:plain