Sphaerula

A recent slashdot.org thread discussed how a programmer at Microsoft incorrectly implemented a random shuffle algorithm. The discussion was prompted by an article Rob Weir wrote in which he presented a comprehensive analysis of the problem and provided a correct algorithm. Along the way, he named the botched implementation the “Microsoft shuffle.”

The following points are salient:

1. One can use Pearson’s Chi-squared test to determine if the results are non-random. In Weir’s analysis, the probability that the results were random (the probability that the null hypothesis was true) was p < 2.2e–16, given 10,000 repetitions of the algorithm.
2. Random shuffle algorithms are so commonly used that this is often an interview question for a programmer.
3. The Fisher-Yates shuffle is an excellent random shuffle algorithm of time complexity O(n).
4. The programmer who implemented the Microsoft shuffle did not understand how a sorting algorithm works.

As usual with discussions on slashdot, there were quite a few posters who didn’t understand the problem and why it required an accurate solution.

Yesterday Apple Inc. introduced its new tablet computer, the iPad. The best summary of the iPad that I have read is, not surprisingly, written by Adam Engst at tidbits.com. I provide here notes about the features that interest me.

The iPad is a computer for content consumers, not content creators. It is ideal for casual web browsing, watching television and movies, reading digital books, and playing games. The touted battery life of 10 hours, although undoubtedly exaggerated, is still long enough for a coast-to-coast flight. (It is not so ideal for listening to music, because I don’t have a pair of pants with pockets wide enough to hold it, unlike an iPod.)

For content creators, Apple has created new versions of its iWork suite for the creation of text-based documents (Pages), spreadsheets (Numbers), and slide presentations (Keynote). I am interested in learning how well this actually works without a keyboard and mouse.

The iPad has several shortcomings. Surprisingly, it has no camera. Other commentators have wondered whether Steve Jobs couldn’t decide where the camera should be located. The iPad really needs two cameras, one facing toward the user, for video conferencing, and one on the back for taking stills and videos.

The iPad operating system, which seems to be a variant of the iPhone OS, doesn’t allow multitasking. This is an annoyance, but I think we can anticipate that a future version of the OS will overcome this limitation.

Like the iPhone and the iPod touch, the iPad doesn’t support Adobe Flash. This means there is some material on the web that we won’t be able to view on an iPad. I’m not a big fan of Flash, because I hate how processor-intensive Flash is. If I want to bog down my old PowerBook G4, I just need to open two or three web pages with Flash animations.

I plan to buy one for use at home and to take with me when I travel. I already use my iPod touch as much as or more than my MacBook Pro when I’m at home. Other than listening to music and podcasts, I use it to check the weather, Facebook, Twitter, and email, watch movies, and read books. Movie watching and book reading will be more pleasant on the iPad. One thing I’m eager to test is whether I can read PDFs of scientific papers on an iPad.

Yesterday I finished reinstalling Vista Business on my MacBook Pro. I say finished, because the reinstallation required two days. I needed to reinstall Vista after I had updated Mac OS X to Snow Leopard (10.6), at which time I had wiped out my old Vista partition, which at 25 GB was too small.

I used Boot Camp Assistant to create a 32-GB partition and reboot my MacBook Pro from the Vista installation DVD. I installed Vista Business from the DVD and then began applying software updates. I should have counted these, but I estimate there were six separate operating system updates that I estimate required six hours to apply. The first update applied 93 individual patches to my system, and I let this run while I slept. If I remember correctly, it reported that it took 90 minutes to complete the update. Later updates updated Vista to SP1 (Service Pack 1) and SP2 (Service Pack 2). (I discovered that I couldn’t get the SP2 and later updates until I remembered to activate Vista.) One of the updates installed Internet Explorer 8; that one took a long time because I didn’t realize that it had displayed a dialog window for accepting the EULA. The problem was that the dialog was hidden under the main update window, where I couldn’t see it.

My question at this point is, why can’t Microsoft combine all these updates into a single update? Why do I have to install SP1 before I can install SP2? Why can’t SP2 contain all the changes already in SP1?

After installing Vista, I installed Office 2007 Professional, after which at least two more updates were required to bring it up to date, taking another two hours.

I want to contrast that experience to what happened last fall when I wiped clean my old PowerBook G4 and performed a fresh install of Leopard (Mac OS X 10.5). My install disk installed OS X 10.5 (which you would think would be called version 10.5.0, but Apple doesn’t begin adding the third numeric field until the first revision is released). When I ran software update, there was a single (massive) update that rolled all changes from 10.5 to 10.5.7 into a single update.

So the Microsoft Experience was six hours of time spent reinstalling Vista, and the Apple Experience was two hours of time spent reinstalling OS X 10.5. If I were doing this for a living, I would bill $75 per hour for my time — $450 for reinstalling Vista, $150 for reinstalling Leopard. The Microsoft Experience cost me an extra four hours of my time or $300 equivalent. This is the primary reason I prefer OS X over Vista — it is less expensive to install and maintain.

Note: What I really wanted to do was install Windows 7, but Apple has been slow in releasing the drivers necessary for full support. Having originally promised the new drivers by the end of 2009, Apple now provides a much more vague estimate of when the drivers will be available.