Optimised power function for integer values

pow.c

/*
 * pow.c
 *
 * Optimised power function for integer values
 */

#include <assert.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <time.h>

/* Number of samples */
#define SAMPLES_CNT 1000

void run_test(uint64_t (*func)(uint64_t, uint64_t),
              uint64_t base, uint64_t exp);

double get_time_elapsed(struct timeval start, struct timeval end);

uint64_t bad_pow(uint64_t base, uint64_t exp);

uint64_t good_pow(uint64_t base, uint64_t exp);

/*
 * Main function
 *
 * Admits <prog> <base> <exp> as arguments
 * base > 1
 * exp > 1
 */
int main(int argc, char ** argv)
{

        uint64_t base, exp;

        assert(argc == 3);

        base = strtoul(argv[1], NULL, 0);
        assert(base > 1);

        exp = strtoul(argv[2], NULL, 0);
        assert(exp > 1);

        puts("Bad power function:");
        run_test(bad_pow, base, exp);

        puts("\nBetter power function:");
        run_test(good_pow, base, exp);

        return 0;
}

/*
 * Test runner
 */
void run_test(uint64_t (*func)(uint64_t, uint64_t),
              uint64_t base, uint64_t exp)
{
        uint64_t result;
        struct timeval start, end;
        double time_taken;

        gettimeofday(&start, NULL);
        for (int i = 0; i < SAMPLES_CNT; i++)
                result = (*func)(base, exp);
        gettimeofday(&end, NULL);
        time_taken = get_time_elapsed(start, end);

        printf("%lu^%lu = %lu\n", base, exp, result);
        printf("Done in %g seconds.\n", time_taken);
}

/*
 * Time interval measurement
 *
 * The clock has a precision of 1 microsecond. This precision is increased,
 * the more samples are collected. E.g. N=1000 -> precision of 1 nanosecond.
 */
double get_time_elapsed(struct timeval start, struct timeval end)
{
        double time_elapsed;
        time_elapsed = (end.tv_sec - start.tv_sec) * 1e6;
        time_elapsed = (time_elapsed + (end.tv_usec - start.tv_usec)) * 1e-6;
        return time_elapsed / SAMPLES_CNT;
}

/*
 * Bad power algorithm
 * Theta(n)
 */
uint64_t bad_pow(uint64_t base, uint64_t exp)
{
        uint64_t result = 1;
        for (uint64_t i = 0; i < exp; ++i)
                result *= base;
        return result;
}

/*
 * Good power algorithm
 * Theta(log2(n))
 *
 * Let N = floor(log2(x))
 * Let zi be the ith bit of exp
 * x = prod(base^(zi*2^i), i=0..N)
 *
 * In each iteration, exp is shifted to extract the zi bit and the base
 * is squared to simulate the base^2^i part of the product operator.
 */
uint64_t good_pow(uint64_t base, uint64_t exp)
{
        uint64_t result = 1;
        while (exp) {
                if (exp & 1) result *= base;
                base *= base;
                exp >>= 1;
        }
        return result;
}