「定数倍高速化」を編集中 (節単位)

===なるべく除算をしない===
<source lang="c">
unsigned long long repeat_add(
		unsigned long long a,unsigned long long b,unsigned long long c) {
	unsigned long long result=0;
	while(b>0) {
		if(b&1)result=(result+a)%c;
		a=(a<<1)%c;
		b>>=1;
	}
	return result;
}
</source>
このコードは、a,bがULLONG_MAX/2以下、cがULLONG_MAX/2+1以下のとき、
(a*b) mod cを[[オーバーフロー]]しないように気をつけながら求める[[プログラム]]である。

しかし、よく考えると、最初に与えられるaがc未満のとき、常にresult+a<2*c,(a<<1)<2*cが成り立つことがわかる。
よって、次のように書くことができ、重い[[除算]]が比較的軽い減算になるため高速化できる。
<source lang="c">
/* suppose that a<c */
unsigned long long repeat_add(
		unsigned long long a,unsigned long long b,unsigned long long c) {
	unsigned long long result=0;
	while(b>0) {
		if(b&1) {
			result+=a;
			if(result>=c)result-=c;
		}
		a+=a;
		if(a>=c)a-=c;
		b>>=1;
	}
	return result;
}
</source>