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:
- 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.
- Random shuffle algorithms are so commonly used that this is often an interview question for a programmer.
- The Fisher-Yates shuffle is an excellent random shuffle algorithm of time complexity O(n).
- 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.
February 28 2010 | Computing | 2 Comments »
Although I love bicycling, I have not done any serious bicycling for several years. In the 1970’s, I was a bicycle commuting pioneer in Portland, Oregon, riding in the morning from my home in SE Portland to classes downtown at Portland State University, then in the afternoon out Sandy Boulevard to my job on NE 82nd Avenue, and finally back home after midnight for a total distance of over 20 miles. During that time I also did some solo tours to the Oregon Coast and the occasional 80-mile ride to Corvallis to visit my friends at Oregon State University.
The closest I’ve been to serious riding since those days was 2006, while I was taking a needed rest from working, when I signed up and began training for an Adventure Cycling tour from Puget Sound to Maine. Employment found me before the trip started, and I had to cancel, putting my life-long dream of a cross-country trip on hold.
I own a used 1980’s model Raleigh road bike that I still ride occasionally, but there are many things about it that dissatisfy me. I don’t like the touring handlebars for riding in the city because I need to keep my head up to watch for cars and other bicyclists. The gearing is not well suited for climbing hills. And the shifters are on the crossbar, not on the handlebars. I have had it in mind for a few years now to buy a modern bicycle.
A year ago, when I was in Florida, I rented a Marin Kentfield for a day to ride on the bicycle path. The frame was too small, but I really enjoyed the shifters, which were mounted near the handle grips, and the range of gears seemed adequate for climbing hills. The Kentfield had straight handlebars and an upright sitting position, and it felt much more nimble and maneuverable than my Raleigh.
I spent the last year reading about the new bicycles, with the thought in mind that I wanted a commuter bike that I could also use for light touring. After dithering for a year, I went to Ace Wheelworks in Somerville yesterday to buy a new bicycle. I had in mind to try four or five models, but I was focused on the Trek Valencia as the model that had the features I desired. I was very interested in the Valencia because of a series of reviews by Bike Geek.
The salesperson at Wheelworks was helpful and patient, and he helped guide me to a decision. At first, his recommendations were cautious, and the first model he had me try was a Specialized Globe Vienna Deluxe 1. This model comes stock with fenders, rack, and light, and it was easy to ride. This model is designed for commuting up to five miles, and I could tell that it would become increasing uncomfortable on longer rides.
The second model was a Trek Soho, which has a Shimano 8-speed internally geared rear hub and belt drive. This is an ideal commuter bike because it doesn’t require the maintenance that derailleurs and a chain require. However, I didn’t think the range of gears, especially the lowest gear, would be suitable for light touring.
The third model I tried was a Trek Soho 3.0. This is a hybrid bike with a frame that was probably too small for me, but it felt zippy and nimble, with excellent brakes. I was very tempted by this model, but I would have wanted to try a larger frame size.
Finally, I tried the Trek Valencia. I like this model because it comes with disc brakes, which would be ideal for light touring, and it has fender and rack mounts. The Valencia is almost identical to the Soho 3, sharing most of the same parts, except for the disc brakes. The only model they had on the floor was the 20″ frame, which the salesperson thought would be too big for me, but that turned out to be a good size. Shifting was very smooth, and the disc brakes were very effective.
In the end, I purchased the Trek Valencia, which cost $680. I knew ahead of time that I was going to spend a couple hundred dollars on accessories. I added Planet 700c hybrid fenders, a Blackburn EX-1 rear rack, Blackburn Voyager 3.3/Mars 1.0 LED headlight and taillight combo, water bottle cage, Topeak Peak Master DX pump, and a Jandd Commuter Pannier, for a total cost of $906.73 plus sales tax.
I pick up the new bike this afternoon. Watch for reviews.
February 07 2010 | Bicycling | No Comments »
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.
January 28 2010 | Computing | No Comments »
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.
January 10 2010 | Computing | 1 Comment »
For the past two or three weeks, I’ve been reading Neal Stephenson’s Cryptonomicon, a novel published in 1999. Much of the story in the novel concerns cryptography, and page 480 contains a Perl script that can be used to encrypt and decrypt messages using the Solitaire cryptosystem.
As published in the novel, the Perl script is gibberish, impossible to read and understand. Fortunately, the “verbose version” of the script is available on Bruce Schneier’s web site at www.schneier.com/code/sol.pl. Bruce Schneier provides an explanation of the Solitaire Encryption System at www.schneier.com/solitaire.html. And Neal Stephenson himself discusses the novel and the Perl script at web.mac.com/nealstephenson/Neal_Stephensons_Site/cypherFAQ.html.
Cryptonomicon is a brilliant novel, and it reminds me in many ways of Gravity’s Rainbow by Thomas Pynchon, one of my favorite books. It is a book I know I’ll have to read more than once, because I’m certain I’m missing important clues and subtexts in the story that will become apparent only on a rereading.
January 09 2010 | Books and Computing | No Comments »
An article by Adam Liptak in the New York Times today describes how the American Law Institute has given up attempting to maintain an intellectual framework for the death penalty.
A study commissioned by the institute said that decades of experience had proved that the system could not reconcile the twin goals of individualized decisions about who should be executed and systemic fairness. It added that capital punishment was plagued by racial disparities; was enormously expensive even as many defense lawyers were underpaid and some were incompetent; risked executing innocent people; and was undermined by the politics that come with judicial elections.
The death penalty is never just, and it’s time to eliminate it.
January 04 2010 | Society | No Comments »
Fourteen months ago I traded in my old iPod mini for a new 8-GB iPod touch. I think the price at the time was about $230, but I got a 10% discount for exchanging the old iPod mini.
Six weeks later, I dropped the iPod touch from waist height onto brick pavement and broke it; the impact created a dent in the metal back and apparently crushed some of the electronic components inside. (These things are surprisingly delicate.) I took it to the Apple store on Boylston Street in Boston and asked if they could fix it. The answer was no, but they offered me a refurbished unit in exchange for the broken unit and a little under $130. I have been using the refurbished iPod for over a year now.
Since I live in an urban area, I usually have wifi connectivity. (For example, when I’m waiting for the bus in Kendall Square, I get a good connection to MIT Guest wifi.) This means I don’t need to buy a smart phone such as the iPhone; I get nearly iPhone-equivalent functionality from two devices, my minimal cell phone ($40 a month with Verizon) and my iPod touch, saving me roughly $40 per month that I can spend on books or music.
I was slow to take advantage of all of the iPod touch’s capabilities, using it initially for listening to music, podcasts, and audiobooks. I usually commute to work by walking, a 45-minute trip each way. I can listen to two audiobooks per month plus quite a few podcasts during my commuting time.
The first apps I added were news-, information-, and book-related: New York Times, Bloomberg, Yahoo Finance, WeatherBug Elite, Stanza, and Shakespeare Pro. I find that the iPod touch makes for a great electronic book reader (although I still haven’t found a good app for reading PDFs of research papers).
Lately I’ve been taking advantage of the iPod touch’s abilities to act as a small pocket computer. I purchased the American Heritage Deluxe dictionary app ($35), and I feel like I’ve already gotten my money’s worth for that app alone because now I have an unabridged dictionary in my pocket and I use it all the time. I also installed the Facebook, LinkedIn, TweetDeck, and WordPress apps for managing my Web 2.0 presence. And recently I set up two new email addresses that I use primarily from the iPod touch with the Mail app.
Lately, I’ve begun buying movies and TV shows from the iTunes store. The TV shows are, in my opinion, an incredible bargain. I bought the first season (twelve episodes, 10 hours) of HBO’s Rome for only $20. Recently, I taught myself how to use Handbreak and VLC to copy my DVDs to mpeg files formatted for the iPod touch.
The result is that my little 8-GB iPod touch is feeling cramped for space. First of all, the 8-GB iPod touch actually has 7.66 GB of storage capacity. (Is the remaining 0.34 GB used for the operating system and included apps?) Second, I have almost 2 GB of apps installed, the dictionary being the largest. Third, I like to carry one or two TV shows or a movie with me, and each of these is roughly 0.6 GB in size. Fourth and finally, I like to carry plenty of music and audiobooks.
Consequently, I’m ready to buy a new iPod touch. The bigger models have 32 GB and 64 GB of storage and list for $300 and $400, respectively. However, rumor has it that the next model of the iPod touch will include a camera for stills and video, and I would find a camera quite useful. And rumor has it that Apple is about to announce its new tablet computer, allegedly named the iSlate. So I’ve decided to bide my time to see what Apple might announce in the next few months.
January 03 2010 | Computing | 1 Comment »
Next »
