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?

$\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$
    – celtschk
    Oct 18, 2012 at 8:51
  • $\begingroup$ Possibly helpful: stackoverflow.com/questions/11436464/… $\endgroup$
    – user1722
    Oct 18, 2012 at 16:41

2 Answers 2

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

$\endgroup$
9
  • $\begingroup$ If one still wants to take the logarithm route, BitLength[] is one function to look at... $\endgroup$ Oct 18, 2012 at 8:39
  • $\begingroup$ @J.M. what are you thinking? $\endgroup$
    – Mr.Wizard
    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$
    – stevenvh
    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$
    – Mr.Wizard
    Oct 18, 2012 at 8:54
  • $\begingroup$ "what are you thinking?" - well, BitLength[] is effectively equivalent to Log2[], so... $\endgroup$ 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]]
$\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$
    – stevenvh
    Oct 18, 2012 at 8:47
  • $\begingroup$ @steven, I know you're an EE; that's precisely why I brought bit twiddling up... ;) $\endgroup$ Oct 18, 2012 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.