Recursively calculate integer sqrts with C

Question

I adapted some python code I found here to calculate the sqrt of a number if it exists as an integer using bitwise operations. here is my code.

int ft_sqrt(int nb){
    int smallcandidate;
    int largecandidate;

    if (nb < 0){
        return (0);
    }else if (nb < 2){
        return (nb);
    }else{
        smallcandidate = ft_sqrt(nb >> 2) << 1;
        largecandidate = smallcandidate + 1;

        if (largecandidate * largecandidate > nb){

            return (smallcandidate);
        }
        else{
            return (largecandidate);
        }
    }
}

This works for every number i've tested (within the bounds of what an integer can hold), except for 3. Why is this? and how can i fix it?

I don't see the problem. Your function returns `1` when `3` is passed in. — selbie, May 20 '18 at 04:23
I want it to return 0 when 3 is passed in, but nvm i fixed that, going to add answer now. — Gabe Spound, May 20 '18 at 04:28
The square root of 3 is 1.73. Why would you want your function to return 0 instead? — selbie, May 20 '18 at 04:28
Why do you want the square root of 3 to be reported as 0 rather than 1? It is a non-obvious definition of the square root. — Jonathan Leffler, May 20 '18 at 04:29
Because I want '0' to mean that either the square root isn't an integer, or the input was invalid. — Gabe Spound, May 20 '18 at 04:30
Possible duplicate of [Fastest way to determine if an integer's square root is an integer](https://stackoverflow.com/questions/295579/fastest-way-to-determine-if-an-integers-square-root-is-an-integer) — selbie, May 20 '18 at 04:47
@GabeSpound The algorithm you copied from Wikipedia isn't restricted to numbers that are perfect squares. If the square root isn't an integer, it returns the integer part of the square root. — Barmar, May 20 '18 at 05:33

Luis Colorado · Answer 1 · 2019-05-23T16:50:03.023

Sorry, but you had better to use an iterative function, as you see your recursion is final recursion, that can be collapsed to a while loop. Your algorithm is:

#include <stdio.h>

unsigned isqrt(unsigned x)
{
    unsigned quot = 1, mean = x; /* isqrt must be between these two */
    /* we begin with extreme numbers and for each pair of (quot,mean),
     * the first, below the square root, and the other above, we get 
     * mean value of the two (lesser than previous) and the
     * quotient (above the prev. value, but still less than the 
     * square root, so closer to it) to get a better approach */
    while (quot < mean) {
        mean = (mean + quot) >> 1;
        quot = x / mean;
    }
    /* quot is always <= mean so finally it should be the same,
     * we can return quot or mean, indistinctly. */
    return mean;
}

int main() /* main test function, eliminate to use the above. */
{
    unsigned n;
    while (scanf("%u", &n) == 1) {
        printf("isqrt(%u) ==> %u\n", n, isqrt(n));
    }
}

EDIT

This algorithm is based on the fact that the geometric mean is always closer to 1 than the arithmetic mean. So we take two approximations (the source number and 1, as their geometric mean is the square root) then we calculate their arithmetic mean (so the value obtained is between both, and so, closer to the geometric mean) then we divide the original number by the arithmetic mean so both aproximations multiply to the original data (and their geometric mean is, again, the square root). As, in each loop the arithmetic mean is closer to the geometric mean, so must be the quotient (and so the quotient to the geometric mean), leading to two numbers that are closer to the square root. We continue the algorithm until both numbers are equal (a / sqrt(a) = sqrt(a), and (sqrt(a) + sqrt(a))/2 = sqrt(a)) or, due to rounding errors, they cross over. ---this happens with integers---

Recursively calculate integer sqrts with C

1 Answers1

EDIT