# How does Mathematica decide that Log[2,8] is integer?

At school we learned that $\log_b(x)=\log(x)/\log(b)$, which is implemented in Mathematica as Log[b, x], but the results are different.

Log[8]/Log[2] // N


returns

3.  (* Real *)


while

Log[2, 8]


returns

3  (* Integer *)


If I want to validate the argument of my hadamardMatrix[] function as a power of 2:

hadamardMatrix[1] := {{1}}
hadamardMatrix[2] := {{1, 1}, {1, -1}}


How can I be sure that any Log[2, 2N] will always be regarded as integer?

-
Of course, in your first snippet, you ensured your not getting an Integer by applying N. Try Log[2, 8]//N to see that you don't get an Integer either. –  celtschk Oct 18 '12 at 8:51
Possibly helpful: stackoverflow.com/questions/11436464/… –  barrycarter Oct 18 '12 at 16:41

An interesting question which I've never specifically considered before.

Some observations:

Log[8]/Log[2] // FullSimplify

Log2[8]

Log[2, 8]

3

3

3

And @@ IntegerQ /@ Log2[2^Range[50000]]

And @@ Table[IntegerQ@Log2[2^RandomInteger[5*^8]], {500}]

True

True


Mathematica documentation explicitly states:

Log2 gives exact integer or rational number results when possible.

Also for Log:

Log gives exact rational number results when possible.

For certain special arguments, Log automatically evaluates to exact values.

I think that based on the combination of the empirical result and the statements in the documentation that it is safe to assume that Log2 will return an integer when given a 2^n number.

As far as how this is determined the Implementation Notes say only:

Log and inverse trigonometric functions use Taylor series and functional relations.

which I'm not sure applies.

Timings of Log2 compared to J. M.'s lovely bit-level test:

Do[IntegerQ @ Log2 @ n, {n, 1*^7}] // AbsoluteTiming // First

Do[BitAnd[n, n - 1] == 0, {n, 1*^7}] // AbsoluteTiming // First


15.9120279

6.4116112

And now vectorized:

a = Range@1*^6;

Position[Log2@a, _Integer, {1}] // AbsoluteTiming // First

Position[BitAnd[a, a - 1], 0] // AbsoluteTiming // First


1.4196025

0.0468001

-
If one still wants to take the logarithm route, BitLength[] is one function to look at... –  Ｊ. Ｍ. Oct 18 '12 at 8:39
@J.M. what are you thinking? –  Mr.Wizard Oct 18 '12 at 8:43
Aaah, I should have dug deeper in the documentation :-(. I knew about Log10[], but didn't know there was a Log2[] as well. Thanks. (No need for Taylor here) –  stevenvh Oct 18 '12 at 8:51
@stevenvh I don't think your question has been answered but I'm not sure it can be by anyone other than the Mathematica developers. Nevertheless given the vastly superior performance of BitAnd it apparently isn't anything special. :^) –  Mr.Wizard Oct 18 '12 at 8:54
"what are you thinking?" - well, BitLength[] is effectively equivalent to Log2[], so... –  Ｊ. Ｍ. Oct 18 '12 at 9:41
There is in fact an easy test to determine if an integer is a power of $2$, thanks to bit twiddling:
hadamardMatrix[1] := {{1}}