备考(C)具有自写函数的-> n-根(无数学或其他)

Question

目标很简单：

找到X1，X2，.的几何中间。Xn (在我的例子中，n= 3)

但是我必须编写自己的函数，不能使用pow()、exp()、log2()等等。

所以，在我开始编码之前，我试着先用纸张计算它。我使用125作为(a *b* c)的结果，因为我知道125的第三个词根是5。

我想使用"125 e(1/n)“，但我真的很难计算这个表达式，因为我根本不知道如何.但是谷歌并没有真正的帮助..。

这只是一项考试的学习任务.

Answer 1

你可以用牛顿法计算x的第n根。

牛顿法是

Y=y- f(y) / f'(y)

使用

f(y) = y^n -x

这将给出以下迭代：

Y=(n-1)*y/n+x/n* y^(1-n)

对于初始y大于x的序列，该序列是收敛的(参见第n次根迭代 )

在普通C中，这意味着：

#include <assert.h>
#include <stdio.h>

double nthpower(int n, double x)
{
  if (n < 0)
    return nthpower(-n, 1 / x);

  double y = 1;

  for (int i = 0; i < n; i++)
  {
    y = y * x;
  }

  return y;
}

int close_to_zero(double x)
{
  const double eps = 1e-10;

  return (-eps < x) && (x < eps);
}

double nthroot(int n, double x)
{
  assert(x >= 0);
  assert(n >= 0);

  switch (n)
  {
    case 0:
      return 1;

    case 1:
      return x;

    default:
      double yp, y = x;

      do
      {
        yp = y;
        y = (n - 1) * y / n + x / n * nthpower(1 - n, y);
      } while (!close_to_zero(yp - y));

      return y;
  }
}

double geometric_mean(double* x, int n)
{
  double p = 1;

  for (int i = 0; i < n; i++)
  {
    p *= x[i];
  }

  return nthroot(n, p);
}

int main(void)
{
  double x[6] = {2, 3, 4, 5, 6, 7};

  printf("GM %f\n", geometric_mean(x, 0));
  printf("GM %f\n", geometric_mean(x, 1));
  printf("GM %f\n", geometric_mean(x, 6));

  return 0;
}

其中的指纹：

通用1.000000通用2.000000通用4.140681

还有改进的余地，例如，通过计算x.x，然后x^2.x^2，然后x^4.x^4，可以更有效地计算n次方。但我认为，主要思想(使用牛顿法)是正确的。

Answer 2

找一个数的第n根没有通用的算法.但是，由于我们手头有一台计算机，我们可以使用数值逼近。

我们有两种求单调函数根的通用方法。

• 二分法:如果你有一个数值以下和超过一个，取平均值，并继续进行。这是一种非常稳健的方法，但收敛速度慢。
• 牛顿:你用导数公式从最初的猜测中找到一个更好的值。这是一个非常快，只要你开始足够接近根，但如果你开始一个糟糕的猜测可能很差。顺便说一下，我们都知道x -> x^n在x -> n* x^(n -1)中的导数.

因此，经验法则是从二分法开始，找到一个可接受的猜测，然后与牛顿一起找到一个非常精确的近似。

当我们得到一些值时，我们想取几何平均值，我们知道结果大于最小值，小于最大值，所以我们需要初始化二分法。

一项可能的守则可以是：

#include <stdio.h>
#include <stdlib.h>
#include <float.h>

// a trivial implementation for x -> x^n
double ipow(double x, int n) {
    double val = 1;
    int i;
    for (i = 0; i < n; i++) val *= x;
    return val;
}

int main() {
    //double *arr;
    int i, n;
    printf("Enter the number of values: ");
    for (;;) {
        if (1 == scanf("%d", &n) && n > 1) break;
        printf("Invalid input, try again\n");
        int c;
        while ((c = fgetc(stdin)) != EOF && c != '\n');
        if (c == EOF) return 1;
    }
    double min = DBL_MAX, max = -DBL_MAX, a = 1;
    //arr = malloc(n * sizeof(*arr));
    printf("Enter %d values: ", n);
    for (i = 0; i < n; i++) {
        double val;
        for (;;) {
            if (1 == scanf("%lg", &val) && (val > 0)) break;
            printf("Invalid input, try again\n");
            int c;
            while ((c = fgetc(stdin)) != EOF && c != '\n');
            if (c == EOF) return 1;
        }
        a *= val;
        if (min > val) min = val;
        if (max < val) max = val;
    }
    // we want x, ipow(x, n) "close" to a, we know min <= x <= max
    // first a dichotomy
    double x, eps = 1 / 10.;
    int nd = 0, nn = 0; // will trace the number of dich and Newton iterations
    for (;;) {
        ++nd;
        x = (min + max) / 2;
        if (max - min < x * eps) {
            break;
        }
        if (ipow(x, n) < a) min = x;
        else max = x;
    }
    eps = 1e-10;
    // let's go with Newton
    for (;;) {
        ++nn;
        double x1 = x;
        x = x1 + (a - ipow(x1, n)) / n / ipow(x1, n - 1);
        if (x1 - x > -eps * x && x1 - x < eps * x) break;
    }
    printf("sqrt%d(%g) = %g (%d dichotomy, %d Newton)\n", n, a, x, nd, nn);
    return 0;
}

它可能不是最有效的方法，但它是稳健的，因为它能够计算1e-300和1e300的几何平均数，而1e300 * 1e300溢出到inf。(但幸运的是，inf比任何浮点值都大，二分法部分工作得很好)

Answer 3

正如"abelenky“在他(已删除的)答案中所写，如果您想要计算严格递增函数的反函数，并且您知道结果是正的，您也可以使用二进制搜索：

搜索一个数字的n-th根y是函数y=f(x, n)的反函数；对于x>0，这个函数是严格增加的。

因为编写C代码是为了你的家庭作业练习，所以我不会在这里展示工作C代码，而只是解释一下这个原则：

在执行二进制搜索之前，必须执行两次检查：

• 如果数字为零，则解(根)也为零。
• 如果数字为负数，如果-root(-y, n)是奇数，则可以计算n；如果n是偶数，则没有解。 (-root(-y, n)的意思是:计算y绝对值的n-th根，并更改结果的符号。)

现在搜索起始号码g

double g = 1;
while(f(g) > y) { g /= 2; }
while(f(g) < y) { g *= 2; }

对于n-th根，f(x)是pow(x, n)，如果已知n是正整数，则可以轻松地用自写函数(使用for循环)替换n。

然后执行二进制搜索：

double x;
int i;
for(i=0; i<60; i++)
{
    if(f(x+g) <= y) { x+=g; }
    g /= 2;
}

由于double变量的精度，增加循环运行次数不会改变结果。如果使用更精确的数据类型(如long double)，则需要更多的循环运行才能获得最佳结果。