// Find square root of a function using binary search.
// int b_sqrt(int num);
// returns -1 if num is out of range (0 to 1,000,000)
// Returns integer part of square root otherwise.
#include <iostream>
#include <cmath>
using namespace std;
/// b_sqrt
/// Calculation square root of an integer using binary search
/// @param[in] num Argument
/// @ret Integer containing the squareroot of num
int b_sqrt(int num) {
int ans = -1;
if(0 <= num && num <= 1000 * 1000) {
ans = 0;
int bitfield = 1 << 10; // a rought estimastion of sqrt(1 million)
// Alternatively you can initialize bitfield_sq with 1 << 20
// and right shift it by 2 bits everytime to avoid multiplication
while(bitfield * bitfield > num) bitfield >>= 1;
ans = bitfield;
while( 0 != (bitfield >>= 1) ) {
ans |= bitfield;
if(ans * ans > num) ans ^= bitfield;
}
}
return ans;
}
int main() {
const int sqrtm1 = b_sqrt(-1);
if(sqrtm1 != -1) cout << "Failed at -1, expected -1, actual " << sqrtm1 << endl;
for(int i = 0; i <= 1000000; ++i) {
const int expected = static_cast<int>( sqrt(i) );
const int actual = b_sqrt(i);
if(expected != actual) cout << "Failed at " << i
<< ", expected " << expected
<< ", actual " << actual << endl;
}
const int sqrtmillion1 = b_sqrt(1000 * 1000 + 1);
if(sqrtmillion1 != -1) cout << "Failed at 1mn+1, expected -1, actual " << sqrtmillion1 << endl;
cout << "Problems (if any) are printed above. Rest.... all is well" << endl;
return 0;
}