Log 2

Request For Comments
#1

Hello,

I just noticed that there isn’t a library function to calculate log 2 of an integer; getting to this seems cumbersome via recursive loops (e.g. shift left 1 until zero), or some lookup (hash), best, if it were built in like the shift operator.

Here are some tricks to calculate it fast in C:

Dan

#2

I now noticed this:

I wonder how efficient this is, say, compared to a built in shift / loop implementation.

Also, this returns a real, which needs to be converted to integer – adding another step.

?- use_module(library(clpr)).
true.

?- {I = 2^3}.
I = 8.0 ;
false.

?- {8 = 2^E}.
E = 3.0 ;
false.
#5

Great.

How does it work internally?

#6

It just gets the most significant bit of an integer.

#7

Right,

But, an integer can be of any size, or at least the size of max_tagged_integer.

So, there has to be a way to identify that set bit that sits the most left within the memory cells allocated for that integer number – in a way log2 truncated does that – i.e. shows how many bits one needs to encode that number.

Dan

#8

The source code is public :slight_smile: The msb function is implemented in ar_msb in src/pl-arith.c. For tagged integers, it uses the macro MSB64 from src/pl-inline.h, which uses compiler builtins/intrinsics if possible, but also has a pure C fallback implementation. For larger integers, GMP is used to calculate how many digits the number would use in base 2, which is equivalent to the MSB position.

1 Like
#9

thanks :slight_smile:

Ah, yes, its public – should have thought about this …

#11

There’s also always the ability to just use the logarithmic identity to compute for an arbitrary base - X is log(128) / log(2) or ceil(log(N) / log(2)).

1 Like
#12

Hi James,

Indeed.

I am looking for something that performs really well. It looks like the msb would be the best fit for me right now – and if i need negative numbers or zero without exception then i could create a wrapper around it.

Dan

1 Like