如何改进一个功能？

Question

我有一个程序可以计算 2 的 26 次方和结果数的根。

程序的源代码包含在几个文件中，我通过带有 -pg 标志的 makefile 编译了它。我运行通过 gprof ./main 结果我得到了：

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 51.95      1.73     1.73       52     0.03     0.03  very_smart_add
 32.73      2.82     1.09 67108863     0.00     0.00  give_me_sum
 11.71      3.21     0.39       13     0.03     0.16  the_middle_of
  3.60      3.33     0.12       26     0.00     0.05  give_me_product
  0.00      3.33     0.00       13     0.00     0.13  the_middle_of2
  0.00      3.33     0.00        1     0.00     1.21  give_me_power
  0.00      3.33     0.00        1     0.00     2.12  square_root

我想改进最耗时的功能，但我不知道该怎么做。在这种情况下可以做什么？

文件：

part1.c:

long long give_me_product(long long a, long long b);

long long give_me_power(long long a, long long b)
{
    long long ret = 1;
    while (b--)
    {
        ret = give_me_product(a, ret);
    }
    return ret;
}

part2.c:

long long give_me_sum(long long a, long long b);

long long give_me_product(long long a, long long b)
{
    long long ret = 0;
    while (b--)
    {
        ret = give_me_sum(a, ret);
    }
    return ret;
}

part3.c:

long long give_me_sum(long long a, long long b)
{
    long long ret = 0;
    while (a--)
    {
        ret++;
    }
    return ret + b;
    while (b--)
    {
        ret++;
    }
    return ret;
}

sqrt.c:

#define EPS 0.0000000001
#define STEP 1.0

/* This function adds two numbers. */
double very_smart_add(double a, double b)
{
    while (b >= STEP)
    {
        a += STEP;
        b -= STEP;
    }
    a += b;
    return a;
}

double the_middle_of2(double a, double b)
{
    double l = a, r = b;
    double check, m;
    while (1)
    {
        m = very_smart_add(l, r)/2;
        check = very_smart_add(m, m);
        if (check > very_smart_add(a, b) + EPS)
            r = m;
        else if (check < very_smart_add(a, b) - EPS)
            l = m;
        else
            return m;
    }
}
double the_middle_of(double a, double b)
{
    double r = 0;
    double s = a + b;
    while (r + r < s)
    {
        r += 1.0;
    }
    return the_middle_of2(r - 1.0, s - (r - 1.0));
}

double square_root(double x)
{
    double l = 0, r = x;
    double check, m;
    while (1)
    {
        m = the_middle_of(l, r);
        check = m * m;
        if (check > x + EPS)
            r = m;
        else if (check < x - EPS)
            l = m;
        else
            return m;
    }
}

Answer 1

看起来像是一项家庭作业，但我将提供一个简化加法的想法 - 摆脱不必要的 while 循环并可能检测溢出。

将此移动到社区 wiki。

long long give_me_sum(long long a, long long b) {
  #if NEED_TO_PREVENT_UNDEFINED_BEHAVIOR
  if (a >= 0) {
    if (b > LLONG_MAX - a) return LLONG_MAX;
  } else {
    if (b < LLONG_MIN - a) return LLONG_MIN;
  }
  #endif
  return a + b;
}

Answer 2

您 give_me_power 函数的复杂度为 O(n)。您可以将其优化为 O(log n).

long long give_me_power(long long a, long long b)
{
    long long ret = 1;
    while (b)
    {
        if ( b & 1) {
            ret *= a;
            b--;
        } else {
            a *= a;
            b >>= 1;
        }
    }
    return ret;
}

如何改进一个功能？

How to improve a function?

c

optimization

gprof