Determining if an integer is a perfect square in assembly (mips32)

Question

I know how to do it in c. Compute the square root, take the modulus 10 of the square root. if the modulus is 0 then it's a perfect square.

But how can I do it in assembly, since I can't do a square root in it. Is there an easier way?

You could always link against the C runtime library and call `sqrt`. — TypeIA, Mar 24 '14 at 13:50
I am attempting to learn assembly, so attempting some exercises. I am aware that we can link functions, but i would like to do it in assembly — Wobblester, Mar 24 '14 at 13:51
I'm not aware of any square number tests that don't require square roots (except brute force, i.e. checking all candidates roots one by one). If there is a way, the guys at math.stackexchange.net might know it. Or you can [implement your own `sqrt` function](http://stackoverflow.com/questions/3581528/how-is-the-square-root-function-implemented). The brute force solution would work for small input numbers, but does not scale well at all. If this is *just* an exercise in assembly, that probably doesn't matter; but implementing your own `sqrt` may not be the best "beginner's exercise." — TypeIA, Mar 24 '14 at 13:57
possible duplicate of [Finding square root of an integer on MIPS assembly](http://stackoverflow.com/questions/17868029/finding-square-root-of-an-integer-on-mips-assembly) — Engineer2021, Mar 24 '14 at 14:06
If you want to do it all in integers, try this. In a loop compute 1 squared, 2 squared, 4 squared, 8 squared, 16 squared, 32 squared, up to 65536 squared. If any of them are your number, you're done; it's a perfect square. If one of them is bigger than your number. Say, 16 squared is bigger, then it can only be 9, 10, 11, 12, 13, 14 or 15 squared; binary search that list. You will likely run into some tricky cases around the top end, ie, if your number is close to 65536 squared, which does not actually fit into a 32 bit integer, so be careful there. — Eric Lippert, Mar 24 '14 at 15:19
First find some algorithimic solution. Check this answer first http://stackoverflow.com/questions/295579/fastest-way-to-determine-if-an-integers-square-root-is-an-integer or this http://stackoverflow.com/questions/2489435/how-could-i-check-if-a-number-is-a-perfect-square there are some routines on various languages. — Vovanium, Mar 24 '14 at 16:23

score 3 · Answer 1 · edited May 23 '17 at 12:20

3

Have you had a look at Newton's Method?

http://en.wikipedia.org/wiki/Newton's_method

And floating point registers in mips

http://en.wikipedia.org/wiki/MIPS_architecture#Floating_point

And another similar thread

Finding square root of an integer on MIPS assembly

Have you tried to do any coding yourself? And what is your assembly level?

Thanks.

edited May 23 '17 at 12:20

Community

1
1

answered Mar 24 '14 at 14:08

MrSykkox

528
4
14

Seva Alekseyev · Answer 2 · 2014-03-24T15:06:31.917

0

Yes you can do square root in assembly. Square root of floating point numbers, that is. If your MIPS CPU supports floating point instructions (most of them do these days), it has the SQRT.D command (square root of double).

If you need help with the rest of the algorithm, e. g. copying general purpose registers to floating point ones, converting integer to float and back, FP arithmetic, please say so.

edited Mar 24 '14 at 15:06

answered Mar 24 '14 at 14:41

Seva Alekseyev

59,826
25
160
281

barak manos · Answer 3 · 2014-03-24T16:06:41.233

You can implement it in C or C++, and then view the disassembly.

In order to do it efficiently, I suggest using an iterative binary search:

int isSquare(unsigned int num)
{
    unsigned int lo = 0;
    unsigned int hi = num;
    do
    {
        unsigned int mid = (hi+lo)/2;
        unsigned int square0 = mid*mid;
        unsigned int square1 = (mid+1)*(mid+1);
        if (num == square0 || num == square1)
            return 1;
        if (num < square0)
            hi = mid;
        else // if (num > square1)
            lo = mid;
    }
    while (lo+1 < hi);
    return 0;
}

Please note that any input to this function cannot be larger than 2^(num_of_bits_per_int/2+1)-3.

@Paul R: thank you for endorsing my attention to that; disassembly example removed. — barak manos, Mar 24 '14 at 16:08

Determining if an integer is a perfect square in assembly (mips32)

3 Answers3