Created
August 22, 2019 03:04
-
-
Save guidanoli/e8ebb481262daa490ac45d26dd365c2c to your computer and use it in GitHub Desktop.
Optimised power function for integer values
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* 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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment