Industrial Strength Left-truncated Prime Checker

I saw a post on Facebook about left-truncatable prime numbers.  A left-truncatable prime number is a prime number that is still prime with each successive removal of its left-most digit.  For example, 137 is a left-truncatable prime number because 137 is prime and, when you remove the left-most digit, 1, the remaining number, 37, is still prime, and so is 7 after you remove the 3.

I got it in my head that this would be fun to write a script for.  Because I hate myself immeasurably I wrote it in JavaScript.  Let’s break down the problem a little bit to get an idea of how I approached it.

What do we need?  We need:

  1. An algorithm for checking if a number is prime.
  2. A way to remove the left-most digit from the number so the new number can be checked for primeness (I put 1 and 2 together in the same function because laziness).
  3. Assuming we do check large numbers, we ought to be nice to users and figure out a way to handle the checking in a non-blocking way (more below).
  4. We need to know JavaScript’s limitations on numbers (because, of course, the only interesting primes are big, right?) and check the input against them.

In my posts I’m usually pretty light on the walk-throughs and this post will be no different.  Check the comments in the code.  Let’s get right to it.

1) and 2) an algorithm for checking if a number is prime while successively removing its left-most digit:

<script type="text/js-worker">
  // This script WON'T be parsed by JS engines because its MIME type is text/js-worker.
  var prefix = 'The number ';
  var evenSuffix = ' is even so it\'s not prime.';
  var primeSuffix = ' is prime!';
  var notSuffix = ' is not prime!';
  var divSuffix = ' is not prime because it\'s divisible by ';
  
	onmessage = function(tneve) {
    var num = tneve.data;
    console.log('inside WEB WORKER!', num);
    for (var i = 0; i < num.length; i++) {
      var truncatedNumStr = num.slice(i,num.length);
      var truncatedNum = parseInt(truncatedNumStr);

      if ((truncatedNum % 2 === 0) && (truncatedNum !== 2)) {
        return postMessage(prefix + truncatedNumStr + evenSuffix + ',true');
      }

      if (truncatedNum === 1) {
        return postMessage(truncatedNumStr + notSuffix + ',true');
      }

      for (var j = 3; j <= ((truncatedNum/2)+1); j++) {
        if (truncatedNum % j === 0) {
          return postMessage(prefix + truncatedNumStr + divSuffix + j + '.,true');
        }

        if (j >= (truncatedNum/2)) {
          postMessage(truncatedNumStr + primeSuffix + ',false');
        }
      }

      if (i === num.length-1) {
        return postMessage(prefix + ' ' + num + ' is a truncatable prime!,true');
      }
    }
  };
</script>

The first thing that might stand out to you is that this is an odd script in script tags and that postMessage is being used.  Usually, postMessage is for passing messages between windows and across origins.  In this case, we are using a web worker and so we need to pass data between the parent window and the web worker.  PostMessage can be used for passing data to and from iframes as well, which I’ve done for third-party widgets.

3) Which brings us to the web worker:

The web worker is being used for one specific reason: we don’t want those sweet sweet for-loops to block our browser tab.  JavaScript is single-threaded so if you give it something that is computationally costly, like checking if a large number is prime and if each truncated number within it is also prime, then your script will block the window, or browser tab, meaning the user won’t be able to do anything like click on buttons and what not.  Not really a big deal for a little script whose sole purpose is to do this specific computation, but it can still be unsettling for a user to essentially have a frozen tab.  Is it working?  I typed a number and pressed the button, but now it’s frozen!  My beautiful messages and artistic animations would do nothing until the whole thing was done.  So we order up a web worker which the browser graciously treats separately from the current thread meaning it will not block our browser tab.

Anyway, that link to web workers is where I got the example for embedded web workers.  That’s what my example code is, an embedded web worker.  It’s a nifty trick in a pinch when you can’t serve a JavaScript file.

4) Other JavaScript limits:

Ok, so we’ve got an algorithm for checking primeness which also left-truncates using a slice and we created a web worker so we can show off while a separate thread actually does the computation, but how long will the computation really take?  Can I input anything at all?

Well, let’s start with JavaScript’s idea of a safe integer.  Basically, JavaScript has a limit for number accuracy which is the maximum safe integer.  Beyond that point you’ll get numbers in an inaccurate notation (actually, it’s more complicated than that: numbers beyond the maximum won’t compare correctly).   For example, if the maximum safe integer is 9007199254740991 and you multiply it by 9999999999999, as you typically would, then you’d end up with this value: 9.00719925474009e+28.  Not so great for checking left-truncatable primeness.  If you follow those links to safe integer info you’ll see how to check if an integer is safe and all the mathematical goodness underlying it.

But you may have realized that the maximum safe integer is actually beside the point.  2^53 – 1 is actually really big to be running nested for-loops on.  Like really really big.  Like will take you years to compute with your shitty laptop’s quad-core cpu.  Like around 3 years.  Ok, I don’t know if my calculation is accurate.  I’m a high-level programmer, web developer, who usually doesn’t need to devise efficient algorithms with estimates of complexity.  That said, this is how I notify the user of how long it might take to compute their desired input for left-truncatable primeness:

// check your perf, mister
var perf = function(number, callback) {
	if (legitimizer(parseInt(number), callback)) {
    var numStr = number;
    var count = 0;
    var jsSteps = 0;
    var time = 0;
    var units = ' minutes ';

    while(number.length > count) {
      numStr = number.slice(count,number.length);
      jsSteps = parseInt(numStr) + jsSteps;
      count++;
    }

    time = ((jsSteps * number.length * 5) / 1800000000) / 60;
    if (time > 60) {
      time = time / 60;
      units = ' hours ';
      if (time > 24) {
        time = time / 24;
        units = ' days ';
      }
    } 

    return callback('The number ' + number + ' could take ' + jsSteps + ' steps which if you have a single 1.8GHz CPU could take ' + time.toFixed(11) + units + 'to compute truncation.', true, null, true);
	}
};

Anyway, as mentioned above here’s the thing in action.  I may have exaggerated a bit on how beautiful and exciting it is.

 

Advertisements

Leave a Reply

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