≡ Menu

The New & Improved Microsoft Shuffle

A quick update on my post from last week on the “Microsoft Shuffle“, where I looked at how Microsoft’s “random” browser ballot was far from random.

First, I’d like to thanks those who commented on that post, or sent me notes, offering additional analysis. I think we nailed this one. Within a few days of my report Microsoft updated their JavaScript on the browserchoice.eu website, fixing the error. But more on that in a minute.

Some random observations

Several commenters mentioned that if you search Google for “javascript random array sort” the first link returned will be a JavaScript tutorial that has the same offending code as Microsoft’s algorithm. This is not surprising. As I said in my original post, this is a well-known mistake. But it is no less a mistake. If you use Google Code Search for the query “0.5 – Math.random()” lang:javascript you will find 50 or so other instances of the faulty algorithm. So if anyone else is using this same algorithm, they should evaluate whether it is really sufficiently random for their needs. In some case, such as a children’s game, it might be fine. But know that there are better and faster algorithms available that are not much more complicated to code.

Another thing to note is that the Microsoft Shuffle algorithm is bad enough with 5-elements in the array, but the non-randomness gets more pronounced as you increase the length of the array. Regardless of the size of the array, it appears that on Internet Explorer the 1st element will end up in last place 50% of the time. There are other pronounced patterns as well. You can see this yourself this this test file, which allows you to specify the size of the array as well as the number of iterations. Try a 50-element array for 10,000 iterations to get a good sense of how non-random the results can be.

I used that script to run a large test of 1,000,000 iterations of a 1024-element array. The raw results are here. I took that table, and using R’s image() function produced a rendering of that matrix. You can see here the clear over-representation at some positions, including (in the lower left) the flip of the first position to last place. (I’m not quite satisfied with this rendering. Maybe someone can get a better-looking visualization of this same data.)

Evaluating Microsoft’s new shuffle

Sometime last week — I don’t know the exact date — Microsoft updated the code for the browser choice website with a new random shuffle algorithm. You see the code, in situ, here. The core of it is in this function:

function ArrayShuffle(a)
{
    var d, c, b=a.length;
    while(b)
    {
        c=Math.floor(Math.random()*b);
        d=a[--b];
        a[b]=a1;
        a1=d
     }
}

This looks fine to me. I created a new test driver for this routine, which you can try out here. Aside from being much faster, it is gives much better results. Here is a run with a million iterations:

 

Raw counts

Position I.E. Firefox Opera Chrome Safari
1 199988 200754 199944 199431 199883
2 200320 200016 199838 199752 200074
3 199702 199680 199911 200865 199842
4 200408 200286 199740 199861 199705
5 199582 199264 200567 200091 200496

Fraction of total

Position I.E. Firefox Opera Chrome Safari
1 0.2000 0.2008 0.1999 0.1994 0.1999
2 0.2003 0.2000 0.1998 0.1998 0.2001
3 0.1997 0.1997 0.1999 0.2009 0.1998
4 0.2004 0.2003 0.1997 0.1999 0.1997
5 0.1996 0.1993 0.2006 0.2001 0.2005

And the results of the Chi-square test:

X-squared = 18.9593, df = 16, p-value = 0.2708

Final thoughts

In the end I don’t think it is reasonable to expect every programmer to memorize the Fisher-Yates algorithm. These things belong in our standard libraries.   But what I would expect every programmer to know is:

  1. That the problem here is one that requires a “random shuffle”. If you don’t know what it is called, then it will be difficult to lookup the known approaches. So this is partially a vocabulary problem. We, as programmers, have a shared vocabulary which we use to describe data structures and algorithms; binary searches, priority heaps, tries, and dozens of other concepts. I don’t blame anyone for not memorizing algorithms, but I would expect a programmer to know what types of algorithms apply to their work.
  2. How to research which algorithm to use in a specific context, including where to find reliable information, how to evaluate the classic trade-offs of time and space, etc.  There is almost always more than one way to solve a problem.
  3. That where randomized outputs are needed,  the outputs should be statistically tested. I would not expect the average programmer to know how to do a chi-square test, or even to know what one is. But I would expect a mature programmer to know either find this out or seek help.

Creative Commons License
This work, unless otherwise expressly stated, is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 United States License.

{ 13 comments… add one }

  • orcmid 2010/03/06, 15:36

    Yes, the ArrayShuffle(a) procedure that is now used is an implementation of Algorithm 3.4.2P (Shuffling) in [D.E.Knuth. The Art of Computer Programming, vol.2: Seminumerical Algorithms. ed.3 pp.145-146]. The ECMAScript version is a tidy little thing.

    Knuth also reports that the (effective) modulus of the random number generator is a factor, since that can prevent all possible n! permutations from appearing in the list of n selections (or a shuffled deck of n cards, where the problem can be serious).

    For n=5 I wouldn’t expect trouble. Of course, the random number generator quality can be a factor in other ways.

  • The Mad Hatter 2010/03/07, 06:37

    While it may be a simple mistake, Microsoft are supposed to be professionals. At least they claim they are.

    Thanks for the articles, they were an interesting read. Since I don’t use Windows or do Javascript I wouldn’t have seen this myself.

  • Christoph S. 2010/03/07, 17:26

    The analysis is done well, I like it. Only a minor problem: The link to the shuffle2.html is currently broken (mixed in a semicolon…).

  • orcmid 2010/03/07, 17:52

    I supposed they didn’t think they needed a rocket scientist to create a randomized list of five items on demand.

    What is even funnier is that the improved method does two shuffles when one has to be enough. (shuffle the indexes and the rest follows). It doesn’t seem to matter, but it does obscure what is being done and inspecting to confirm that what is being done is sufficient.

    I guess deciding that if shuffling one list is good, shuffling another one too must be better, is an indication that the rocket scientist has left the building (or decided to leave things alone the parts that don’t matter anyhow).

  • Rob 2010/03/07, 19:44

    @orcmid, you don’t to be a genius to get it right. But you do need access to a compendium of algorithms written by geniuses of the past. We stand on the shoulders of giants: Hoare, Dijkstra, Knuth, etc.

  • Rob 2010/03/08, 17:58

    Hmmm… maybe knowledge of algorithms is more widespread than I realized. See, for example, this:

    http://www.youtube.com/watch?v=k4RRi_ntQc8

  • Noam Gal 2010/03/09, 05:57

    Strange – running both of your tests in Chrome yielded a much more even results. I haven’t checked their p-value, but even with the 50/10000, most table cells are between 180 and 230. I wonder how Chrome manages to run the “wrong” algorithm in a somewhat more random way.

  • Jose_X 2010/03/09, 11:32

    Noam Gal, if you mean that the old 0.5-rand() algorithm appears to have a more even distribution from the trials (is this what you mean?), it could be because the quicksort routine does produce an even distribution for it. It would not be unusual that Chrome would use quicksort (although other algorithms could also exhibit this property). This observation was covered in a number of comments in the first article. There was even a link to someone that ran a bunch of trials with the old algorithm on various standard sorts, and you can clearly see that quicksort has an even distribution (the others did not).

  • Rob 2010/03/09, 20:51

    @Noam, I think we should put to bed the idea that Microsoft’s original random shuffle algorithm is acceptable in any browser. It may work better in some than others, or with some sort algorithm than others, but I have yet to see it actually produce reasonably random results.

    In the case of the browser ballot case I tested only the simplest quality of the outcomes, namely whether each browser occurred equally often in each position. I tested whether the positions were uniformly distributed.

    That is a necessary condition of a good random shuffle — and in the case of the browser ballot might be all that is needed — but it is not a sufficient condition for a good general purpose random shuffle. What you want in the general case is that all possible combinations are equally likely. Otherwise, I could just treat the array as a circular array and rotate it in order: 01234, 12340, 23410, 34012, 40123, and have perfectly uniform distribution of positions with only 5 different unique permutations. Now that might be fine for a browser ballot, but imagine the trouble if you did a random shuffle of a card deck that way! (In other words, take the top card and place it at the bottom of the deck and call it good enough.)

    What you really want is for all of the N! (in our case 120) different permutations to have an equal chance of occurring. So uniform distribution of all possible orderings of the array.

    I did a quick test of 1,000,000 iterations, looking at how often each of the 120 orderings occurred, and it is clear that the Microsoft shuffle is not doing a good job, even in Chrome. I also added a column for the Fisher-Yates shuffle on Internet Explorer, for comparison.

    Combination IE Firefox Chrome Fisher-Yates
    01234 508 66200 15645 8467
    01243 3327 3939 15654 8356
    01324 3449 33188 15651 8232
    01342 22644 1869 15710 8306
    01423 1946 7636 15501 8359
    01432 2938 3900 15712 8326
    02134 701 32996 7890 8301
    02143 5665 1982 7818 8303
    02314 5556 16625 7759 8247
    02341 11109 956 7797 8367
    02413 788 3876 7924 8384
    02431 1457 1940 7881 8202
    03124 1956 16483 15696 8235
    03142 18477 995 15663 8414
    03214 3383 8478 7676 8460
    03241 6876 474 7761 8192
    03412 9648 1970 15485 8321
    03421 3888 995 7776 8403
    04123 3394 15433 7705 8356
    04132 2871 7713 7798 8197
    04213 488 7702 3789 8371
    04231 949 3912 3915 8447
    04312 13749 3946 7910 8336
    04321 6783 1944 3993 8289
    10234 497 66488 15657 8328
    10243 3346 3905 15633 8310
    10324 3548 33155 15510 8366
    10342 22446 1947 15520 8171
    10423 1878 7621 15552 8385
    10432 2943 3903 15798 8509
    12034 717 33495 7800 8247
    12043 4623 1960 7827 8337
    12304 3287 16637 7864 8317
    12340 44916 968 7829 8317
    12403 2468 3857 7949 8401
    12430 5604 1907 7873 8366
    13024 2424 16611 15612 8389
    13042 13596 996 15752 8406
    13204 1976 8260 7916 8441
    13240 27321 470 7781 8439
    13402 7779 1887 15457 8165
    13420 15609 948 7864 8310
    14023 2441 15738 7762 8351
    14032 1998 7638 7827 8329
    14203 1958 7999 3917 8401
    14230 3854 3927 3762 8254
    14302 13617 3839 7547 8239
    14320 27391 1953 3887 8270
    20134 750 33267 7806 8429
    20143 5689 2030 7679 8240
    20314 5648 16630 7859 8344
    20341 11326 994 7872 8386
    20413 728 3818 7781 8255
    20431 1458 1929 7975 8365
    21034 720 33345 7806 8232
    21043 4715 1896 7738 8360
    21304 3418 16677 7863 8236
    21340 45101 983 7846 8465
    21403 2430 3894 7710 8120
    21430 5914 1967 7877 8273
    23014 4679 8338 7696 8263
    23041 9371 501 7838 8330
    23104 2426 8377 7913 8332
    23140 37102 464 7894 8315
    23401 4836 965 7850 8401
    23410 19535 931 7777 8175
    24013 713 7913 3892 8106
    24031 1497 3891 3874 8472
    24103 3384 8018 3862 8331
    24130 5829 3947 3894 8514
    24301 6880 1938 4001 8463
    24310 27276 1948 4074 8383
    30124 2004 16620 15642 8217
    30142 18677 977 15598 8083
    30214 3409 8358 7822 8484
    30241 7066 487 7882 8412
    30412 9888 1924 15554 8238
    30421 3924 987 7724 8273
    31024 2429 16573 15690 8225
    31042 13381 1010 15565 8413
    31204 2066 8257 7725 8382
    31240 27326 513 7806 8301
    31402 7912 1999 15530 8359
    31420 15493 1067 7975 8409
    32014 4612 8302 7814 8412
    32041 9434 508 7766 8342
    32104 2400 8345 7730 8362
    32140 37043 466 7875 8406
    32401 4919 1002 7743 8353
    32410 19341 987 7630 8426
    34012 7749 3950 7889 8307
    34021 4780 1985 3947 8292
    34102 9866 3945 7862 8393
    34120 19658 1908 3816 8351
    34201 3860 1991 3761 8220
    34210 15367 1916 3946 8448
    40123 3478 31351 7719 8296
    40132 2800 15675 8029 8380
    40213 478 15780 4021 8320
    40231 1006 7823 3892 8350
    40312 13676 7915 7800 8344
    40321 6850 3928 3945 8413
    41023 2449 31019 7730 8224
    41032 2025 15620 7736 8401
    41203 1901 15444 3865 8446
    41230 3924 7959 3838 8383
    41302 13743 7858 7737 8417
    41320 27417 3871 3949 8293
    42013 688 15562 3971 8336
    42031 1446 7942 3912 8209
    42103 3548 15564 3778 8311
    42130 5895 7807 3913 8385
    42301 6815 3881 4015 8187
    42310 27509 3838 3981 8328
    43012 7716 7808 7751 8389
    43021 4906 3952 3890 8369
    43102 9640 7779 7900 8249
    43120 19477 3865 3940 8360
    43201 3931 3886 3966 8309
    43210 15746 3754 3928 8362

    And it doesn’t end there. There are other tests you might want to apply, a whole battery of them, to fully test a random shuffle algorithm. The browser ballot case only required (IMHO) the simplest quality — uniform distribution of browser positions. Other uses might require additional qualities, including lack of correlation across shuffles. (Otherwise I could just repeat the same 120 permutations in order, over and over again.) Because of that I would always recommend to use a tried-and-true algorithm like Fisher-Yates over something that “seems to work” but has not been rigorously characterized.

  • fred bloggs 2010/03/15, 06:25

    Each party fetches the script separately from Microsoft. There are a couple of opportunities for bias in this situation:

    1. What is stopping a man-in-the-middle attack from altering the ballot script?

    2. It’s impossible to be sure that every single instance of the script served to clients is the same. The script could be varied based on knowledge of the geography of the requestor (mined from the IP number), or perhaps just alter a small percentage of the scripts that are served to introduce a bias.

    I’d be astonished if Microsoft was practicing Item 2 (because of the risk to their reputation if caught, relative to the small potential for benefit), but thought I’d mention it anyway as part of trying to explore the entire infrastructure, looking for points at which fraud could be practiced.

    – recherche

  • hm 2010/04/19, 23:44

    I wonder why MS is allowed to control the ballot screen, shouldn’t it be ran by someone else, EU itself perhaps?

  • mistaecko 2011/03/25, 00:15

    Well it’s more than a year after the browserchoice ‘incident’ and I may point out that the copy of the algorithm in your blog post has the var names mixed up (see ‘c’) :D

  • Rob 2011/03/25, 08:04

    @mistacko, Wow, that was a mess. It looks like that got scrambled somewhere along the way. I suspect the syntax highlighter plugin. I updated the snippet so it correctly shows what Microsoft used, and what I tested.

    Thanks!

    -Rob

Leave a Comment