Paul's PRPrime Page

[paulunderwood]

I have written a web page which uses javascript to run a psedoprimality test. I have attached it here. Here are some test primes to try

201 digits:

100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000357

1001 digits:

10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000453

For the 1001 digit prime I get the following timings on (one core of) a Q6600:
Firefox 21.0 -- 20 seconds
Chrome 6.0.472.63 -- 60 seconds
Epiphany 2.30.6 -- 75 seconds
Iceweasel 3.15.16 -- over 720 seconds (eats up to 200Mb)

It would be interesting to me to read how well it runs on different versions of Internet Explorer and Safari etc. Does it run on smart phones and tablets?

Feel free to look at the source and make suggestions for improving the code.

Possible future features include tick box options for trial division and a 2-prp test; Under the hood, Barrett modular reduction.

[R.D. Silverman]

Originally Posted by paulunderwood

I have written a web page which uses javascript to run a psedoprimality test.

You are misusing the word pseudoprime.

[paulunderwood]

Originally Posted by R.D. Silverman

You are misusing the word pseudoprime.

You are right. The program does not find composite numbers that pass the test as a likely prime! I would dearly like such an example. I use the word on the same sense as pari-gp's ispseudoprime(). The Prime Pages give this definition of a pseudoprime: "A probable-prime which is composite is called a pseudoprime. (At one time all probable primes were called pseudoprimes, but now the terminology has been corrected.)"

[jcrombie]

Paul, that's an interesting piece of javascript! Thanks!

Here's one test run on an iphone 5, Safari.

p201 -- 2 secs.
p1001 -- 2 mins 27 secs.

[Mini-Geek]

On a US-edition Galaxy S3, Android 4.1 Jelly Bean, testing the p1001 (latest versions of each browser):
Chrome: 75 seconds
stock "Internet": 73 seconds (maybe faster if it hadn't interrupted twice to let me know the page stalled?)
Dolphin Jetpack: 73 seconds

All browsers I tested were surprisingly close to each other, as you can see. And, unsurprisingly, much faster than the iPhone 5 (go Android! ).

Also, on one core of an i5-M450@2.4 GHz, 18 seconds in Chrome 27.

[paulunderwood]

Thanks guys. Keep the tests coming. How about the Internet Explorers and tablets?

I have replaced the final line of "getStrongX" with "return undefined;" and added to "pseudoPrimeTest" after "getStrongX" is called:

  if( x === undefined ) {
    document.inputForm.resultText.value = "Inconclusive: minimal Jacobi Symbol parameter too big. Ed?";
    return 0;
  }

This catch-all will only happen if "x" is really big, which is unlikely. I will endeavor to make "x" unlimited.

Also I think I can squeeze a little more out of the existing code by moving from 14 bit array elements to 15 bit ones.

Obviously, Barrett modular reduction and FFT would speed things up a lot.

[Mini-Geek]

Originally Posted by paulunderwood

Thanks guys. Keep the tests coming. How about the Internet Explorers and tablets?

IE8 on Windows 7: "Not prime because it is a square number." (happens on any input I've tried, except 0 which has its own error telling me to use a non-zero value)

[paulunderwood]

Hmm. Thanks I will look into it (under Wine or Virtualbox).

[Batalov]

Originally Posted by Mini-Geek

IE8 on Windows 7: "Not prime because it is a square number." (happens on any input I've tried, except 0 which has its own error telling me to use a non-zero value)

Seconded; also, on IE9 on Win7. And if we comment out

if( isSquare( binaryString ) ) {
    //document.inputForm.resultText.value = "Not prime because it is a square number.";
    //return 0;
  }

then it falls through to the next message (on any non-zero input):

Result: Not prime because gcd(4*4-4,n)>1

Must be something with IE's Array...'s or whatnot.

[paulunderwood]

Yeah, Internet Explorer needed ".charAt(i)" instead of "[i]" to index strings. (Arrays are fine.) I have made the changes and attached it to this message -- version 0.2.1.

The really annoying thing I found with Internet Explorer 8 (running 32-bit XP under VirtualBox) is that a pop-up keeps happening and one fix I found was to hax the registry of the operating system -- not especially user friendly

What is more I.E.8 was very slow -- 30 seconds for the titchy 201 digit prime. It might run better without VirtualBox.

[Batalov]

Confirmed on both counts: 1) it is fixed, and 2) it is slow in IE (takes ~ a second for a 201-digit prime in IE, a split second in Chrome; and much worse for a 1201-digit prime: 23s in Chrome; too long to see the answer in IE)

Additionally (but needs clean investigation on an empty browser) - IE eats up more memory during the test.