Compute a square root (with restrictions)

[brewbuck]

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.

[brewbuck]

Originally Posted by dwks

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.

[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*

[abachler]

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

[Sang-drax]

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.

[abachler]

a solution that meets all the requirements of the rules, but perhaps not the spirit of the contest -

double sqrtfunc(double Input){
 
     __asm    FLD  Input
     __asm    FSQRT
     __asm    FSTP Input
 
     return Input;
     }

hah, no division one iteration beat that

[AverageSoftware]

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

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:

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.

[Sang-drax]

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.

[Daved]

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

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

[dwks]

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

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

[dwks]

This doesn't work?

static_cast<int>(r * .5)

I'm just guessing, I don't know much about that sort of thing.

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

[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".

[Daved]

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