codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
// 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; }
Private
[
?
]
Run code
Submit