note
rubasov
<p>
Thank you all for your responses. I'm still digesting some of your notes, but I do see now that the scope of my little investigation was too narrow, that's why I wasn't able to find failing cases. (And as I haven't found those I was wondering how that can be...)
</p>
<p>
Fortunately my program would be used for statistical purposes, and nowhere near to the petabyte (2**50) file size range, so it'll avoid the real problems.
</p>
<p>
It is still interesting what would I do if I should care about the inaccuracy. Probably something like this sub I've written since my OP:
</p>
<code>
use bigint;
{
my @lookup = (1); # 2, 4, 8, ...
sub int_log2 {
my $n = shift;
return if $n < 1;
my $exp = 0;
# this still could be optimized by starting at
# $exp = min( $#lookup, $some_educated_guess_using_floating_point_approximation )
while ( $lookup[ $exp++ ] <= $n ) {
$lookup[$exp] = 2 * $lookup[ $exp - 1 ] if not exists $lookup[$exp];
}
return $exp - 2;
}
}
for ( 1 .. 2**10 ) {
print int_log2(2**$_-1), ' ', int_log2(2**$_), ' ', int_log2(2**$_+1), "\n";
}
</code>
<p>
This completes under 100sec on my several year old laptop.
</p>
824902
824902