/*Orion Lawlor's Simple C++ Examples, olawlor@acm.org
Shows the dangers of using floating-point "log" math routine
to calculate base-2 integer logs.
*/
/*
The problem is that a log is an infinitely long irrational 
number, but to represent it in the machine, we only use a 
fixed number of digits.  This truncation leads to roundoff
errors, which can result in the wrong value.

Note that the same program written as the mathematically 
equivalent (but slightly slower)
	std::log((double)i)/std::log(2.0)
happens to give exactly the right answers, as the roundoff
is different!

The right way to calculate integer logs is via integer
operations, as in "good_log_2".
*/
#include <iostream>
#include <cmath>

int good_log_2(int i) {
	int m=0;
	while (i>1) {
		m++;
		i=i>>1;
	}
	return m;
}

double bad_log_2(int i) {
	double inv_log_2=1.0/std::log(2.0);
	return std::log((double)i)*inv_log_2;
}

int main()
{
	for (int i=1;i<=1024;i*=2) {
		double bad_d=bad_log_2(i);
		int bad=(int)(bad_d);
		int good=good_log_2(i);
		std::cout.precision(17);
		std::cout<<" log2("<<i<<") = "<<good<<"; or "<<bad<<" from "<<bad_d<<")\n";
	}
	return 0;
}
/*<@>
<@> ******** Program output: ********
<@>  log2(1) = 0; or 0 from 0)
<@>  log2(2) = 1; or 0 from 1)
<@>  log2(4) = 2; or 1 from 2)
<@>  log2(8) = 3; or 2 from 2.9999999999999996)
<@>  log2(16) = 4; or 3 from 4)
<@>  log2(32) = 5; or 4 from 5)
<@>  log2(64) = 6; or 5 from 5.9999999999999991)
<@>  log2(128) = 7; or 6 from 6.9999999999999991)
<@>  log2(256) = 8; or 7 from 8)
<@>  log2(512) = 9; or 8 from 9)
<@>  log2(1024) = 10; or 9 from 10)
<@> */