intの桁数計算の処理時間

intの桁数を求める方法は色々あれど、
どれが一番高速なのかずっと気になっていたため計算してみた。

 

3つの手法で計算

  1. log10の対数を使う
  2. 10での除算回数
  3. charへ変換してstrlen

 

結果

500万回ループして求めた測定結果

2<1<<3 の順で高速

  • 1はなにげに高速。2の2.7倍くらいの処理時間
  • 2が一番高速
  • 3は論外、面倒な上遅い。2の15倍位。

 

結論

最終的に簡潔に記述できるlog10で良さそう。一番良い結果の2.744倍程度だが一番簡潔。
本当に高速を求めることはそうそうないと思われる。(1回の変換時間は約70nsec)

組み込みなどで制限がある場合、math.hをinclude することでサイズ肥大化が気になるときに10除算回数を選択する感じ 

 

log10で計算するともっと時間がかかると思ってたので以外だった。

10で除算するときに、500万回int定義する時間が掛かったのもあるだろうけど。 

 

プログラム

#include <stdio.h>

#include <math.h>

#include <time.h>

#include <string.h>

#include <stdlib.h>

 

#define LOOP_NUM 5000000

 

int  digit_calc_log10(int);

int  digit_calc_division10(int);

int  digit_calc_strlen(int);

void function_loop(int (*p_function)(int));

 

int main(void){

    // 処理 Log10 ()

    function_loop(digit_calc_log10);

 

    // 処理 /10

    function_loop(digit_calc_division10);

 

    // 処理 strlen

    function_loop(digit_calc_strlen);

 

    return 0;

}

 

// 桁数をLog10で計算

int digit_calc_log10(int value){

    return log10(value) + 1;

}

 

// 桁数を10の除算で計算

int digit_calc_division10(int value){

    int digit = 0;

 

    while(value) {

        value /= 10;

        digit++;

    }

 

    return digit;

}

 

// 桁数をcharの長さで計算

int digit_calc_strlen(int value){

    char c_value[100];

    sprintf(c_value, "%d", value);

    return strlen(c_value);

}

 

// LOOP_NUM回p_function関数を繰り返す

void function_loop(int (*p_function)(int)) {

    clock_t start, end;

 

    start = clock();

    int digit;

    int value;

    for(value=1; value<LOOP_NUM; value++ ){

        digit = p_function(value);

//      printf("%d:%d\n", value, digit);

    }

    end = clock();

 

    printf( "処理時間:%d[ms]\n", end - start );

}

 

 実行結果

処理時間:343[ms]

処理時間:125[ms]

処理時間:1684[ms]

 

環境

コンパイラ:Cygwin gcc

CPU: Core 2 Quad Q9650 3.00GHz