[ create a new paste ] login | about

Link: http://codepad.org/WQYbpVOI    [ raw code | output | fork ]

mohit_at_codepad - C++, pasted on Jun 1:
// 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;
}


Output:
1
Problems (if any) are printed above. Rest.... all is well


Create a new paste based on this one


Comments: