How to improve a function?

Question

I have a program that counts 2 to the power 26 and the root of result number.

Program's source code is contained in several files and I compiled it by makefile with -pg flag. I run it by gprof ./main and as a result I got:

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

I want to improve the most time consuming function but I have no idea how to do this. What can be done in this case?

Files:

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

Looks like a homework assignment, but I'll offer one idea to simplify addition - get rid of unnecessary while loops and maybe detect overflow.

Moving this to community 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

You give_me_power function is of O(n). You can optimize it to 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;
}