mersenneforum.org Paul's PRPrime Page
 Register FAQ Search Today's Posts Mark Forums Read

2013-05-21, 15:48   #1
paulunderwood

Sep 2002
Database er0rr

102348 Posts
Paul's PRPrime Page

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:
Code:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000357
1001 digits:
Code:
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.
Attached Files
 paulspseudoprimepage.html.zip (4.1 KB, 218 views)

2013-05-21, 18:04   #2
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

11101001010002 Posts

Quote:
 Originally Posted by paulunderwood I have written a web page which uses javascript to run a psedoprimality test.
You are misusing the word pseudoprime.

2013-05-21, 18:21   #3
paulunderwood

Sep 2002
Database er0rr

22·1,063 Posts

Quote:
 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.)"

 2013-05-22, 17:23 #4 jcrombie     "Jonathan" Jul 2010 In a tangled web... D716 Posts 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.
 2013-05-22, 19:17 #5 Mini-Geek Account Deleted     "Tim Sorbera" Aug 2006 San Antonio, TX USA 2×3×23×31 Posts 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. Last fiddled with by Mini-Geek on 2013-05-22 at 19:20
 2013-05-22, 20:18 #6 paulunderwood     Sep 2002 Database er0rr 102348 Posts 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: Code:  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. Last fiddled with by paulunderwood on 2013-05-22 at 20:21
2013-05-22, 20:22   #7
Mini-Geek
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

2·3·23·31 Posts

Quote:
 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)

Last fiddled with by Mini-Geek on 2013-05-22 at 20:23

 2013-05-22, 20:26 #8 paulunderwood     Sep 2002 Database er0rr 109C16 Posts Hmm. Thanks I will look into it (under Wine or Virtualbox). Last fiddled with by paulunderwood on 2013-05-22 at 20:26
2013-05-23, 00:27   #9
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

9,901 Posts

Quote:
 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
Code:
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):
Code:
Result: Not prime because gcd(4*4-4,n)>1
Must be something with IE's Array...'s or whatnot.

Last fiddled with by Batalov on 2013-05-23 at 00:35

2013-05-23, 01:10   #10
paulunderwood

Sep 2002
Database er0rr

22×1,063 Posts

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.
Attached Files
 paulspseudoprimepage.html.zip (4.2 KB, 213 views)

 2013-05-23, 01:26 #11 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 26AD16 Posts 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. Last fiddled with by Batalov on 2013-05-23 at 01:29

 Similar Threads Thread Thread Starter Forum Replies Last Post jasonp Operation Kibibit 1 2017-09-07 19:54 diep Lounge 3 2009-12-18 12:25 kar_bon Riesel Prime Search 144 2008-10-21 10:27 OmbooHankvald 15k Search 2 2005-08-02 14:53 ixfd64 Lounge 2 2004-02-18 09:42

All times are UTC. The time now is 05:19.

Tue Aug 9 05:19:48 UTC 2022 up 33 days, 7 mins, 1 user, load averages: 1.14, 1.47, 1.39