22
$\begingroup$

Bug introduced in 10.0.0 and fixed in 10.0.2

With Mathematica 10 for Mac, BitShiftRight works properly on lists of up to 100000 numbers, but appears to give incorrect results when threaded over lists of 100001 or more:

v1 = Table[i, {i, 1, 100000}];
v2 = Table[i, {i, 1, 100001}];
s1 = BitShiftRight[v1];
s2 = BitShiftRight[v2];
s1[[1 ;; 10]]
s2[[1 ;; 10]]

Out[1070]= {0, 1, 1, 2, 2, 3, 3, 4, 4, 5}

Out[1071]= {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}

The error seems to occur for any BitShiftRight[n,k] whenever n is a list exceeding 100000 values.

Mathematica 9 gives correct output:

v1 = Table[i, {i, 1, 100000}];
v2 = Table[i, {i, 1, 100001}];
s1 = BitShiftRight[v1];
s2 = BitShiftRight[v2];
s1[[1 ;; 10]]
s2[[1 ;; 10]]

Out[799]= {0, 1, 1, 2, 2, 3, 3, 4, 4, 5}

Out[800]= {0, 1, 1, 2, 2, 3, 3, 4, 4, 5}

I have several notebooks that apply BitShiftRight[n,k] to very large lists. The only Mathematica 10 workaround seems to be the equivalent IntegerPart[n/2^k] that continues to work on very large lists, but is slower and requires rewriting previously working code. Otherwise I would need to stick with MM 9 for these notebooks.

Can anyone confirm this anomalous MM 10 output? Does it affect other platforms? Am I missing something simple, or is this a true MM 10 bug?

Thanks

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ I can confirm the result on M10 running on Win7-64 (Ultimate). $\endgroup$
    – Ymareth
    Jul 30, 2014 at 20:57
  • $\begingroup$ That's a surprising bug. Compact example: v = Range[100001]; a = BitShiftRight[v[[;; 10]]]; b = BitShiftRight[v][[;; 10]]; a == b is False. $\endgroup$
    – Mr.Wizard
    Jul 30, 2014 at 21:08
  • $\begingroup$ I can confirm this on Windows 8.1. Interesting bug. BitShiftLeft works fine by the way. $\endgroup$
    – RunnyKine
    Jul 30, 2014 at 21:14
  • 2
    $\begingroup$ part 1: Here's a guess/suspicion I venture to suggest as a comment, which could be the cause. Try: max = $MaxNumber. After trying to contemplate that magnitude for a moment: max = Log[2, max] is Log[2, max]. So to me it looks as if WRI may have implemented a precision scheme, using the IEEE 64 bit floating point algorithm recursively by using the parallel framework.IEEE 64 bit gets 53 bit precision by always using the same first bit. $\endgroup$
    – Andreas Lauschke
    Jul 31, 2014 at 17:50
  • 2
    $\begingroup$ part 2: If you were to use it recursively, parallel or not, you would only get 52 bits on each precision level. The two things could be related if M is using integers in the same schema as rationals with no modular remainder; it wouldn't be hard to screw up the bit arithmetic if everything was being stored in an array of IEEE 64 bit floating point numbers using Intel's vector system. When you apply Developer`PackedArrayQ[v2] to the example you get True. $\endgroup$
    – Andreas Lauschke
    Jul 31, 2014 at 17:51

2 Answers 2

Reset to default
15
$\begingroup$

Solution

It appears this bug is the result of attempted parallelism gone wrong.
I believe it is corrected in all cases by setting this System Option:

SetSystemOptions[
 "ParallelOptions" -> {"MachineFunctionParallelThreshold2" -> Infinity}
]

This appears to be an out and out bug and I tagged the question accordingly.

Original observations:

Compact example:

v = Range[100001];
a = BitShiftRight[v ~Take~ 10];
b = BitShiftRight[v] ~Take~ 10;
a == b

False

This also affects (at least) tensors with more than 100,000 elements:

v = RandomInteger[99, {80, 80, 55}];
a = BitShiftRight[v ~Take~ 10];
b = BitShiftRight[v] ~Take~ 10;
a == b

False
Improve this answer
$\endgroup$
5
$\begingroup$

Fixed in 10.0.2

Mathematica graphics

v1 = Table[i, {i, 1, 100000}];
v2 = Table[i, {i, 1, 100001}];
s1 = BitShiftRight[v1];
s2 = BitShiftRight[v2];
s1[[1 ;; 10]]
s2[[1 ;; 10]]

Mathematica graphics

v = Range[100001];
a = BitShiftRight[v[[;; 10]]];
b = BitShiftRight[v][[;; 10]];
a == b

Mathematica graphics

Improve this answer
$\endgroup$

Your Answer

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

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