ここでは、解決策に到達するためにいくつかの観測を収集します。
- 標準 C >= 1999 では、基数 2 の数値に期待されるように、非負の整数がビット単位で表現されることが保証されています。
-> したがって、このタイプの数値のビット操作を信頼できます。
- が符号なし整数型の場合
x
、tnenx >> 1 == x / 2
およびx << 1 == x * 2
.
(!) ただし: ビット操作は、対応する算術演算よりも高速に実行される可能性が非常に高くなります。
sqrt(x)
は と数学的に同等exp(log(x)/2.0)
です。
- 切り捨てられた対数と整数の基数2 の指数を考慮すると、次
IntExp2( IntLog2(x) / 2) "==" IntSqrtDn(x)
の公正な推定値を得ることができます。 "="
- と書く
IntExp2( IntLog2(x) / 2 + 1) "==" IntSqrtUp(x)
と、整数平方根の「上の」近似が得られます。
- (4.) と (5.) で得られた近似は少し大雑把です (2 の連続した 2 乗の間に sqrt(x) の真の値を囲んでいます) が、これらは、の角屋根用
x
。
- 平方根のニュートン アルゴリズムは、実際の解に対する適切な最初の近似があれば、整数に対してうまく機能する可能性があります。
http://en.wikipedia.org/wiki/Integer_square_root
最終的なアルゴリズムは、常に適切に動作することを十分に確認するために、いくつかの数学的計算を必要としますが、今は実行しません... 代わりに、最終的なプログラムを示します。
#include <stdio.h> /* For printf()... */
#include <stdint.h> /* For uintmax_t... */
#include <math.h> /* For sqrt() .... */
int IntLog2(uintmax_t n) {
if (n == 0) return -1; /* Error */
int L;
for (L = 0; n >>= 1; L++)
;
return L; /* It takes < 64 steps for long long */
}
uintmax_t IntExp2(int n) {
if (n < 0)
return 0; /* Error */
uintmax_t E;
for (E = 1; n-- > 0; E <<= 1)
;
return E; /* It takes < 64 steps for long long */
}
uintmax_t IntSqrtDn(uintmax_t n) { return IntExp2(IntLog2(n) / 2); }
uintmax_t IntSqrtUp(uintmax_t n) { return IntExp2(IntLog2(n) / 2 + 1); }
int main(void) {
uintmax_t N = 947612934; /* Try here your number! */
uintmax_t sqrtn = IntSqrtDn(N), /* 1st approx. to sqrt(N) by below */
sqrtn0 = IntSqrtUp(N); /* 1st approx. to sqrt(N) by above */
/* The following means while( abs(sqrt-sqrt0) > 1) { stuff... } */
/* However, we take care of subtractions on unsigned arithmetic, just in case... */
while ( (sqrtn > sqrtn0 + 1) || (sqrtn0 > sqrtn+1) )
sqrtn0 = sqrtn, sqrtn = (sqrtn0 + N/sqrtn0) / 2; /* Newton iteration */
printf("N==%llu, sqrt(N)==%g, IntSqrtDn(N)==%llu, IntSqrtUp(N)==%llu, sqrtn==%llu, sqrtn*sqrtn==%llu\n\n",
N, sqrt(N), IntSqrtDn(N), IntSqrtUp(N), sqrtn, sqrtn*sqrtn);
return 0;
}
に格納された最後の値sqrtn
は、 の整数平方根ですN
。
プログラムの最後の行には、すべての値が表示されます。
したがって、さまざまな値を試して、N
何が起こるかを確認できます。
while ループ内にカウンターを追加すると、数回の繰り返ししか発生しないことがわかります。
備考:abs(sqrtn-sqrtn0)<=1
整数値設定で作業する場合は、必ず条件が成立することを確認する必要があります。そうでない場合は、アルゴリズムを修正する必要があります。
注意 2:初期化文では、次のことに注意してsqrtn0 == sqrtn * 2 == sqrtn << 1
ください。これにより、いくつかの計算が回避されます。