# Thread: Compute a square root (with restrictions)

1. 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.

2. 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.

3. 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*

4. nah, if I couldnt use multiplication, Id use bit shifting

5. 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.

6. 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

7. Originally Posted by abachler
hah, no division one iteration beat that
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.

8. 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.

9. >> Wow, amazing, except that you are using division.

But there are no calls to the division operator at runtime, so its close.

10. >> 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.

That code's pretty amazing, though. I would never have thought of it.

11. >> 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.

12. This doesn't work?
Code:
`static_cast<int>(r * .5)`
I'm just guessing, I don't know much about that sort of thing.

13. 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).

14. Oh, I see. Well, the r/2 could be just r or r-1; it would just be less efficient and involve more "recursion".

15. True. And now that I look closer I see that it only does one division anyway, which is allowed in the rules.