mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2018-08-20, 18:01   #1
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

23·3·5·11 Posts
Default Factoring using FFT on the Web browser

I've just updated my factorization tool to use FFT.

Now it can factor numbers up to 100000 digits. Since I made several changes in the program, I've uploaded the alpha version to https://test.alpertron.com.ar/ECM.HTM

Please let me know if you find problems.
alpertron is offline   Reply With Quote
Old 2018-08-20, 18:14   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

23×32×19 Posts
Default

Tried it on 10^99999, basically it doesn't seem that fast, maybe in a minute it could down to 10^99900 on the unfactored part.
R. Gerbicz is offline   Reply With Quote
Old 2018-08-20, 18:47   #3
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

23·3·5·11 Posts
Default

For numbers of about 10000 digits, it runs about 3 times faster than the previous version that uses Karatsuba.

Of course the applet cannot compete with native programs that can use Assembler. Remember that the code runs inside the Web browser.
alpertron is offline   Reply With Quote
Old 2018-08-20, 19:11   #4
GP2
 
GP2's Avatar
 
Sep 2003

2,579 Posts
Default

Quote:
Originally Posted by alpertron View Post
Of course the applet cannot compete with native programs that can use Assembler. Remember that the code runs inside the Web browser.
I wonder if, years from now, they will make Chromebook-style devices that run on chips that have WebAssembly as their native instruction set...

PS, it's confusing to call it an "applet". It's not an old-timey Java applet.
GP2 is offline   Reply With Quote
Old 2018-09-09, 18:43   #5
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

132010 Posts
Default

Now the calculation of sum of squares uses GCD of Gaussian integers (for two squares) and GCD of quaternions (for four squares).

The GCD takes about 1 second for numbers of 10000 digits (I tested that with the smallest gigantic prime, which is 109999 + 33603). Most of the time is used for a modular power.

With the previous version, computing the sum of four squares would have taken about one hour.

I will continue doing more tests, and if everything works OK, I will move the new Web application to the "standard" URL.
alpertron is offline   Reply With Quote
Old 2018-09-12, 17:32   #6
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

132010 Posts
Default

Quote:
Originally Posted by alpertron View Post
Now the calculation of sum of squares uses GCD of Gaussian integers (for two squares) and GCD of quaternions (for four squares).

The GCD takes about 1 second for numbers of 10000 digits (I tested that with the smallest gigantic prime, which is 109999 + 33603). Most of the time is used for a modular power.

With the previous version, computing the sum of four squares would have taken about one hour.

I will continue doing more tests, and if everything works OK, I will move the new Web application to the "standard" URL.
Now when the code detects that the number can be divided by a very small factor (less than 100000), it will quickly determine the maximum exponent of this small factor that can divide the number, so the factorization proceeds a lot faster.

For example, in the previous version the application needed 15 minutes to factor 2678!. In this version it needs only 10 seconds in the same computer.

Now I will need to change the program to quickly compute big factorials (say bigger than 5000!).
alpertron is offline   Reply With Quote
Old 2018-09-16, 12:56   #7
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

23×3×5×11 Posts
Default

I found no further errors, so the new factorization application is at its expected location: https://www.alpertron.com.ar/ECM.HTM
alpertron is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Primo Browser? PawnProver44 Information & Answers 14 2016-04-09 05:49
What browser do you use? Mini-Geek Lounge 12 2007-02-16 06:48
If you haven't yet ditched the Netscape browser... ewmayer Lounge 3 2005-05-10 00:28

All times are UTC. The time now is 14:28.

Tue Aug 4 14:28:53 UTC 2020 up 18 days, 10:15, 0 users, load averages: 1.78, 1.70, 1.72

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.