#include <time.h>
#include <math.h>
#include <stdint.h>
#include <stdio.h>

/* Link me with  -lrt  for clock_gettime(). */

uint32_t Log2_loop (uint32_t n)
{
  uint32_t p = 0;
  n >>= 1;
  while (n) {
      p++;
      n >>= 1;
  }
  return p;
}

uint32_t Log2_direct (uint32_t n)
{
	static const double oneoverlog2 = 1.0/M_LN2;
	return (int)(log(n) * oneoverlog2);
}

uint32_t Log2_direct_float (uint32_t n)
{
	static const float oneoverlog2f = 1.0f/M_LN2;
	return (int)(logf(n) * oneoverlog2f);
}

double timediff(const struct timespec *a, const struct timespec *b)
{
	return a->tv_sec - b->tv_sec + .000000001 * (a->tv_nsec - b->tv_nsec);
}

double dotiming(uint32_t (*log2)(uint32_t n), int size, int* sum)
{
	struct timespec starttime, stoptime;
	int count = 10000000;
	int maxnum = 1 << size;
	int n = 0;
	clock_gettime(CLOCK_REALTIME, &starttime);
	while (1) {
		if (n > maxnum) n = 0;
		if (--count == 0) break;
		*sum += log2(n);
		++n;
	}
	clock_gettime(CLOCK_REALTIME, &stoptime);
	return timediff(&stoptime, &starttime);
}

int main()
{
	printf("size\tloop\t\tdirect\t\tdirect-float\n");

	int sum = 0;
	int size;
	for (size=0; size < 31; ++size) {
		printf("2^%d\t", size);
		printf("%f\t", dotiming(Log2_loop,         size, &sum));
		printf("%f\t", dotiming(Log2_direct,       size, &sum));
		printf("%f\n", dotiming(Log2_direct_float, size, &sum));
	}

	// Prevents the whole calculation from being optimized away
	printf("(sum was %d)\n", sum);

	return 0;
}

/* The integer-math loop is much faster than the math library log()
 * routine.  Output on an Intel "Core" in GNU:

size    loop            direct          direct-float
2^0     0.087742        2.601452        2.628589
2^1     0.084426        2.083092        2.037757
2^2     0.071396        1.701658        1.664958
2^3     0.094062        1.432350        1.387824
2^4     0.107877        1.273175        1.219492
2^5     0.109989        1.186929        1.135338
2^6     0.122546        1.143462        1.088042
2^7     0.130402        1.079676        1.030605
2^8     0.136646        1.067631        1.013757
2^9     0.142111        1.076999        1.011438
2^10    0.196679        1.089228        1.015410
2^11    0.210093        1.097610        1.020255
2^12    0.208401        1.103705        1.025885
2^13    0.203851        1.107369        1.030155
2^14    0.218241        1.110457        1.035080
2^15    0.235556        1.111458        1.037531
2^16    0.233996        1.110822        1.041092
2^17    0.235714        1.110340        1.042268
2^18    0.260464        1.111031        1.042038
2^19    0.267011        1.109349        1.041757
2^20    0.270359        1.108965        1.042859
2^21    0.278299        1.106861        1.042751
2^22    0.286983        1.106733        1.044010
2^23    0.295618        1.107200        1.041387
2^24    0.303384        1.106600        1.041971
2^25    0.303956        1.106322        1.042048
2^26    0.303497        1.105944        1.043350
2^27    0.303684        1.106554        1.041862
2^28    0.303167        1.106842        1.043231
2^29    0.303862        1.107211        1.044259
2^30    0.303785        1.105946        1.043321
(sum was -1470322644)


*/