6 billion names

How does one calculate over 6 billion names using the letters from a single name, how long would such a feat take, and why does one even going about do such a thing? Read on to find out. 😀

Spoiler alert! 6 billion names are how many alternate JimbobJeffers mathematically exist.

On the evening of 13 November, a member of Rock Raiders United was joking how the lead administrator should have some code that randomizes the spelling of his name, with a new spelling appearing upon every page load. Since such a task would be best accomplished client-side using JavaScript, I wrote up some code that did just that.

(gist.github.com/le717/4c2188ca814f56575a26)

The above code loops through each character of the entered name, randomly picks a letter and concatenates it to the existing string. It also ensures it does not use the same letter twice unless it already exists. I have checked each output for my name, “le717”, and every single one only has two sevens in it, never three. The trick is not checking for the character used, but the index chosen. If the index has been used before, then it will choose a different one. Since the sevens have two different indexes (3 and 5), they are both included and a third is never added. The administrator liked the idea, so he and I worked together to get it implemented.

The next morning, most all the active members had already seen the name scrambling and either loved it or hated it. For fun, I decided to run it on a few names on my end and see the results. One member’s name in particular, JimbobJeffers, produced some really scrambled names. He wondered if it were possible for the code to generate a name containing “Bobjim”. Since I knew it would be a trivial bit of code to write, I said I would try it.

I started by calculating the possible permutations of his name using factorials. His name is 13 characters long, producing a possible 6,227,020,800 (six billion, two hundred twenty-seven million, twenty thousand, eight hundred) combinations. ❗ I then found some JavaScript to calculate that number for me (I did not want to type it in manually) (although I should know how to write code to calculate the factorial already 😄 ). Because he wanted to see if any of them contained “Bobjim”, I made it store any names that matched in an object along with its index. Finally, once it had generated and checked all 6 billion names, it would either display the object or report such a combination does not exist, depending on the outcome. After some small-scale tests to ensure the code worked, making his name and check all lowercase to remove possible misses because of case differences, and a false start in order to implement a 100-increment progress counter, around 10:22 AM I let the code loose, powered by none other than the awesome Node.js.

The progress of this code was amazing. While I failed to check the processing speed after I started it, I later started calculating the speed (names processed at the 10 second, 1 minute, and 1 hour levels), current number of names processed, and projected time until completion. A mere 10 minutes after starting, an amazing 64 million names had already been processed. That is a rate of 6.4 million a minute, or roughly 106 thousand a second! 40 minutes after starting, when I formally starting performing logs, I clocked it at 6 million names a minute, or 36 million names an hour. Within an hour, 419 million names had been run, with a projected 15 hours until all 6 billion were processed looking, or 2 AM the next morning. Yikes. I knew it would take a long time, but not that long. 😛

After that, it slowed down drastically. Two hours after starting, it ran at only 54,000 names a minute, or 3,240,000 names an hour, an 11-fold decrease. Within that time, a staggering 419,159,500 names had been generated.

Finally, nearly 4 and a half hours and a CPU priority increase to High (in an attempt to make it run faster) later, it chugged along at 13,000 names an hour, with a projected 49 years remaining for it to calculate the remaining 5,807,484,800 names. Yup, that is totally happening. 😛

At last I killed the code, having processed 419,750,000 names in a few minutes shy of running for 5 hours.

419,750,000 names generated

So, what did I learn from this experiment?

  1. JavaScript, like any other language, slows down the longer it runs.
  2. 6 billion is a lot larger number than you might think. 😛
  3. I brushed up on my factorial and permutation knowledge.
  4. I had fun doing it.
  5. Does there exist an alternate JimbobJeffers that goes under the name “Bobjim”? The world may never know.

In case you wanted to try this experiment yourself, I have posted the code used in a GitHub Gist. This was not the most scientific experiment ever, so there may be some flaws in it, but that’s not the point here. 😛


Well that was fun, perhaps a bit too much fun. 😛 Perhaps I should try to calculate the meaning of life next, as another member suggested. After all, if I can get it to run at an constant rate, which ideally is the rate it starts at, such a calculation should “only take a month”. 😛
-le717

Advertisements

6 thoughts on “6 billion names

  1. I just added “break;” after line 59, and the code finished with “jreffbobjimes” after 1248 iterations (run straight on JSFiddle!).

    if (name.indexOf(“bobjim”) > -1) {
    wanted[i] = name;
    break;
    }

    By my (possibly flawed) calculations, it would take on average 19,387,894,021,813,846,000 tries to guess every possible combination by random. You would want to optimize your JavaScript a bit before running that many iterations!

    I suppose you realize (or else I am reading the code wrong) that there is no check to make sure there are no name repeats, hence they become inevitable, meaning if it ever did finish, it would not have checked every possible name.

    1. And… I got that number wrong. Should be 144,027,127,350.0462 I think.

      for(var i = 1; i <= 6,227,020,800; i++){
      total_guesses += names / i;
      }

      I could have that logic wrong though (as I did last time). As for the 49 years… that's a rate of just over 4 names per second, which seems ridiculously slow. Any idea why it slowed down SO MUCH? I wasn't aware that code slowed down over time. In fact, Java generally speeds up (because frequently used code doesn't keep getting translated to machine code).

    2. Ha! I had no idea “bobjim” would come up that soon! As running on JSFiddle too? Wasn’t expecting that!
      After performing this experiment, I discovered my code was actually flawed in generating the random name. Shh. 😛
      Yes, I should optimize my JavaScript, but I did not expect it to every complete, so I really didn’t. 😛
      Yes, I am aware there is no name repeat check, and later on I did discover repeats were coming up in that code (though I do not directly know about when this was running, but I imagine so). I kinda wanted to see all the possible “bobjim” names, and not just the first instance.

      (I’ll just answer both comments here, if that is OK.)

      I am really not totally sure why it slowed down, but I can imagine it was 1. from it filling up the wanted object with however many names it found and the sheer amount of processing it was doing. This could have been considering a stress test if you look at it like that. I do not think any JS interpreter compiles JavaScript to machine code, because if it did, then by now loading jQuery from CDNs would not have as much performance hit as it sometimes has. 😛

Triangular Reactions

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s