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$
  • 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 '12 at 8:51
  • $\begingroup$ Possibly helpful: stackoverflow.com/questions/11436464/… $\endgroup$ – barrycarter Oct 18 '12 at 16:41
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$
  • $\begingroup$ If one still wants to take the logarithm route, BitLength[] is one function to look at... $\endgroup$ – J. M. will be back soon Oct 18 '12 at 8:39
  • $\begingroup$ @J.M. what are you thinking? $\endgroup$ – Mr.Wizard Oct 18 '12 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 '12 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 '12 at 8:54
  • $\begingroup$ "what are you thinking?" - well, BitLength[] is effectively equivalent to Log2[], so... $\endgroup$ – J. M. will be back soon Oct 18 '12 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$
  • 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 '12 at 8:47
  • $\begingroup$ @steven, I know you're an EE; that's precisely why I brought bit twiddling up... ;) $\endgroup$ – J. M. will be back soon Oct 18 '12 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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