Algorithm 問題を解く 1 - 平方根計算

問題

Implement a fast integer square root function 1 that takes
in a 32-bit unsigned integer and returns another 32-bit unsigned integer
that is the floor of the square root of the input.
There are many variants of searching a sorted array that require a little more thinking and create opportunities for missing corner cases. For the following problems, A is a sorted array of integers.
( 出典: Algorithms for interviews )

一言でいうと，一つの32ビットの符号なし整数を引数に取り，その平方根の切り下げた32ビット整数型の帰り値を返す，関数を実装せよ，所与としてソートされた整数の配列がある，ということだ．基本的な問題だが，解いていると楽しいもの．

解

高校の数学を思い返せば，以下を証明で使ったことをきっと思い出すはずだ．

mとnの２数があってm < nなら
m^2<= x < n^2

問題文の "A is a sorted array of integers"と上記のm^2<= x < n^2 を見ると．．うーん，あのデータ構造がﾄﾞﾔｧって顔をしてるね．

#include <stdio.h>

#include <stdlib.h>

unsigned my_sqrt(unsigned val) {

unsigned st = 0;

unsigned end = val + 1;

unsigned mid = 0;

while(end - st > 1) {

mid = (st + end)/2;

printf("st-%d,end-%d,mid-%d\n",st,end,mid);

if(mid * mid <= val)

st = mid;

else

end = mid;

}

return st;

}

int main(int argc, char **argv) {

printf("sqrt of %d is %d\n", atoi(argv[1]),my_sqrt(atoi(argv[1])));

return EXIT_SUCCESS;

}

アウトプットは

st-0,end-66,mid-33,mid*mid-1089

st-0,end-33,mid-16,mid*mid-256

st-0,end-16,mid-8,mid*mid-64

st-8,end-16,mid-12,mid*mid-144

st-8,end-12,mid-10,mid*mid-100

st-8,end-10,mid-9,mid*mid-81

sqrt of 65 is 8

ちなみに出典に書いてある解は正しくない(笑．

これは32bitの平方根は必ず１６ビットの間に収まる，という事実を上手く捉えた面白い回答なんだけども．

( 実際，Powershellで以下のステートメントを実行してみると
[Math]::floor([Math]::sqrt([UInt32]::MaxValue));
答えは65535，つまり符号なし16ビット整数の最大値．)

以下が本にのってた答えをCで書いたもの．65とかのインプットだと動かないよ．
st = 5, end = 16でmid = 5になって詰み．一つでも動かすとオーバーフローでボンッ！だ．


#define MINIMUM_UINT16BIT 0
#define MAXNUM_UINT16BIT 65535

unsigned my_sqrt_wrong(unsigned val) {

int st = MINIMUM_UINT16BIT;
int end = MAXNUM_UINT16BIT + 1;
unsigned mid = 0;
unsigned midVal = 0;
while(st + 1 < end) {
mid = (end - st) / 2;
printf("st-%d,end-%d,mid-%d,mid*mid-%d\n",st,end,mid,mid*mid);
midVal = mid * mid;
if( midVal == val )
return mid;
else if(midVal > val)
end = mid;
else
st = mid;
}
return st;
}