Results: Calculate square roots

This is a discussion on Results: Calculate square roots within the Contests Board forums, part of the Community Boards category; OK, I' m unable to post the submissions in this thread, for known reasons, but I hope that every contestant ...

  1. #1
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072

    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!

    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!
    Last edited by Sang-drax; 09-29-2004 at 04:39 PM.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  2. #2
    #include<xErath.h> xErath's Avatar
    Join Date
    Jun 2004
    Posts
    722
    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
    Last edited by xErath; 09-29-2004 at 07:59 PM.

  3. #3
    &TH of undefined behavior Fordy's Avatar
    Join Date
    Aug 2001
    Posts
    5,786
    Yay!

    I'll post my code a bit later

  4. #4
    &TH of undefined behavior Fordy's Avatar
    Join Date
    Aug 2001
    Posts
    5,786
    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

  5. #5
    &TH of undefined behavior Fordy's Avatar
    Join Date
    Aug 2001
    Posts
    5,786
    Actually, I think xErath's would have beat mine...

  6. #6
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,088
    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.

  7. #7
    Registered User
    Join Date
    Aug 2003
    Posts
    470
    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;
    }

  8. #8
    Registered User
    Join Date
    Apr 2002
    Posts
    1,571
    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;
    };
    "...the results are undefined, and we all know what "undefined" means: it means it works during development, it works during testing, and it blows up in your most important customers' faces." --Scott Meyers

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. program to calculate the square root
    By saszew in forum C Programming
    Replies: 7
    Last Post: 10-28-2008, 12:53 PM
  2. Forced moves trouble!!
    By Zishaan in forum Game Programming
    Replies: 0
    Last Post: 03-27-2007, 06:57 PM
  3. Simplifing Square Roots
    By LiNeAr in forum C++ Programming
    Replies: 11
    Last Post: 10-01-2005, 08:56 PM
  4. for loops using square roots, square, Cube
    By lotf in forum C Programming
    Replies: 3
    Last Post: 03-21-2004, 03:29 AM
  5. Square roots / Powers etc.
    By Robert602 in forum C++ Programming
    Replies: 4
    Last Post: 09-30-2001, 03:26 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21