Error in height calculation due to FP arithmetic

[thbde]

An array with size 124 and K=5 produces wrong results. index 0 will be mapped to index 124, which is out of bounds:

array_to_complete_tree(124, 5, 0) => 124

This happens due to the height calculation: https://github.com/llersch/linearized_search_trees/blob/5ce053cdafea6600645ec74cc7557ae793083b41/linearized_search_trees.h#L125 which is in this case: std::ceil(std::log(124+1) / std::log(5)) which should be 3 if we calculate it manually (5^3=125); but is 4, because IEEE 754 floating point arithmetic:

cout.precision(17);
cout << std::log(124+1) / std::log(5) << endl;
cout << std::ceil(std::log(124+1) / std::log(5)) << endl;
cout << std::log(124+1)<< endl;
cout << std::log(5) << endl;

3.0000000000000004
4
4.8283137373023015
1.6094379124341003

I do not have a good proposal to fix it. Two ideas:

• round before ceil?
• integer approximation for logarithmus? (e.g. multiply a=1 with 5 until a>index)

(Found by testing, there are most likely more of this FP arithmetic problems)

[llersch]

I started looking for more efficient implementations of pow, %, and log, since our use-cases are only for integers and VTune was showing these as being a bottleneck (which makes sense if you consider that these functions are likely to be called inside a large loop at some point). I have candidates for pow and %, maybe a more efficient implementation of log can also solve this problem. I will look into it.

[llersch]

• round before ceil?

This might be the best solution, for your case, rounding the result of the division to float before ceil yields the correct result:

cout << std::ceil(static_cast<float>(std::log(124+1) / std::log(5))) << endl;
3

The question is if the precision of float is enough. Hopefully yes.

• integer approximation for logarithmus? (e.g. multiply a=1 with 5 until a>index)

Not sure this solution would be correct. It seems it would give you floor of the division, instead of ceil.