# Compute a square root (with restrictions)

Show 80 post(s) from this thread on one page
Page 3 of 4 First 1234 Last
• 05-10-2007
brewbuck
Quote:

Originally Posted by Sang-drax
brewbuck, you must be doing something wrong. 125 iterations for newton's method?

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.
• 05-10-2007
brewbuck
Quote:

Originally Posted by dwks
Code:

`index *= 0.5;`
I think that counts as a sneaky way to avoid using division . . . :)

I disagree. What if it had read index *= 2? Is that a "sneaky way" to avoid dividing by 0.5? It's just a multiplication. The fact that the number is less than one doesn't really mean anything.
• 05-11-2007
zacs7
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*
• 05-11-2007
abachler
nah, if I couldnt use multiplication, Id use bit shifting :)
• 05-12-2007
Sang-drax
Quote:

Originally Posted by brewbuck
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.

Yeah, but a correctly implemented Newton's method should ceonverge much faster than that.
• 06-07-2007
abachler
a solution that meets all the requirements of the rules, but perhaps not the spirit of the contest -

Code:

```double sqrtfunc(double Input){       __asm    FLD  Input     __asm    FSQRT     __asm    FSTP Input       return Input;     }```
hah, no division one iteration beat that :devil:
• 06-07-2007
AverageSoftware
Quote:

Originally Posted by abachler
hah, no division one iteration beat that :devil:

Alas, since templates can't take doubles, I can't quite beat that, but...

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; };```
This will find integer square roots at compile time, so I don't even need instructions.

Usage:
Code:

`cout << SqRoot<9>::value << endl;`
If you pick an integer that doesn't have an integer square root (5 for example) you'll get -1.
• 06-07-2007
Sang-drax
Quote:

Originally Posted by AverageSoftware
This will find integer square roots at compile time, so I don't even need instructions.

Wow, amazing, except that you are using division.
• 06-07-2007
Daved
>> Wow, amazing, except that you are using division.

But there are no calls to the division operator at runtime, so its close.
• 06-07-2007
dwks
Quote:

>> 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:

That code's pretty amazing, though. I would never have thought of it. :)
• 06-07-2007
Daved
>> 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.
• 06-07-2007
dwks
This doesn't work?
Code:

`static_cast<int>(r * .5)`
I'm just guessing, I don't know much about that sort of thing.
• 06-07-2007
Daved
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).
• 06-07-2007
dwks
Oh, I see. Well, the r/2 could be just r or r-1; it would just be less efficient and involve more "recursion".
• 06-07-2007
Daved
True. And now that I look closer I see that it only does one division anyway, which is allowed in the rules.
Show 80 post(s) from this thread on one page
Page 3 of 4 First 1234 Last