/* * Copyright (C) 2003 Leonid A. Broukhis * This copyright notice and accompanying text * must be preserved in all copies of the template definitions below. */ #include <iostream> #include <cstdio> // A straightforward Newton approximation; terminates when // the next probe is equal either to the current probe or the quotient. template<unsigned n, unsigned a, bool> struct newton { static const unsigned q = n/a; static const unsigned a2 = (a+q)/2; static const bool good = a2==a || a2==q; static const unsigned value = newton<n,a2,good>::value; }; // The terminating clause template<unsigned n, unsigned a> struct newton<n, a, true> { static const unsigned value = a; }; // First approximation is the 4th power root of max. unsigned value, // so it converges in no more than 9 iterations template<unsigned n> struct Sqrt : newton<n, 256, false> { }; int main() { std::cout << 0 << ' ' << Sqrt<0>::value << std::endl; std::cout << 1 << ' ' << Sqrt<1>::value << std::endl; std::cout << 2 << ' ' << Sqrt<2>::value << std::endl; std::cout << 3 << ' ' << Sqrt<3>::value << std::endl; std::cout << 4 << ' ' << Sqrt<4>::value << std::endl; std::cout << 5 << ' ' << Sqrt<5>::value << std::endl; std::cout << 6 << ' ' << Sqrt<6>::value << std::endl; std::cout << 7 << ' ' << Sqrt<7>::value << std::endl; std::cout << 8 << ' ' << Sqrt<8>().value << std::endl; std::cout << 9 << ' ' << Sqrt<9>::value << std::endl; std::cout << 10 << ' ' << Sqrt<10>::value << std::endl; std::cout << 11 << ' ' << Sqrt<11>::value << std::endl; std::cout << 12 << ' ' << Sqrt<12>::value << std::endl; std::cout << 13 << ' ' << Sqrt<13>::value << std::endl; std::cout << 14 << ' ' << Sqrt<14>::value << std::endl; std::cout << 15 << ' ' << Sqrt<15>::value << std::endl; std::cout << 16 << ' ' << Sqrt<16>::value << std::endl; std::cout << 17 << ' ' << Sqrt<17>::value << std::endl; std::cout << 18 << ' ' << Sqrt<18>::value << std::endl; std::cout << 19 << ' ' << Sqrt<19>::value << std::endl; std::cout << 20 << ' ' << Sqrt<20>::value << std::endl; std::cout << 21 << ' ' << Sqrt<21>::value << std::endl; std::cout << 22 << ' ' << Sqrt<22>::value << std::endl; std::cout << 23 << ' ' << Sqrt<23>::value << std::endl; std::cout << 24 << ' ' << Sqrt<24>::value << std::endl; std::cout << 25 << ' ' << Sqrt<25>::value << std::endl; std::cout << 26 << ' ' << Sqrt<26>::value << std::endl; std::cout << 27 << ' ' << Sqrt<27>::value << std::endl; std::cout << 28 << ' ' << Sqrt<28>::value << std::endl; std::cout << 29 << ' ' << Sqrt<29>::value << std::endl; std::cout << 30 << ' ' << Sqrt<30>::value << std::endl; std::cout << 31 << ' ' << Sqrt<31>::value << std::endl; std::cout << 32 << ' ' << Sqrt<32>::value << std::endl; std::cout << 33 << ' ' << Sqrt<33>::value << std::endl; std::cout << 34 << ' ' << Sqrt<34>::value << std::endl; std::cout << 35 << ' ' << Sqrt<35>::value << std::endl; std::cout << 36 << ' ' << Sqrt<36>::value << std::endl; std::cout << 37 << ' ' << Sqrt<37>::value << std::endl; std::cout << 38 << ' ' << Sqrt<38>::value << std::endl; std::cout << 39 << ' ' << Sqrt<39>::value << std::endl; std::cout << -1 << ' ' << Sqrt<-1>::value << std::endl; }