I was just playing around, trying to compute a square root at compile time. I came up with the following: template < unsigned int N, unsigned int X = 1, unsigned int X2 = ( X + N / X ) / 2 > struct Sqrt { typedef typename Sqrt < N, X2 > :: ValueHolder ValueHolder; }; template < unsigned int N, unsigned int X > struct Sqrt < N, X, X > { struct ValueHolder { enum ValueStorage { Value = X }; }; }; This works for most values, but unfortunately some ( like 80 ) end up oscillating and X never becomes equal to X2. How could I go about correcting this? -Jason
Jason Hise wrote:
I was just playing around, trying to compute a square root at compile time. I came up with the following:
<code snip>
This works for most values, but unfortunately some ( like 80 ) end up oscillating and X never becomes equal to X2. How could I go about correcting this?
you can do something like this: template < unsigned int N, unsigned int X = 1, unsigned int X1 = 0, unsigned int X2 = ( X + N / X ) / 2 > struct Sqrt { enum { Value = Sqrt < N, X2, X > :: Value }; }; template < unsigned int N, unsigned int X, unsigned int X1 > struct Sqrt < N, X, X1, X1 > { enum { Value = X1 }; }; this code takes one more iteration to solve, but avoid the oscillation problem, I was not sure why you are using this ValueHolder struct so I took the liberty to remove it, but if you need it, you can bring it back without any problem.
-Jason Sérgio
Jason, I found an algorithm at http://www.pedrofreire.com/sqrt/ that claims to be quite fast. I haven't really looked into that. The algorithm needs to be modified to always round down (I'm assuming this is what you want, since that's what the code you posted does when it works.) Here is the runtime version: unsigned int UIntSqrt(unsigned int n) { unsigned int r; for(r = 1; n >= r; n -= r, r += 2); return (r - 1) / 2; } Putting this into compile-time code is as follows: template <unsigned int N, unsigned int R = 1, bool C = (N >= R)> struct Sqrt { static const unsigned int value = Sqrt<(N - R), (R + 2)>::value; }; template <unsigned int N, unsigned int R> struct Sqrt<N, R, false> { static const unsigned int value = (R - 1) / 2; }; I hope this helps, David "Jason Hise" <chaos@ezequal.com> wrote in message news:41F884F5.3030508@ezequal.com...
I was just playing around, trying to compute a square root at compile time. I came up with the following:
template < unsigned int N, unsigned int X = 1, unsigned int X2 = ( X + N / X ) / 2 > struct Sqrt { typedef typename Sqrt < N, X2 > :: ValueHolder ValueHolder; };
template < unsigned int N, unsigned int X > struct Sqrt < N, X, X > { struct ValueHolder { enum ValueStorage { Value = X }; }; };
This works for most values, but unfortunately some ( like 80 ) end up oscillating and X never becomes equal to X2. How could I go about correcting this?
-Jason
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Jason Hise wrote:
I was just playing around, trying to compute a square root at compile time. I came up with the following:
template < unsigned int N, unsigned int X = 1, unsigned int X2 = ( X + N / X ) / 2 > struct Sqrt { typedef typename Sqrt < N, X2 > :: ValueHolder ValueHolder; };
template < unsigned int N, unsigned int X > struct Sqrt < N, X, X > { struct ValueHolder { enum ValueStorage { Value = X }; }; };
This works for most values, but unfortunately some ( like 80 ) end up oscillating and X never becomes equal to X2. How could I go about correcting this?
// This is a somewhat boostified implementation // of your algorithm rotated by 180 degrees 8-) #include <boost/config.hpp> #include <boost/mpl/eval_if.hpp> #include <boost/mpl/identity.hpp> using namespace boost::mpl; template< unsigned int N> struct sqrt_result { BOOST_STATIC_CONSTANT(unsigned int, value = N); }; template< unsigned int N, unsigned int I > struct sqrt_impl { // Note: Bare ICEs ( '(I*I>N)', '(I+N/I)/2' ) are not very portable // [ ref. http://www.boost.org/more/int_const_guidelines.htm ]. // Using separate metafunctions (like sqrt_iteration_invariant, // sqrt_approximation_step) can solve the problem. typedef typename eval_if_c< (I*I>N) // approximation from above , sqrt_impl< N, (I+N/I)/2 > // step (original formula) , identity< sqrt_result<I> > >::type type; }; template< unsigned int N > struct sqrt : sqrt_impl<N,N>::type // start with I=N { // Note: Inheritance of static constants does not work properly for // all compilers. An explicit advice like: // // typedef typename sqrt_impl<N,N>::type base; // using base::value // // may solve this problem. typedef sqrt type; }; // Test #include <iostream> using namespace std; template< unsigned int N > void test() { cout << "sqrt(" << N << ") = " << ::sqrt< N >::value << std::endl; } int main() { test< 1>(); test< 2>(); test< 3>(); test< 4>(); test< 9>(); test< 16>(); test< 80>(); test< 81>(); test<144>(); return 0; } // Hey, that was fun. // // Regards, // // Tobias
Would the following work in all cases? My assumption is that if an oscillation is going to occur, the two numbers will always be off by exactly one. template < unsigned int N, unsigned int X = 1, unsigned int X2 = ( X + N / X ) / 2, unsigned int XP1 = X + 1 > struct Sqrt { enum ValueStorage { Value = typename Sqrt < N, X2 > :: Value }; }; template < unsigned int N, unsigned int X, unsigned int XP1 > struct Sqrt < N, X, X, XP1 > { enum ValueStorage { Value = X }; }; template < unsigned int N, unsigned int X, unsigned int XP1 > struct Sqrt < N, X, XP1, XP1 > { enum ValueStorage { Value = X }; }; -Jason
not exactlly, sometimes you get the 1 difference correctly so, you will introduce an error for such cases, and on some compillers (bcc) for some cases you get an error because it don´t know which version to instantiate Sqrt<N,X,XP1,XP1> or Sqrt<N,X,X,XP1> On Thu, 27 Jan 2005 22:55:49 -0500, Jason Hise <chaos@ezequal.com> wrote:
Would the following work in all cases? My assumption is that if an oscillation is going to occur, the two numbers will always be off by exactly one.
template < unsigned int N, unsigned int X = 1, unsigned int X2 = ( X + N / X ) / 2, unsigned int XP1 = X + 1 > struct Sqrt { enum ValueStorage { Value = typename Sqrt < N, X2 > :: Value }; };
template < unsigned int N, unsigned int X, unsigned int XP1 > struct Sqrt < N, X, X, XP1 > { enum ValueStorage { Value = X }; };
template < unsigned int N, unsigned int X, unsigned int XP1 > struct Sqrt < N, X, XP1, XP1 > { enum ValueStorage { Value = X }; };
-Jason
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Sérgio Vale e Pace wrote:
not exactlly, sometimes you get the 1 difference correctly so, you will introduce an error for such cases, and on some compillers (bcc) for some cases you get an error because it don´t know which version to instantiate Sqrt<N,X,XP1,XP1> or Sqrt<N,X,X,XP1>
XP1 should never be equal to X, so how could there be an ambiguity between the instantiations? Also, even when the difference of 1 is arrived at correctly, isn't it reasonable to assume that the lesser of the two numbers is the floor of the square root? -Jason
On Fri, 28 Jan 2005 10:47:21 -0500, Jason Hise <chaos@ezequal.com> wrote:
XP1 should never be equal to X, so how could there be an ambiguity between the instantiations?
sorry, I overlooked that
Also, even when the difference of 1 is arrived at correctly, isn't it reasonable to assume that the lesser of the two numbers is the floor of the square root?
try 4
Sérgio Vale e Pace wrote:
Also, even when the difference of 1 is arrived at correctly, isn't it reasonable to assume that the lesser of the two numbers is the floor of the square root?
try 4
ahh... alright, I see the problem. So how about I just default X to N instead of 1? -Jason
Jason Hise wrote:
Sérgio Vale e Pace wrote:
Also, even when the difference of 1 is arrived at correctly, isn't it reasonable to assume that the lesser of the two numbers is the floor of the square root?
try 4
ahh... alright, I see the problem. So how about I just default X to N instead of 1?
You can start with X=(N-1)/2. This small adjustment came to my mind just after I sent my previous post. It saves you one recursion step.
participants (4)
-
David M. Jones -
Jason Hise -
Sérgio Vale e Pace -
Tobias Schwinger