mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2013-05-21, 15:48   #1
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

350410 Posts
Default 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
File Type: zip paulspseudoprimepage.html.zip (4.1 KB, 98 views)
paulunderwood is offline   Reply With Quote
Old 2013-05-21, 18:04   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
I have written a web page which uses javascript to run a psedoprimality test.
You are misusing the word pseudoprime.
R.D. Silverman is offline   Reply With Quote
Old 2013-05-21, 18:21   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

DB016 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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.)"
paulunderwood is offline   Reply With Quote
Old 2013-05-22, 17:23   #4
jcrombie
 
jcrombie's Avatar
 
"Jonathan"
Jul 2010
In a tangled web...

2×107 Posts
Default

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.
jcrombie is offline   Reply With Quote
Old 2013-05-22, 19:17   #5
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts
Default

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
Mini-Geek is offline   Reply With Quote
Old 2013-05-22, 20:18   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

24×3×73 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2013-05-22, 20:22   #7
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
Mini-Geek is offline   Reply With Quote
Old 2013-05-22, 20:26   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

24·3·73 Posts
Default

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

Last fiddled with by paulunderwood on 2013-05-22 at 20:26
paulunderwood is offline   Reply With Quote
Old 2013-05-23, 00:27   #9
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

916110 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
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
Batalov is offline   Reply With Quote
Old 2013-05-23, 01:10   #10
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

24×3×73 Posts
Default

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
File Type: zip paulspseudoprimepage.html.zip (4.2 KB, 92 views)
paulunderwood is offline   Reply With Quote
Old 2013-05-23, 01:26   #11
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

9,161 Posts
Default

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
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
PhD student needed for Paul Zimmermann's group jasonp Operation Kibibit 1 2017-09-07 19:54
Searching for Paul Underwood diep Lounge 3 2009-12-18 12:25
New data page kar_bon Riesel Prime Search 144 2008-10-21 10:27
Question about your page OmbooHankvald 15k Search 2 2005-08-02 14:53
Paul Leyland's Mersenne factors table gone? ixfd64 Lounge 2 2004-02-18 09:42

All times are UTC. The time now is 17:18.

Mon Nov 30 17:18:26 UTC 2020 up 81 days, 14:29, 3 users, load averages: 1.65, 1.71, 1.75

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.