I didn't use Newton-Rhapson, but this seems to work up to 3599999999 on my machine. I don't think it would have a chance at the smallest code part. I borrowed the Select struct from Alexandrescu's Modern C++ Design book. Not bad I guess for my first template metaprogramming experience.
Code:
template<bool f,class T,class U>
struct Select
{
typedef T Result;
};
template<class T,class U>
struct Select<false,T,U>
{
typedef U Result;
};
template<int x, unsigned long cur = 30000, unsigned long mn = 0, unsigned long mx = 60000>
struct SquareRoot
{
static const int v = Select<
(cur*cur > x), SquareRoot<x, (cur+mn)/2, mn, cur>, SquareRoot<x, (cur+mx)/2, cur, mx> >::Result::v;
};
template<int x, unsigned long y, unsigned long z>
struct SquareRoot<x, y, y, z>
{
static const int v = y;
};
template<int x, unsigned long y, unsigned long z>
struct SquareRoot<x, y, z, y>
{
static const int v = y;
};
template<int x, unsigned long y>
struct SquareRoot<x, y, y, y>
{
static const int v = y;
};
#include <iostream>
#include <climits>
int main()
{
std::cout << SquareRoot<1>::v << " - " << 1 << std::endl;
std::cout << SquareRoot<9>::v << " - " << 9 << std::endl;
std::cout << SquareRoot<82>::v << " - " << 82 << std::endl;
std::cout << SquareRoot<1000>::v << " - " << 1000 << std::endl;
std::cout << SquareRoot<123456789>::v << " - " << 123456789 << std::endl;
std::cout << SquareRoot<INT_MAX>::v << " - " << INT_MAX << std::endl;
std::cout << SquareRoot<3599999999>::v << " - " << 3599999999 << std::endl;
std::cout << SquareRoot<3600000000>::v << " - " << 3600000000 << std::endl;
}
Nice job Fordy, Okinrus and xErath.