使用C的二进制搜索算法找到第n个根

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); 

尝试使用二进制搜索算法查找第n个根。有人能发现任何阻碍我的代码工作的逻辑错误吗？非常感谢。

Answer 1

这是您清理的代码。不需要外环。它不适用于负数；我没有探究原因。我没有改变你的"乘法"函数，所以它不在这里

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);
}

核心逻辑仍然是你的，所以你应该修复它，使-8的立方根变成-2。

Answer 2

您可以尝试以下方法：

#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);
}
}

如果你需要pow功能：

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;
}