{"id":450,"date":"2007-12-09T17:41:27","date_gmt":"2007-12-09T07:41:27","guid":{"rendered":"http:\/\/www.somethinkodd.com\/oddthinking\/2007\/12\/09\/shuffling-and-ownage\/"},"modified":"2007-12-09T17:47:55","modified_gmt":"2007-12-09T07:47:55","slug":"shuffling-and-ownage","status":"publish","type":"post","link":"https:\/\/www.somethinkodd.com\/oddthinking\/2007\/12\/09\/shuffling-and-ownage\/","title":{"rendered":"Shuffling and Ownage"},"content":{"rendered":"

Last week, Mike Pope<\/a> wrote about card-shuffling<\/a>.<\/p>\n

By his own admission, he didn’t know the best way, and he described a number of sub-optimal solutions – generally O(n2<\/sup>) – but some had an unbounded worst case, and one displayed biases.<\/p>\n

Another commenter pointed to John Viega<\/a>‘s solution, which assigned a random number to each card, sorted the result, and then reshuffled if no two random numbers were the same. It was on average about O(n.log n) but it had an unbounded worst case.<\/p>\n

So along I came, and ever so helpfully added a comment to the article with an algorithm I stole off a Commodore-64 program and have been using (very occasionally) for over 20 years. It is short, bounded, takes O(n), it has a low-constant time and a small memory footprint<\/p>\n

Pope came back to say he’s tried it, but he was not sure of the randomness. I wasn’t sure how to respond to that – it was obvious that it is completely random to me. I made a note to go back to leave another comment, but before I got a chance…<\/p>\n

… along came Jeff Atwood at Coding Horror<\/a>, and he waded in with a post<\/a>. (Actually, Eric Lippert<\/a> argued against my algorithm first in a comment on the article, but I saw Jeff Atwood’s post before Eric Lippert’s comment.) Atwood brought up an algorithm very similar to the one that I had proposed, and then tried to shoot it down on two grounds.<\/p>\n

One, that it was too complicated. I didn’t feel that it was complicated at all. Then again, I have been using it for a while and it seems natural. Anyway, quicksort is more complicated than bubblesort, but you implement it once, and it’s done, right?<\/p>\n

The other was that its random number generator wasn’t secure enough. (There’s a very slight strawman here – my original didn’t mention the seeding of the random number generator, but (a) Atwood wasn’t trying to directly attack my solution, he was trying to attack a naive solution that he himself would have tried, and (b) Atwood’s solution wasn’t much different to the one I would have chosen, had I bothered to mention it.)<\/p>\n

My response to that was to grumble to myself about security experts who think every single project has security implications, resulting in terrible scope creep. Yes, if you are implementing an online casino, the security of randomisation is a real problem. However, for a huge majority of implementations, it simply isn’t an issue. For a single player implementation of Klondike<\/a> it isn’t important. My main use of card-shuffling is for Monte Carlo simulations<\/a>. The idea that someone could crack the code and start predicting what was going to come next is irrelevant in these situations.<\/p>\n

If you have a choice between implementing securely or insecurely for the same price, obviously you should take the secure method – hey, you never know when your code will be re-used – but how much does the secure method cost?<\/p>\n

Atwood recommends generating a GUID per card, and sorting by that! Oh dear! Not only is it O(n.log n) but it has a huge constant time. My Monte Carlo simulations are going to be dominated by the card-shuffling, especially when testing a game like Blackjack with simplistic play and 416 card decks. I’ll stick with my algorithm, thanks!<\/p>\n

I made a note to go back to leave another comment, but before I got a chance…<\/p>\n

… Atwood posted another follow-up<\/a> in which he called the algorithm I used “na\u00c3\u00afve”. He then quietly demonstrated that it wasn’t truly random at all. <\/p>\n

You could have knocked me down with a feather. I was completely wrong. Perhaps “na\u00c3\u00afve” is the word!<\/p>\n

My algorithm had biases – exactly the sort of biases that you don’t<\/em> want in a Monte Carlo simulation.<\/p>\n

Atwood points out that a slightly different implementation<\/a> fixes the problem, and seems to offer the best of both worlds.<\/div>\n

In summary: I’ve been owned by Jeff Atwood. Eric Lippert owns a part-share of me, too.<\/p>\n","protected":false},"excerpt":{"rendered":"

In which Jeff Atwood dismisses my experience as “na\u00c3\u00afve”… <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_s2mail":"","footnotes":""},"categories":[28,25,34],"tags":[189,191,190,90,188],"class_list":["post-450","post","type-post","status-publish","format-standard","hentry","category-doubleplus-geek","category-insufficiently-advanced-technology","category-software-development","tag-cards","tag-coding-horror","tag-randomness","tag-security","tag-shuffling"],"_links":{"self":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts\/450","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/comments?post=450"}],"version-history":[{"count":0,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts\/450\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/media?parent=450"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/categories?post=450"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/tags?post=450"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}