 # Log 2

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

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.
``````

Great.

How does it work internally?

It just gets the most significant bit of an integer.

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

The source code is public 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

thanks 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

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