Beta

Slashdot: News for Nerds

×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Schooling Microsoft On Random Browser Selection

kdawson posted more than 4 years ago | from the let-me-show-it-you dept.

Internet Explorer 436

Rob Weir got wind that a Slovakian tech site had been discussing the non-randomness of Microsoft's intended-to-be-random browser choice screen, which went into effect on European Windows 7 systems last week. He did some testing and found that indeed the order in which the five browser choices appear on the selection screen is far from random — though probably not intentionally slanted. He then proceeds to give Microsoft a lesson in random-shuffle algorithms. "This computational problem has been known since the earliest days of computing. There are 5 well-known approaches: 3 good solutions, 1 acceptable solution that is slower than necessary and 1 bad approach that doesn’t really work. Microsoft appears to have picked the bad approach. But I do not believe there is some nefarious intent to this bug. It is more in the nature of a 'naive algorithm,' like the bubble sort, that inexperienced programmers inevitably will fall upon when solving a given problem. I bet if we gave this same problem to 100 freshmen computer science majors, at least 1 of them would make the same mistake. But with education and experience, one learns about these things. And one of the things one learns early on is to reach for Knuth. ... The lesson here is that getting randomness on a computer cannot be left to chance. You cannot just throw Math.random() at a problem and stir the pot and expect good results."

cancel ×

436 comments

BROWZAAAAZ!! (-1, Offtopic)

Anonymous Coward | more than 4 years ago | (#31308086)

EU RULEZ !!!!!

LAST (5, Funny)

DamonHD (794830) | more than 4 years ago | (#31308092)

Hmm, there's a nice shuffle implementation in Java that Microsoft could use... Oh, wait...

Rgds

Damon

damned faintly praising? (0, Offtopic)

Anonymous Coward | more than 4 years ago | (#31308126)

if we gave this same problem to 100 freshmen computer science majors, at least 1 of them would make the same mistake (as Microsoft)

Ouch, that's gotta sting.

Re:damned faintly praising? (0)

Anonymous Coward | more than 4 years ago | (#31308182)

not really. multinational corporations don't feel shame.

this is one of the highest-profile pieces of code microsoft had to come up with, and they fucked it up. we're supposed to believe it was unintentional?

Re:damned faintly praising? (4, Informative)

sopssa (1498795) | more than 4 years ago | (#31308326)

Is picking a worse random number generation function (the default one in C and JS) really fucking up?

And btw, it looks like their choice promotes all other browsers than IE almost 2x more!

Position I.E. Firefox Opera Chrome Safari
1 1304 2099 2132 2595 1870
2 1325 2161 2036 2565 1913
3 1105 2244 1374 3679 1598
4 1232 2248 1916 590 4014
5 5034 1248 2542 571 605

I can already see all the comments how MS would be favoring IE with this (summary conveniently left that one out), but as it is they're promoting the other browsers almost double more.

Re:damned faintly praising? (3, Informative)

GIL_Dude (850471) | more than 4 years ago | (#31308362)

Right; the point of "random" was just that Microsoft didn't PICK the order that the browsers would show up in. For the business purpose required, the solutions selected was adequate and met the requirement. This guy is talking about trying to get highly random stuff like you might need in encryption or quantum physics simulations. While interesting, those higher randomness generators aren't required by the need here.

Re:damned faintly praising? (5, Insightful)

beelsebob (529313) | more than 4 years ago | (#31308586)

No, the point was that no one browser got unfairly pushed to the top all the time. This algorithm does push a certain browser higher more often than not, and hence is not fit for it's job.

Re:damned faintly praising? (5, Insightful)

644bd346996 (1012333) | more than 4 years ago | (#31308594)

Even with a very high quality entropy source, the algorithm Microsoft used will result in a very non-uniform distribution.

Clearly, Microsoft didn't care about this enough to assign one of their experienced coders to it, which is odd given the legal involvement. Either the technical side of MS ignored the legal department's explanation of the importance of the browser ballot to MS's ability to do business on a particularly profitable continent, or someone powerful in MS decided to spite the EU by assigning low quality programmers to the project.

Re:damned faintly praising? (2, Informative)

DamonHD (794830) | more than 4 years ago | (#31308636)

Yes, indeed, you've hit the nail on the head.

A very sloppy shallow unworkmanlike solution to a very high profile legal issue.

Almost as clever as the 'messing up pages shown to Opera' issue, though I suspect that that was deliberate and this not.

Rgds

Damon

Re:damned faintly praising? (4, Insightful)

EvanED (569694) | more than 4 years ago | (#31308368)

Is picking a worse random number generation function (the default one in C and JS) really fucking up?

There's no problem with the function they're using; the problem is how they're using it. If 'rand()' were perfect, their technique would still suck.

I can already see all the comments how MS would be favoring IE with this (summary conveniently left that one out), but as it is they're promoting the other browsers almost double more.

I do think the summary should have mentioned that bias, but I don't think it's quite as good a position as you convey. I bet the far right position is better than #3 and #4 at least.

(If I wanted to put on my conspiracy hat -- which I don't, I don't really believe this -- I'd say that MS wanted to bias it towards them and decided that biasing it toward #1 would be too blatant, but that #5 was "good enough".)

Re:damned faintly praising? (0)

Anonymous Coward | more than 4 years ago | (#31308360)

It won't sting because very few programmers implement effective random selections. Check out your mp3 player on shuffle (iPods are abyssal) or even a random feature when playing CDs in your car. This is something that programmers assume just works, but never actually test.

Re:damned faintly praising? (1)

pelrun (25021) | more than 4 years ago | (#31308524)

Hah! The mp3 shuffle thing isn't a case of poor randomisation - humans just tend to pick a poor definition of random here. Usually people expect "play stuff I haven't heard recently, and in a completely new order that I haven't heard before". True random shuffle will give you songs and orders you've already heard, and your brain is good at picking them up.

Re:damned faintly praising? (1)

donaggie03 (769758) | more than 4 years ago | (#31308588)

True random shuffle will give you songs and orders you've already heard --- just as likely as any other song and order combination. With a decently large selection of music, the chance to randomly pick the exact same song and order combination as one you have recently heard is quite low. In other words, your randomization technique sucks.

Adding randomness... (3, Funny)

Idbar (1034346) | more than 4 years ago | (#31308108)

just requires something like:
pickabrowser() {
if (rand()>0.05) {
use IE
} else {
pickabrowser()
}
}

Nobody said anything about bias.

Re:Adding randomness... (-1, Troll)

Anonymous Coward | more than 4 years ago | (#31308146)

more like

int random =666;
if(int browser = 666)
        showIE();
else
      showElse();

Re:Adding randomness... (4, Funny)

K. S. Kyosuke (729550) | more than 4 years ago | (#31308236)

Exactly, as there is always a chance for you to get a better browser due to a stray alpha particle.

Re:Adding randomness... (1)

DamonHD (794830) | more than 4 years ago | (#31308150)

I think that the EU *might* take a view about that algorithm... %-P

Rgds

Damon

Worthless idea from government... (-1, Troll)

Anonymous Coward | more than 4 years ago | (#31308164)

This is an example of yet another worthless idea from the government. Superficially it may do some good, but ultimately, it just gives another thing to bitch about.

Did they even mandate how the randomness would be implemented? No? What kind of retards were involved in that decision.

Then again, I'm going to bitch at how WOW keeps giving me the same random heroics. Never the ones I want. And the dailies tend to run in strings. DAMN IT I DON'T WANT TO PICK FLOWERS FOR THAT TROLL BITCH!

What's the problem? (3, Insightful)

Anonymous Coward | more than 4 years ago | (#31308172)

What's the problem? It's random enough for a browser selection screen.

This isn't an application where a statistically random shuffle is required.

Re:What's the problem? (2, Funny)

El Lobo (994537) | more than 4 years ago | (#31308224)

Exactly, let's force them solve this problem with a .000000001 floating point precision. After all, this is a critical issue.

Re:What's the problem? (1)

QuoteMstr (55051) | more than 4 years ago | (#31308630)

.000000001 floating point

There's no such thing. That number cannot be represented in IEEE binary floating point.

Re:What's the problem? (1, Informative)

Anonymous Coward | more than 4 years ago | (#31308260)

You are missing the point.

As the author of the article pointed out, this technique can cause an infinite loop.

Re:What's the problem? (0)

Anonymous Coward | more than 4 years ago | (#31308430)

How, exactly?

Re:What's the problem? (5, Funny)

Anonymous Coward | more than 4 years ago | (#31308562)

You are missing the point. As the author of the article pointed out, this technique can cause an infinite loop.

Re:What's the problem? (1)

TerranFury (726743) | more than 4 years ago | (#31308458)

Can it really? I can't come up with an example where this would occur with nonzero probability...

Re:What's the problem? (0)

Anonymous Coward | more than 4 years ago | (#31308618)

Depends on the sorting algorithm. Consider an algorithm which cycles through the array, swapping neighboring numbers which are in the wrong order, until no numbers need to be swapped (Bubble Sort). If the random function by chance returns a value which calls for swapping two elements in the array in every pass, then the algorithm never ends.

Re:What's the problem? (1)

EvanED (569694) | more than 4 years ago | (#31308634)

If the random function by chance returns a value which calls for swapping two elements in the array in every pass, then the algorithm never ends.

The probability that happens is 0.

Re:What's the problem? (3, Insightful)

EvanED (569694) | more than 4 years ago | (#31308526)

As the author of the article pointed out, this technique can cause an infinite loop.

For certain, pretty crappy definitions of "can". First, you'll notice he also points out that that "depends on the sorting algorithm used". I don't think that the most likely choices (Quicksort in particular) fall victim to this. Second, the other poster is right: the probability that it's actually an infinite loop is 0.

He's just bitching (4, Insightful)

Sycraft-fu (314770) | more than 4 years ago | (#31308322)

It is probably a combination of two things:

1) Hate for MS. MS is doing what some have said they've needed to do in giving users browser choice, and they've done so as to try not to promote any given one. While that makes proponents of choice happy, it makes MS haters mad. The more MS does to try and accommodate users and play fair, the less there is to hate on them for legitimately. As such haters are going to try and find nit picks to bitch about.

2) General geek pedantry. Many geeks seem to love to be exceedingly pedantic about every little thing. If a definition isn't 100% perfect, at least in their mind, they jump all over it. I think it is a "Look at how smart I am!" kind of move. They want to show that they noticed that it wasn't 100% perfect and thus show how clever they are.

Doesn't matter, it is what it is and as you said, random enough. This guy can whine all he likes.

Re:He's just bitching (4, Insightful)

magsol (1406749) | more than 4 years ago | (#31308352)

On the other hand, the devil is in the details, and one would think that a company such as Microsoft that has been owning the software market for decades now would know how to implement a randomizing algorithm correctly.

Re:He's just bitching (3, Insightful)

AdmiralXyz (1378985) | more than 4 years ago | (#31308456)

one would think that a company such as Microsoft that has been owning the software market for decades now would know how to implement a randomizing algorithm correctly.

Wrong: a software company such as Microsoft that has been owning the software market for decades now knows how to use programmer time and resources effectively. Spending the extra programmer time and effort to turn a "99.99% random" process into a "100% random" one is an utter waste of both on something this trivial. Hate to break it to you, and to look-at-me-I'm-so-much-smarter-than-evil-Microsoft Rob Weir, but they're not making any mistake here.

Re:He's just bitching (1)

MaskedSlacker (911878) | more than 4 years ago | (#31308542)

To be fair, this is more like 60% random, not 99.99%.

Re:He's just bitching (4, Interesting)

maxwell demon (590494) | more than 4 years ago | (#31308590)

Spending the extra programmer time and effort to turn a "99.99% random" process into a "100% random"

I don't know what you consider "99.99% random", but the difference between 20% (probability of IE turning up last in a real random shuffle) and ca. 50% (probability of IE showing up last in the implemented "random shuffle") is certainly significant enough that you can't call it 99.99% random." You might argue that it is "random enough for this," but that's of course a matter of opinion, and therefore debatable (there's no objective definition of "random enough").

Re:He's just bitching (3, Insightful)

644bd346996 (1012333) | more than 4 years ago | (#31308644)

They made the stupid mistake of not assigning an experienced or well-educated programmer to a project that was necessary for them to legally do business in Europe. Somewhere along the way, the legal department had to have sent the technical managers an email containing a phrase very similar to "don't fuck this up!!", and the manager ignored it and assigned a programmer who didn't go to a good CS school and thus has never heard of a Fisher-Yates shuffle or something equivalent.

It's very understandable that some of Microsoft's programmers are of such low quality. What is odd is that their legal department can't make their technical managers understand "do this right or we lose the right to do business on the second most profitable continent."

Re:He's just bitching (0)

Anonymous Coward | more than 4 years ago | (#31308648)

a software company such as Microsoft that has been owning the software market for decades now knows how to use programmer time and resources effectively.

You'd have hoped so, eh?

What about Windows Vista? Hundreds of man-years of effort and billions of develoment costs down the shitter. Oops!

Microsoft actually has a notiously bad internal culture full in infighting between competing groups.

Re:He's just bitching (1)

magsol (1406749) | more than 4 years ago | (#31308670)

I don't know why you're coming down so hard on this, particularly since you are absolutely correct. My point was that Microsoft knows how to implement a trivial randomization algorithm in a trivial situation (the difference between 60% and 100% random in this situation is not only unobservable unless thousands of iterations are performed, but it's also trivial to close that gap). If they went with a less-random algorithm, it would be far more likely to have been a willful decision instead of an accidental mistake. We're making two different and non-overlapping points.

Re:He's just bitching (4, Insightful)

TerranFury (726743) | more than 4 years ago | (#31308468)

Whatever. They offloaded what looked like a menial task to some low-level programmer, who ran it a few times, saw it was "random" (without doing any statistical tests), and went home happy. He probably should have known the Knuth shuffle algorithm -- I remember studying it in high school CS, even -- but honestly it's not that huge a deal.

Re:He's just bitching (2, Funny)

lennier (44736) | more than 4 years ago | (#31308556)

On the other hand, the devil is in the details, and one would think that a company such as Microsoft that has been owning the software market for decades now would know how to implement a randomizing algorithm correctly.

Sure!

10 RANDOMIZE TIMER
20 PRINT INT(RND * 5)
30 GOTO 20

Re:He's just bitching (2, Insightful)

Short Circuit (52384) | more than 4 years ago | (#31308592)

It's paranoia and naiveté like yours that led me to stop hanging around here so much.

Paranoia in that everything company X does is evil or has an inappropriate or immoral ulterior motive. Naiveté in that you don't stop to recognize that the not all of the developers who work for an institution are going to output code of the caliber of its most senior, experienced and/or knowledgeable developers, nor can code review and automated tests catch all of the problems and gotchas known to computer science, academia and the body of professional programmers.

So can the "the devil is in the details" crap; you don't know what you're talking about. Building a complex software package that takes into account every possible detail in both process and implementation is impossible in any environment currently available for consumer software and general computing hardware. Just when you think you've got everything covered, nature builds a vendor builds a buggy component, security specialists discover a flaw in the way you learned to write your software, nature builds a better idiot, or a piece of a radioactive isotope in a memory module emits a beta particle, just to ruin your day.

Re:He's just bitching (-1, Troll)

Anonymous Coward | more than 4 years ago | (#31308404)

2) General geek pedantry. Many geeks seem to love to be exceedingly pedantic about every little thing. If a definition isn't 100% perfect, at least in their mind, they jump all over it. I think it is a "Look at how smart I am!" kind of move. They want to show that they noticed that it wasn't 100% perfect and thus show how clever they are.

It's because their pathetic little egos are based upon how "smart" they are. Of course there's always someone smarter than you. And even if there isn't someone smarter than you , at least in your field, you're probably a moron in some other. Aside from a couple of groundbreaking physics papers, Einstein was failure - he was a shitty father, husbands and a complete moron when it came to finance.

Also, the moderators here reward pedantry. Wanna a quick karma hit? Post a pedantic comment and +5 Insightful.

Re:He's just bitching (2, Insightful)

DavidShor (928926) | more than 4 years ago | (#31308566)

Did you read the god-damn article? The results are insanely non-uniform. With a sample-size of 10,000 , IE ends up in 5th place 50% of the time. I mean, it's not evil, it doesn't benefit them. But it makes them look insanely dumb.

Re:He's just bitching (0)

Anonymous Coward | more than 4 years ago | (#31308628)

2) General geek pedantry.

I'm all for it. Just could we also go after silly coding in popular Linux distros? Not just to be evenhanded, but to improve the breed.

Given: MS is under a lot of righteous suspicion when it comes to playing fair, and putting this article on /. quashes what would have been heavy rumours that the browser selection was not random. That's good.

Let's just shine the light further. Maybe every other Sunday run a /. post like "What's your current face-palm about distro ____?"

You can't artificially put down competition (5, Insightful)

SuperKendall (25149) | more than 4 years ago | (#31308428)

Here's the problem - consider the results again. Safari will almost always (almost 50% of the time) be put in the bottom two elements. In fact depending on the algorithm used it's 40-50% chance of being put in one exact slot (either choice four or five).

When the whole point of the list is promote browser competition, it makes no sense to accept a list which is that skewed for ANY browser result from the list. You need to have it properly shuffled so that no one browser has a statistical advantage or disadvantage - if you are going to claim it doesn't matter then why not let Microsoft set an arbitrary fixed order for the list?

That is not what the legal injunction against them says they can do, therefore the randomness of the results DO matter. Just as in most things in life, correctness of results is actually important.

Re:You can't artificially put down competition (4, Funny)

pushing-robot (1037830) | more than 4 years ago | (#31308554)

Safari will almost always (almost 50% of the time) be put in the bottom two elements [out of five].

And how well did you do in statistics class?

Re:What's the problem? (1)

ejtttje (673126) | more than 4 years ago | (#31308610)

It's not an academic issue of minor bias: the measurements show that IE winds up in slot 5 with 50% probability. That's hugely biased.

And although some might shrug as the rightmost slot being somehow "bad", there are well known tendencies for people to remember the first and last thing in a list. The point of this whole ballot screen is to even the playing field to avoid this psychology stuff, and they missed the mark. Not to mention how bad it looks that they supposedly hire the best and brightest, but can't code a shuffle properly for a key component of a major lawsuit. WTF.

Cheating at online poker (0, Offtopic)

EvanED (569694) | more than 4 years ago | (#31308174)

There were some folks a while ago who wrote up a security investigation [cigital.com] they did of Party Poker's site.

One of the problems they had was a terrible, non-uniform shuffling algorithm. Completely different problem than what MS did, but interesting nonetheless. (I actually guessed that this is what MS did, but that's not the case.)

Re:Cheating at online poker (1)

EvanED (569694) | more than 4 years ago | (#31308206)

they did of Party Poker's site.

Shit, PlanetPoker, not Party Poker. Sorry.

What? Why not? (-1)

bogaboga (793279) | more than 4 years ago | (#31308176)

You cannot just throw Math.random() at a problem and stir the pot and expect good results."

Let me ask:

Why not? Is the author suggesting that random functions in use today are somewhat deficient? What is his solution?

Re:What? Why not? (5, Insightful)

EvanED (569694) | more than 4 years ago | (#31308226)

Why not? Is the author suggesting that random functions in use today are somewhat deficient? What is his solution?

You know, it's really too bad that the author of the article the summary linked to didn't write up an article answering exactly that. Then maybe Slashdot could have linked to it.

(In a nutshell, the answers are, respectively: "because plopping a 'rand()' into your code doesn't mean that what you'll get out is uniform", "no", and "use a shuffling algorithm that works.")

Re:What? Why not? (1)

maestroX (1061960) | more than 4 years ago | (#31308480)

kdawson obviously skimmed the article for a few seconds and attributed the flaw to Math.random and Microsoft.

Of course, hindsight is always twenty-twenty. We now know a shuffling algorithm should have been used and Microsoft could have evaded prosecution by including a random^H^H^H^H^H^Hshuffled list of browsers for shuffling the list of browsers instead of IE only to run the browser selection process.

Re:What? Why not? (5, Informative)

Tapewolf (1639955) | more than 4 years ago | (#31308264)

I thought it was originally going to be that they forgot to seed the random number generator or something.

What the problem actually seems to be is not that they're using random, but how they're using it.

What they essentially did was use something like qsort() to sort the list, but in their comparator function, instead of returning which of the two strings comes first, they return some random crap instead. qsort() or whatever they used was designed to have results that are consistent, and with input like that it could potentially abort and leave the list entirely unsorted. Or if you're really unlucky it could sit there sorting them forever.

Re:What? Why not? (1)

Lehk228 (705449) | more than 4 years ago | (#31308346)

i'm trying to figure out why they went to the trouble of screwing things up as bad as they did, a trivial decrementing for loop pulling randomInt(1,i) and placing it in slot 5-i would be the obvious off the top of the head solution, and it would work.

Re:What? Why not? (1)

maxwell demon (590494) | more than 4 years ago | (#31308484)

i'm trying to figure out why they went to the trouble of screwing things up as bad as they did, a trivial decrementing for loop pulling randomInt(1,i) and placing it in slot 5-i would be the obvious off the top of the head solution, and it would work.

No, it wouldn't work. Here's a possible run of that algorithm:

Initial:
a = -----
Step 1: randomInt(1,5) -> 3
a = ----3
Step 2: randomInt(1,4) -> 1
a = ---13
Step 3: randomInt(1,3) -> 2
a = --213
Step 4: randomInt(1,2) -> 1
a = -1213
Step 5: randomInt(1,1) -> 1
a = 11213

Doesn't look like a random shuffle. Indeed, it doesn't even look like a shuffle at all.

Indeed, your algorithm has the following properties:

  • always a[0] == 1
  • the only possible result where all 5 numbers occur (i.e. the only result where the result is a permutation of the numbers from 1 to 5) is a == {1, 2, 3, 4, 5}
  • the only place where 5 could be is a[4]

Interesting that random compare is not random... (1)

SuperKendall (25149) | more than 4 years ago | (#31308358)

What they essentially did was use something like qsort() to sort the list, but in their comparator function, instead of returning which of the two strings comes first, they return some random crap instead.

That algorithm seems really wrong, for the reason you mentioned - that potentially you get an infinite loop.

However after further thought, I don't think that result is possible, and I find it more interesting to think about why this does not work as intended. After all, if you are randomly comparing random numbers why is the end result not still random?

First, why it is not going to ever result in an infinite loop - because pretty much any sorting algorithm is not going to engage in an infinite number of comparisons. Pretty much any technique I can think of is always going to be left with an assumption about a growing number of elements and where they fit into place, so even though the comparison result is totally random the sort will always complete (the results will just always be wrong, if you can call any ordering based on a broken comparator wrong).

I think that the non-randomness of the result is related, in that that assumption is made as to where a value falls and then the remaining elements fall into line after that result... which might explain how one element like Safari was so out of whack when the others were also out of balance but to a lesser degree, as the initial list is probably always fed in the same order and the algorithm works on one particular element first to start the sort (which might also explain the browser variation, having slightly different sorting algorithms).

Re:What? Why not? (1)

Animaether (411575) | more than 4 years ago | (#31308438)

I thought it was originally going to be that they forgot to seed the random number generator or something.

Out of curiosity - why would they need to seed the random number generator?

Wouldn't -not- seeding it be better? That way MS don't have to include some seed number in their script and have everybody thinking they're manipulating the results by using seed numbers that they know would generate a certain ordering in various versions of IE.

I actually found this bit...

Repeating the same test on Firefox is also non-random, but in a different way:

...rather interesting. How are two browsers using the same script resulting in different ways of being non-random; presuming that, in itself, was not by chance?

Although I can't verify this, as the test page provided... http://www.robweir.com/blog/shuffle.html [robweir.com] ...won't actually run in IE8 here :D

That said.. odd method of getting random results out of an array.. I'm sure it's more efficient but KISS would dictate you grab one random result out of the array, delete the one you chose, pick a new one, delete, etc. until the array is down to 1 and you stick that last one at the end. Can't really go wrong with that unless the random number generator itself is hosed, and even non-mathematicians can understand how that one works. It's not like it's a high-performance application.

Re:What? Why not? (2, Informative)

Tapewolf (1639955) | more than 4 years ago | (#31308506)

Out of curiosity - why would they need to seed the random number generator?

Wouldn't -not- seeding it be better?

I can't speak for Javascript but in most C libraries - at least in the DOS era when I last made this mistake - the library would default to a static seed of its own during program initialisation, probably 0 or something.

As a result, if you made a program that started, output 15 random numbers and then quit, each time you ran it you would get the same 15 numbers.
What you're supposed to do to avoid that is seed the RNG at the program start, using the current time since the epoch as the seed. This is what I was referring to, not using a static seed :P

Re:What? Why not? (1)

Animaether (411575) | more than 4 years ago | (#31308642)

I can't speak for Javascript but in most C libraries - at least in the DOS era when I last made this mistake - the library would default to a static seed of its own during program initialisation, probably 0 or something.

A-ha... crystal clear - thanks for clarifying :)

Just to check - IE8 certainly seems to do this - whether it does it properly, I wouldn't know, but it's certainly not the same results each time I fire up IE8 with a test page (just printing out 10 random numbers).

This is what I was referring to, not using a static seed :P

Certainly not ;) But if MS were to seed the number, they'd still have to get that seed out of somewhere.. though I suppose they could use javascript date/time functions for that.

Re:What? Why not? (5, Insightful)

Anonymous Coward | more than 4 years ago | (#31308354)

No, Math.random is not the problem, the problem is how it is used. They used it as random input to a sorting algorithm without considering how the sorting algorithm works. The assumption that any sorting algorithm with inconsistently random input = random order is wrong. If they had assigned a random value to each element and sorted by that value the result would have been truly random as the value associated with each element would have been consistent.

Yeah right (2, Insightful)

CSHARP123 (904951) | more than 4 years ago | (#31308184)

Showing a browser selection has been imposed on them and these geeks think MS is going to select the best approach possible for randomness. No wonder none of you are sucess in business.

Re:Yeah right (1)

TerranFury (726743) | more than 4 years ago | (#31308488)

1 - You didn't read the article, did you?

2 - Although their method for generating uniformly-random permutations is incorrect, they are doing nothing to favor IE.

Re:Yeah right (1)

girlintraining (1395911) | more than 4 years ago | (#31308490)

Showing a browser selection has been imposed on them and these geeks think MS is going to select the best approach possible for randomness.

I don't believe many of them think that, judging by the comments so far. I think they're incredulous that a multibillion dollar company that has been developing software since the dawn of the information era managed to screw up a rather basic computer science problem. Given a lack of indication as to motive, they've decided to jump to whatever conclusion fits their personal biases best, which is what happens in every argument when there aren't enough facts to conduct a proper analysis.

Just because you've got a forum full of people who spend their days working with machines that answer everything with either 1 or 0, doesn't mean they've learned anything from the interaction and incorporated it into their own thought processes.

Re:Yeah right (1)

CSHARP123 (904951) | more than 4 years ago | (#31308530)

You don;t need perfect solution for every problem is what I am saying. Thats just waste of time. A geek is the only one who will try for that not a successful business.

Good enough (1, Insightful)

TBoon (1381891) | more than 4 years ago | (#31308194)

Given that each user is only going to see this screen once per computer, I'd say simply using the seconds of the current minute as a random seed should be OK. Can't see why you would need more randomness that that in this particular situation. Just make sure that the distribution of browsers evens out for all seeds...

Re:Good enough (4, Informative)

EvanED (569694) | more than 4 years ago | (#31308242)

Given that each user is only going to see this screen once per computer, I'd say simply using the seconds of the current minute as a random seed should be OK

This problem has nothing to do with how the PRNG is seeded.

The word "seed" doesn't even appear in TFA at all.

Re:Good enough (0)

Anonymous Coward | more than 4 years ago | (#31308282)

*woosh*

Re:Good enough (0)

Anonymous Coward | more than 4 years ago | (#31308302)

*woosh*

Re:Good enough (4, Insightful)

mangu (126918) | more than 4 years ago | (#31308366)

Given that each user is only going to see this screen once per computer

Given that each person will only lose one cent per lifetime, I propose to move $0.01 from each bank account in the world to my own account.

Re:Good enough (1, Funny)

Anonymous Coward | more than 4 years ago | (#31308396)

Given that each user is only going to see this screen once per computer

Given that each person will only lose one cent per lifetime, I propose to move $0.01 from each bank account in the world to my own account.

That must be the most accurate and incredible insightful analogy to the issue at hand I've ever seen that doesn't involve cars.

Re:Good enough (1)

maxume (22995) | more than 4 years ago | (#31308580)

The interesting thing there is that it would only be a great deal of money, you wouldn't be particularly wealthy (in a relative sense).

Read the results, not good enough (2, Insightful)

SuperKendall (25149) | more than 4 years ago | (#31308380)

Given that each user is only going to see this screen once per computer, I'd say simply using the seconds of the current minute as a random seed should be OK.

A) That was not the problem.

B) Consider the result instead of the algorithm is it OK to have your "random" list just about always present any one choice in the bottom two elements? Because that is what happened for Safari.

If you aren't going to insist on a list that's even close to random then you should not make randomness a requirement.

Re:Good enough (1)

mattack2 (1165421) | more than 4 years ago | (#31308622)

Given that each user is only going to see this screen once per computer,

Tangential question (not nitpicking) - isn't it really once per user? Those of us that actually use multiple users may have to answer it multiple times. (I'm on OS X, but I'm still curious.)

Milliseconds (2, Interesting)

Lord Lode (1290856) | more than 4 years ago | (#31308220)

They could as well just have used the last millisecond to show the browser. I mean, it's a screen shown only once to a user. What's more random, and uniform, than the time the screen appears in milliseconds modulo 5?

Re:Milliseconds (2, Informative)

SpinyNorman (33776) | more than 4 years ago | (#31308444)

It's not an issue of how to get a truly random number, or of seeding a random number generator, but rather how to you use a source of random numbers to randomly order a list.

Some "reasonable sounding" methods don't actually work - e.g. attach random numbers to each list item and sort the list by these numbers (1). Microsoft used a similar method of sorting using a random comparator.

Some simple methods that DO work are picking a random permutation or executing a bunch of random swap operations on the list.

(1) http://okmij.org/ftp/Haskell/perfect-shuffle.txt [okmij.org]

Re:Milliseconds (1)

Jorl17 (1716772) | more than 4 years ago | (#31308656)

That'd be the same problem! The thing is not the randomness of the number but how they use it!

I have been fired for less. (0, Troll)

bezenek (958723) | more than 4 years ago | (#31308252)

People like the higher-ups at Microsoft (or most companies, I believe) do not care or want to hear about these issues.

If it does not involve a bonus (for the executive) or making them look good (the executive), engineers have to shut up and smile.

-Todd

p.s. Of course, this is my opinion--not what I would do, and it goes against good ethics. But, who in Silicon Valley cares about ethics? :-|

The top hit on Google... (5, Interesting)

jmtpi (17834) | more than 4 years ago | (#31308258)

A Google search on:

javascript array sort

gives exactly the bogus answer that Microsoft used in the top hit. [javascriptkit.com]
Unfortunately for Microsoft, a bing search gives the same top hit.

Microsoft problem solving (1, Funny)

gmuslera (3436) | more than 4 years ago | (#31308270)

There are 5 well-known approaches: 3 good solutions, 1 acceptable solution that is slower than necessary and 1 bad approach that doesn’t really work. Microsoft appears to have picked the bad approach.

We are still talking here about the random selection of browsers, or something more broad?

Re:Microsoft problem solving (0)

Anonymous Coward | more than 4 years ago | (#31308374)

It's talking about algorithms for creating a random permutation.

Another common example of this problem is creating a fair shuffle of a pack of cards. If your poker machine is going to pass the gaming board, it's going to have to do it correctly...

Amateurs... (0)

Anonymous Coward | more than 4 years ago | (#31308274)

...they should ask the Debian folks.

random number generator (0)

Anonymous Coward | more than 4 years ago | (#31308290)

... nine nine nine nine nine nine ...

http://dilbert.com/strips/comic/2001-10-25/

Um, yeah (0, Troll)

oldhack (1037484) | more than 4 years ago | (#31308296)

Microsoft was so grateful, because Microsoft cares.

I'm sure it's deliberate (0, Flamebait)

david_craig (892495) | more than 4 years ago | (#31308328)

"But I do not believe there is some nefarious intent to this bug"

The article states that IE is more likely than any other browser to appear at the bottom of the list. To me, this is one of two optimal positions (top or bottom being easiest to pick out).

Microsoft is so well known for dirty tricks I'm sure that this is not an accident

Re:I'm sure it's deliberate (0)

Anonymous Coward | more than 4 years ago | (#31308508)

"But I do not believe there is some nefarious intent to this bug"

The article states that IE is more likely than any other browser to appear at the bottom of the list. To me, this is one of two optimal positions (top or bottom being easiest to pick out).

Microsoft is so well known for dirty tricks I'm sure that this is not an accident

I've been involved in a lot of real life testing of web user interfaces, placements of buttons/options, which get the most clicks, etc. Some quite close to this. And the numbers are overwhelming for the first choice in a line-up like this crushing the others in the distribution of choice. And according to these numbers, Chrome is twice as often in the first position as IE. This is most definitely not the result of some nefarious plan, unless that plan is to buy Google afterwards,

do not fix! (1)

orta (786013) | more than 4 years ago | (#31308330)

looking at the outcome IE comes off the worst with the current algorithm, please keep it that way. Thanks from all the Web Developers.

Re:do not fix! (3, Interesting)

jonbryce (703250) | more than 4 years ago | (#31308538)

I don't think it comes off worst at all. People usually look towards the right of the screen for the "go away and stop bugging me" button, and that's where Internet Explorer is 50% of the time.

Remember that the yellow exclamation mark in the system tray telling people they need to reboot is an annoyance when they just want to get on with their work. Then when the computer finally does reboot and they really really want to start doing whatever it was they turned on the computer to do, they get this annoying thing about web browsers.

Re:do not fix! (1, Insightful)

Anonymous Coward | more than 4 years ago | (#31308602)

looking at the outcome IE comes off the worst with the current algorithm, please keep it that way. Thanks from all the Web Developers.

Exactly. And the Apple people here managing to interpret this as a plot against Safari are just amazing. MS would represent IE the worst, and Chrome and Firefox the best, just to get Safari. Yeah, right. Talk about delusions of grandeur.

I have no problem with this at all (1, Informative)

Zocalo (252965) | more than 4 years ago | (#31308348)

Frankly, I have no problem with this result. Quite the opposite in fact, since I think you can probably group the users into three sets, only one of which really matters in connection with the Browser Selection Screen:
  1. Those that equate "Internet" with a blue "e" and as such will pick IE regardless of its position
  2. Those that prefer another browser to IE and will pick another option regardless of positioning
  3. Those that have no clue about browsers and pick essentially at random, or belong to one of the above groups and click in error.

The only people where the selection and any possible bias inherent in the implementation of the random() function are the last group, which is also quite possibly the smallest of the three sets. In an ideal world, you are going to get a bellcurve with the optimum position being in the middle and the least favourable at the sides, so if Microsoft wants to implement random() so that IE is more likely to end up in the position that is joint least likely to be picked of the big five browsers, that's fine by me.

It's also apparently fine for Google's Chrome as well, so if you are anywhere near Ballmer's office in the next few days then I'd keep an eye out for any flying chairs, just in case...

Re:I have no problem with this at all (1)

westlake (615356) | more than 4 years ago | (#31308504)

3 Those that have no clue about browsers and pick essentially at random, or belong to one of the above groups and click in error.

It won't be a random choice.

They will choose the browser associated with their operating system:

Microsoft Windows = Microsoft IE 8 for Windows.

The only people where the selection and any possible bias inherent in the implementation of the random() function are the last group, which is also quite possibly the smallest of the three sets.

It is more likely the largest of the three sets.

These aren't geeks shopping for tech, these are ordinary people looking for a familiar and trusted brand name.

The ballot is a bureaucratic perversity that will play to Microsoft's advantage.

Re:I have no problem with this at all (1)

jonbryce (703250) | more than 4 years ago | (#31308540)

Those who prefer another browser to IE will have already installed one, and they won't see this screen.

Seems like the right solution to me (2, Insightful)

kevinNCSU (1531307) | more than 4 years ago | (#31308388)

One solutions takes 3 seconds, can be done by an intern, and makes the company no money. The other solution takes a little bit of time, maybe some reading or prior knowledge and still makes the company no money. The results yielded for each solution are acceptable for the situation. Given the cost to profit it seems like Microsoft chose EXACTLY the right solution.

This is like your community telling you that you must have a fenced in yard for your dog to be off the leash and then setting up a cheap 6-foot standard wooden fence and then the local anti government militia guy laughing at your ignorance because everyone who knows anything about fences knows you choose the solution that's 12 feet high with curved top to prevent climbing and a sunken base of 3 feet to prevent dog-tunneling.

Re:Seems like the right solution to me (1)

SpinyNorman (33776) | more than 4 years ago | (#31308578)

Well, as it happens (if you read TFA) Microsoft's solution ends up being biased against Microsoft rather than for them. It hard to say which is worse, though; in one case you work against your own market share, in the other you end up wasting time and money as the EU hauls you back in court for unfair practices.

It seems the least cost option for Microsoft would have been to have gotten this right first time (as is always the case with software).

Bug in the story (1)

tomhudson (43916) | more than 4 years ago | (#31308442)

Microsoft used none of these well-known solutions in their random solution. Instead they fell for the well-known trap. What they did is sort the array, but with a custom-defined comparison function. JavaScript, like many other programming languages, allows a custom comparator function to be specified. In the case of JavaScript, this function takes two indexes into the value array and returns a value which is:

  • < 0 if the value at the first index should be sorted before the value at the second index
  • 0 if the values at the first index and the second index are equal, which is to say you are indifferent as to what order they are sorted
  • < 0 if the value at the first index should be sorted after the value at the second index

According to the description, it returns either 0 or < 0.

That's not the way the comparator function works in any implementation I've seen. Hopefully, the test code the author wrote wasn't as random as the documentation.

Jesus Fucking Christ (-1, Flamebait)

Anonymous Coward | more than 4 years ago | (#31308450)

Who gives a flying fuck? This isn't dealing with nuclear missile codes or quantum cryptography; it's a fucking browser selection screen. If a naive random selection implementation is the best criticism you can come up with then they must have done a good job. This is why people don't take you freetards seriously.

Re:Jesus Fucking Christ (0)

Anonymous Coward | more than 4 years ago | (#31308532)

This is why people don't take you freetards seriously.

People don't take us seriously because we think that software should be implemented correctly, and that the programmers employed by the world's most successful software company should know trivial algorithms? Ri-i-i-ight.

Simple solution (0)

Anonymous Coward | more than 4 years ago | (#31308460)

Excel formula:

=ROUND(RAND(),1)*10 .
This works for up to 11 different browsers (yes, 0 is a number).

Random (3, Funny)

Greyfox (87712) | more than 4 years ago | (#31308552)

I like this [xkcd.com] one.

Anywhoo... So what you're telling me is that Microsoft's programmers made a mistake for a production system that 99% of freshmen CS students wouldn't make? In this case, I think you're actually giving too much credit to Freshman CS students...

On the up side: it's a webpage. On the down side: (1)

Animaether (411575) | more than 4 years ago | (#31308560)

On the down side.. it's a webpage.

To cover the first bit.. it's a webpage - if a potential problem has been found, it can be fixed. I.e. this random selection thing? They can implement a better one.

Though I do wish they would start by fixing the page's use of javascript to sort the results -after- their display.
Turn off Javascript.. the order appears to always be: IE, FF, Opera, Chrome, Safari.

In fact - if you have a slow machine like I do.. leave javascript on, and just refresh the page.. look closely, and you'll find that -that- is the order of display *before* it gets shuffled by the javascript.

On the down side... if they were to detect the user not using javascript, and would switch server side-shuffled results instead, people would wonder how fair -those- are.. and since they can't peek inside the server, there's no way to tell.

Which leads to another down side... it's on a server out of our control - it's entirely possible, albeit unlikely, that one out of N hits favors browser X by design.

note: I don't really care much.. I don't think this should have been pushed through at all. But if they -have- to do it, I'd rather they do it well, just because it would have prevented the flurry of articles on this and other issues (such as the rollout not being instant, but stretched out through April(?) - probably to keep media attention / panicked users calling their tech support to a minimum), even in times to come.

Might be a mistake but not where Rob is pointing (1)

ma_luen (798746) | more than 4 years ago | (#31308604)

Well unless there is something else going on Rob needs to go back to school too. A simple quicksort algorithm with the comparator replaced with a random choice becomes a recursive random partition of the array. A simple inductive argument shows that this will not produce the unbalanced results he found. So the problem is elsewhere (most likely in the RNG seeding or a bias in the pivot selection, if he is running it in a tight loop and the seed is something like, current second, then the same seed may appear several times).

I am amazed... (-1, Troll)

ei4anb (625481) | more than 4 years ago | (#31308658)

by the number of people who say the MS solution was "good enough". MS has been making "good enough" software for many years and that is what has given us an unending series of vulnerabilities.

The only true random function (1)

Jorl17 (1716772) | more than 4 years ago | (#31308662)

There's only ONE trully random-compliant function: http://xkcd.com/221/ [xkcd.com]

I use it everyday. Funny, though, 4 turned out to be my good-luck number since I started using it...
Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Create a Slashdot Account

Loading...