除算アルゴリズム

Linuxカーネルでは一般的に除算演算は使用されません.kernelが除算をするのは不便で、効率が低いはずです.一連の浮動小数点演算に関連しています.
次はLinuxカーネルでの時間管理を学ぶときに見られるアルゴリズムで、特に取り出して考えてみましょう.
プリペイドアルゴリズム:

void
clocks_calc_mult_shift(u32 *mult, u32 *shift, u32 from, u32 to, u32 minsec)
{
	u64 tmp;
	u32 sft, sftacc= 32;

	/*
	 * Calculate the shift factor which is limiting the conversion
	 * range:
	 */
	tmp = ((u64)minsec * from) >> 32;
	while (tmp) {
		tmp >>=1;
		sftacc--;
	}

	/*
	 * Find the conversion shift/mult pair which has the best
	 * accuracy and fits the maxsec conversion range:
	 */
	for (sft = 32; sft > 0; sft--) {
		tmp = (u64) to << sft;
		do_div(tmp, from);
		if ((tmp >> sftacc) == 0)
			break;
	}
	*mult = tmp;
	*shift = sft;
}

本質は次のとおりです.
将
times_elapse = cycles_interval/frequency

変換:times_elapse = cycles_interval * mult >> shift
このような変換には必ず誤差があるので,誤差の範囲を定義する精度が必要である.
パラメータの説明:

u32 *mult   	      mult  

u32 *shift	      shift  

u32 from	frequency  

u32 to		

u32 minsec

demo:

#include
#include

typedef unsigned int u32;
typedef unsigned long long u64;

#define NSEC_PER_SEC 1000000000L

void
clocks_calc_mult_shift(u32 *mult, u32 *shift, u32 from, u32 to, u32 maxsec)
{
    u64 tmp;
    u32 sft, sftacc= 32;

    /*
     * * Calculate the shift factor which is limiting the conversion
     * * range:
     * */
    tmp = ((u64)maxsec * from) >> 32;
    while (tmp) {
            tmp >>=1;
            sftacc--;
        }

    /*
     * * Find the conversion shift/mult pair which has the best
     * * accuracy and fits the maxsec conversion range:
     * */
    for (sft = 32; sft > 0; sft--) {
            tmp = (u64) to << sft;
            tmp += from / 2;
            //do_div(tmp, from);
            tmp = tmp/from;
            if ((tmp >> sftacc) == 0)
                break;
        }
    *mult = tmp;
    *shift = sft;
}


int main()
{ 

    u32 tsc_mult;
    u32 tsc_shift ;

    
    u32 tsc_frequency = 2127727000/1000; //TSC frequency(KHz)
    clocks_calc_mult_shift(&tsc_mult,&tsc_shift,tsc_frequency,NSEC_PER_SEC/1000,600*1000); //NSEC_PER_SEC/1000   TSC    clocksource_register_khz

    fprintf(stderr,"mult = %d shift = %d
",tsc_mult,tsc_shift);
    return 0;
}

600はTSC clocksourceのMASKから算出した入参で、興味があれば自分で推計して結果を見ることができます.
mult = 7885042 shift = 24 root@manu:~/code/c/self/time# python Python 2.7.3 (default, Apr 10 2013, 05:46:21)  [GCC 4.6.3] on linux2 Type "help", "copyright", "credits"or "license"for more information. >>> (2127727000*7885042)>>24
1000000045L >>>