Subj : Re: sqrt algo
To   : comp.programming
From : pete
Date : Wed Jul 13 2005 09:19 pm

himanshu bafna wrote:
> 
> Hi
> 
> Can anyone shed light on an Algorithm for
> finding out the square root of
> a number? to make it simple lets only consider integers.

/* BEGIN isqrt.c */

#include <stdio.h>

#define N_MAX (16 + 1)

unsigned isqrt(unsigned, unsigned *);
unsigned irt(unsigned);

int main(void)
{
    unsigned n, root;

    for (n = 0; N_MAX > n; ++n) {
        root = isqrt(n, NULL);
        printf("The square root of %u is %u.\n", n, root);
    }
    putchar('\n');
    for (n = N_MAX - 2; N_MAX > n; ++n) {
        unsigned rem;

        root = isqrt(n, &rem);
        if (rem != 0) {
            printf("%u is not a perfect square.\n", n);
        } else {
            printf("%u is a perfect square.\n", n);
            printf("The square root of %u is %u.\n", n, root);
        }
    }
    return 0;
}

unsigned isqrt(unsigned n, unsigned *remainder)
{
    unsigned power_of_4, root, sum;

    power_of_4 = ((unsigned)-1 >> 2 - (unsigned)-1 % 3) + 1;
    root = 0;
    do {
        sum = root + power_of_4;
        if (n >= sum) {
            n -= sum;
            root = sum + power_of_4;
        }
        root >>= 1;
        power_of_4 >>= 2;
    } while (power_of_4 != 0);
    if (remainder != NULL) {
        *remainder = n;
    }
    return root;
}

unsigned irt(unsigned n)
{  
    unsigned a, b;

    a = n;
    for (b = (1 == n) + n >> 1; n > b; b = a / n + n >> 1) {
        n = b;  
    }
    return n;
}

/* END isqrt.c */


-- 
pete

.