Results: Calculate square roots

OK, I' m unable to post the submissions in this thread, for known reasons, but I hope that every contestant can post their submission here for review.

Overview
Most people used the Newton-Rhapson method of solving equations. You can google for information about the algorithm, it's not advanced at all.
If you set up the equation
x^2 - a =0
It will have one root x = sqrt(a). The equation is solved with Newton-Rhapson's method.

Two different styles of was used to implement the iteration. One involved one general template and one specialization to stop the iteration (which I used in my best solution and also used by the winner). Another interessting implementation was invented by xErath, who used lots of template arguments to obtain the correct number of iterations.

Results
Everyone listed in the fist post of the original thread has submitted working solutions and are good coders -- this isn't trivial.
However, two persons submitted solutions that worked for every value of x >= 1 (I didn't get the time to do extensive tests) -- Okinrus and Fordy

Of these two, Fordy has the smallest submission. Good work! Fordy is the winner! :cool:

While his submission was short, every solution can be made shorter! Here are some of my thoughts:

• Used 'int' and 0/1 instead of 'bool' and true/false
• >>1 instead of /2 (getsrid of parentheses)
• Somewhat different #defines

But this doesn't matter as he was the best anyway!

I'm really sorry that I was unable to judge xErath's last submission, because it was really short as well!

Code:

---

#include<iostream>
#include<limits.h>
#include<math.h>

#define c(_n) ( (_n)/(2.0) + (x)/((_n)*(2.0)))

template<int x, int a = c(c(c(c(c(c(c(c(x)))))))), int b = c(c(c(c(c(c(c(c(a))))))))>
class SquareRoot{
public:
        static const int v = (int)c(c(c(b)));
};

int main(){
        char data[SquareRoot<1024>::v] = "";
       
        std::cout<<9      <<" "<<SquareRoot<9>::v      <<" "<<(int)sqrt((float)9)      <<'\n'; //Must output 3
        std::cout<<1000  <<" "<<SquareRoot<1000>::v  <<" "<<(int)sqrt((float)1000)  <<'\n'; //Must output 31
        std::cout<<82    <<" "<<SquareRoot<82>::v    <<" "<<(int)sqrt((float)82)    <<'\n'; //Must output 9
        std::cout<<INT_MAX<<" "<<SquareRoot<INT_MAX>::v<<" "<<(int)sqrt((float)INT_MAX)<<'\n'; //Must output 46340

        return 0;
}

---

Congrats Fordy... ;)
Bah!!! me wanted to win :(

Yay!

I'll post my code a bit later

I think this is the final version

PHP Code:

---

#define B ((b+a/b)/2) 
#define S SquareRoot
#define I static const int
#define L template<
#define J >struct
L int a,int b=a/2,bool c=false J S{I v=S<a,B,(a/B-B>=0)&&(a/B-B<=2)>::v;};L int a,int b J S<a,b,true>{I v=b;};L J S<1>{I v=1;}; 


---

A more sensible version before I (rather ham-handidly) tried to reduce the amount of code;

PHP Code:

---

#define B ((b+a/b)/2)
template<int a,int b=a/2,bool c=false>
struct SquareRoot{static const int v=SquareRoot<a,B,(a/B-B>=0)&&(a/B-B<=2)>::v;};
template<int a,int b>struct SquareRoot<a,b,true>{static const int v=b;};
template<>struct SquareRoot<1>{static const int v=1;}; 


---

I hate optimising for code size...optimising for speed - yeah, working the code to allow it to work with the maximum range of values - yeah. But there you go, you cant have it all youre own way ;)

Actually, I think xErath's would have beat mine...

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.

I did something similar to Newton-rhapson's method.

Code:

---

#include <iostream>
#include <climits>

// #define USE_UNSIGNED

#ifdef USE_UNSIGNED
typedef unsigned sqrt_type;
#else
typedef int sqrt_type;
#endif

template<sqrt_type val, sqrt_type bit, sqrt_type x>
struct SQ {
    static const sqrt_type nxt_bit = bit >> 1;
    static const sqrt_type try_val = val | nxt_bit;
    static const bool      valid  = try_val <= x/try_val;
    static const sqrt_type nxt_val = valid? try_val : val;

    static const sqrt_type v = SQ<nxt_val, nxt_bit, x>::v;
};



template<sqrt_type val, sqrt_type x>
struct SQ<val, 0, x> {
    static const sqrt_type v = val;
};


// find msb of the square root
template<sqrt_type bit, sqrt_type count>
struct FindMSB {
    static const sqrt_type bit_shr = bit >> 1;
 
    static const sqrt_type v = FindMSB<bit_shr, count + 1>::v;
};

template<sqrt_type count>
struct FindMSB<1, count> {
    static const sqrt_type v = 1 << (count/2);
};

template<sqrt_type x>
struct SquareRoot {
    static const sqrt_type msb = FindMSB<x, 0>::v;
    static const sqrt_type v  = SQ<msb, msb, x>::v;
};

template<int n>
void test_print()
{
    std::cout << "sqrt(" << n << ") = " << SquareRoot<n>::v << std::endl;
}



int main(void)
{ 
    test_print<1>();
    test_print<2>();
    test_print<3>();
    test_print<4>();
    test_print<5>();
    test_print<6>();
    test_print<7>();
    test_print<8>();
    test_print<9>();
    test_print<10>();
    test_print<11>();
    test_print<12>();
    test_print<13>();
    test_print<24>();
    test_print<25>();
    test_print<26>();

    test_print<10>();
    test_print<INT_MAX>();
    test_print<INT_MAX-1>();
    test_print<1000>();
    test_print<1024>();
    test_print<82>();
    test_print<4>();
    test_print<16>();
    test_print<17>();
    test_print<64>();

    return 0;
}

---

I used Newton-Raphson. A word about my entry. Now I'm not trying to make excuses and the other contestants beat me fair and square. The contest interested me so I took 15 minutes out of my lunch break at work to come up with what I ultimately submitted. I didn't even see where it would be judged on size. That is my fault for not paying closer attention. Also I knew not putting in an appropriate iteration amount for larger numbers would come back to haunt me. That having been said, this is what I submitted.

Code:

---

template<int x>
struct SquareRoot
{
  template<int xp, int i>
  struct NewtonsMethod
  {
    static const int val = NewtonsMethod<(xp + (x / xp)) / 2, i - 1>::val;
  };

  template<int xp>
  struct NewtonsMethod<xp, 0>
  {
    static const int val = (xp + (x / xp)) / 2;
  };
 
  static const int v  = NewtonsMethod<x, 32>::val;
};

---