If you implement it exactly as I did, and graph the number of iterations to achieve the accuracy I specified, that is what comes out. It is what it is.
Printable View
Perhaps an even greater challenge is no division or multiplication operators ;)
But then I suppose you'd define some macros that multiply by addition... *sigh*
nah, if I couldnt use multiplication, Id use bit shifting :)
a solution that meets all the requirements of the rules, but perhaps not the spirit of the contest -
hah, no division one iteration beat that :devil:Code:double sqrtfunc(double Input){
__asm FLD Input
__asm FSQRT
__asm FSTP Input
return Input;
}
Alas, since templates can't take doubles, I can't quite beat that, but...
This will find integer square roots at compile time, so I don't even need instructions.Code:template <int r, int x>
struct SqRootCalc
{
const static int value = x * x == r ? x : SqRootCalc<r, x - 1>::value;
};
template <int r>
struct SqRootCalc<r, 1>
{
const static int value = -1;
};
template <int r>
struct SqRoot
{
const static int value = SqRootCalc<r, r / 2>::value;
};
template <>
struct SqRoot<1>
{
const static int value = 1;
};
template <>
struct SqRoot<0>
{
const static int value = 0;
};
Usage:
If you pick an integer that doesn't have an integer square root (5 for example) you'll get -1.Code:cout << SqRoot<9>::value << endl;
>> Wow, amazing, except that you are using division.
But there are no calls to the division operator at runtime, so its close.
Besides, you can just change it to *0.5 and you'll be just fine. :rolleyes:Quote:
>> Wow, amazing, except that you are using division.
But there are no calls to the division operator at runtime, so its close.
That code's pretty amazing, though. I would never have thought of it. :)
>> Besides, you can just change it to *0.5 and you'll be just fine.
Except that you can't unfortunately. I believe everything must be integral.
This doesn't work?
I'm just guessing, I don't know much about that sort of thing.Code:static_cast<int>(r * .5)
It does, but that's different than AverageSoftware's template metaprogramming based solution. Yours is a run-time operation, but the templated stuff is compile time, which I believe must be integral (which is also why double can't be used instead of int).
Oh, I see. Well, the r/2 could be just r or r-1; it would just be less efficient and involve more "recursion".
True. And now that I look closer I see that it only does one division anyway, which is allowed in the rules.