find the nth root using binary search algorithm using C

Question

double x;
size_t n;
double precision;

double high = x < 1.0 ? 1.0 : x;
double min = 0.0;
double unknown = //idk??

double eps = 1e-6; 

double multiply(double number, int n) {
    double ans = 1.0;
    for (int i = 1; i <= n; i++) {
        ans = ans * number;
    }
    return ans;
}

while (precision < error) {
    while ((high - min) > eps) {
        double old = (min + high) / 2.0; 
        if(multiply(old, n) < unknown) {
            min = old; 
        } else {
            high = old; 
        }
    }
}

printf("%f", unknown); 

Trying to find the nth root using binary search algorithm. Can someone spot any logic errors that is keeping my code from working? Appreciated.

Answer 1

Here is your code cleaned up. The outer loop isn't needed. It doesn't work with negative numbers; I did not drill into why. I did not change your 'multiply' function so its not here

int main() {

    double x = 42; // number we want the root of
    size_t n = 2;  // the root we want

    // squeeze boundaries
    double high = x < 1.0 ? 1.0 : x;
    double min = 0.0;
    double eps = 1e-6; // how tight we want to squeeze the answer

    int iterations = 0; // count of iterations for interest
    double guess = 0;   // our current guess at the root

    while ((high - min) > eps) {
        iterations++;
        guess = (min + high) / 2.0;
        double guessPow = multiply(guess, n);
        if (guessPow < x) {
            min = guess;
        }
        else {
            high = guess;
        }
    }
    printf("%f %d %f", x, iterations, guess);

}

the core logic is still yours, so you should fix it so that cube root of -8 comes out as -2.

Answer 2

You can try this method :

#include <stdio.h>
#include <math.h>

double nth_root(double d, int n) {
    double x = d; // guess greater than result
    for (; x - .001 > (x -= (pow(x, n) - d) / (n * pow(x, n - 1))););
    return x;
}

// using Newton's method
int main(void) {
    for (int i = 1; i < 10; ++i) {
        double n = 625;
        double a = pow(n, 1. / i); // C answer
        double b = nth_root(n, i); // your answer
        printf("nth_root(%g, %d) = %-9g (found %-9g, diff is %.15f)\n", n, i, a, b, b - a);
    }
}

If you need a pow function :

double my_pow(double n, unsigned long long int power) {
    if (power) {
        double tmp = 1;
        for (; power > 1; n *= n)
            if (power & 1) {
                tmp *= n;
                power = (power - 1) >> 1;
            } else
                power >>= 1;
        n *= tmp;
    } else
        n = 1;
    return n;
}