9
$\begingroup$

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}} hadamardMatrix[n_ /; IntegerQ[Log[2, n]]] := KroneckerProduct[hadamardMatrix[2], hadamardMatrix[n/2]]

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

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ 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. $\endgroup$ Commented Oct 18, 2012 at 8:51
  • $\begingroup$ Possibly helpful: stackoverflow.com/questions/11436464/… $\endgroup$ Commented Oct 18, 2012 at 16:41

2 Answers 2

Reset to default
13
$\begingroup$

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

Improve this answer
$\endgroup$
9
  • $\begingroup$ If one still wants to take the logarithm route, BitLength[] is one function to look at... $\endgroup$ Commented Oct 18, 2012 at 8:39
  • $\begingroup$ @J.M. what are you thinking? $\endgroup$ Commented Oct 18, 2012 at 8:43
  • $\begingroup$ 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) $\endgroup$ Commented Oct 18, 2012 at 8:51
  • $\begingroup$ @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. :^) $\endgroup$ Commented Oct 18, 2012 at 8:54
  • $\begingroup$ "what are you thinking?" - well, BitLength[] is effectively equivalent to Log2[], so... $\endgroup$ Commented Oct 18, 2012 at 9:41
16
$\begingroup$

There is in fact an easy test to determine if an integer is a power of $2$, thanks to bit twiddling:

hadamardMatrix[1] := {{1}} hadamardMatrix[2] := {{1, 1}, {1, -1}} hadamardMatrix[n_Integer /; Positive[n] && BitAnd[n, n - 1] == 0] := KroneckerProduct[hadamardMatrix[2], hadamardMatrix[n/2]]
Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I was aware of the bit twiddling (I'm an electronics engineer and have low-level programmed lots of microcontrollers), but I thought the bit twiddling would be Mathematica's job, not mine :-). Still +1, thanks. $\endgroup$ Commented Oct 18, 2012 at 8:47
  • $\begingroup$ @steven, I know you're an EE; that's precisely why I brought bit twiddling up... ;) $\endgroup$ Commented Oct 18, 2012 at 9:39

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.