New feature in my ECM applet - Page 3

VolMike · 2009-03-24, 20:43

While factoring 55293490455562934504190087591724059219231190853 siqs application hangs on matrix step.

Any time I tried to factor this number applet stopped at
Solving 1306x1174 congruence matrix using Block Lanczos algorithm,
but ammount of found congruences was diffferent from time to time.

alpertron · 2009-03-25, 12:16

Yes, it appears that I performed an error in my last optimization so the SIQS fails for several numbers. At this moment I'm changing the applet to support multithread. In my first attempt the timings for 2 threads on 10^59+213 changed from 19 sec. to about 12 sec on the Core 2 Duo 1.86 GHz. After the multithreading code works ok I will continue fixing other errors.

VolMike · 2009-03-25, 12:48

Ok. That's great about multithread realization.

R.D. Silverman · 2009-03-25, 14:26

Quote:

Originally Posted by VolMike

While factoring 55293490455562934504190087591724059219231190853 siqs application hangs on matrix step.

Any time I tried to factor this number applet stopped at
Solving 1306x1174 congruence matrix using Block Lanczos algorithm,
but ammount of found congruences was diffferent from time to time.

So? This is not surprising. It is a random algorithm.

xilman · 2009-03-25, 15:40

Quote:

Originally Posted by R.D. Silverman

So? This is not surprising. It is a random algorithm.

It is if you start from a random state. Last I looked, the CWI lanczos.c used the same initialization vector on every run. Its implementation is fully deterministic, in other words.

Paul

Jeff Gilchrist · 2009-03-29, 18:50

So the multi-threaded version of the applet is now available and I have some benchmarks. If you are willing to use 4 cores you can sometimes finish your SIQS faster than both msieve and yafu. I wonder if this will encourage Jason and Ben to update their software to support multiple threads as well.

Code:

Intel Core2 Q9550 @ 3.4GHz (Vista 64bit)

SIQS (C85 = 1877138824359859508015524119652506869600959721781289179190693027302028679377371001561)
==================================================================================================
YAFU 1.08 64bit MSVC 32k       =  9m 25.339s
YAFU 1.06 64bit MSVC           =  9m 40.275s
YAFU 1.08 32bit gcc 32k        = 11m 53.406s
YAFU 1.08 32bit gcc-k8 32k     = 12m 13.938s
YAFU 1.06 32bit gcc-k8         = 12m 19.639s
YAFU 1.08 32bit MSVC 32k       = 12m 20.500s
YAFU 1.06 32bit gcc            = 12m 37.120s
YAFU 1.06 32bit MSVC           = 13m 09.457s
MSIEVE 1.40 32bit MSVC         = 13m 12.638s
ALPERTRON 3/28/09 Java (4 CPU) = 13m 31.100s
MSIEVE 1.40 32bit              = 15m 23.490s
MSIEVE 1.39 32bit              = 17m 12.597s
MSIEVE 1.40 64bit MSVC         = 17m 16.731s
MSIEVE 1.39 64bit MSVC         = 19m 43.278s
ALPERTRON 3/28/09 Java (2 CPU) = 20m 49.900s
ALPERTRON 3/16/09 Java         = 35m 47.000s
ALPERTRON 3/28/09 Java (1 CPU) = 36m 20.500s


SIQS (C80 = 43756152090407155008788902702412144383525640641502974083054213255054353547943661)
=============================================================================================
YAFU 1.08 64bit MSVC 32k       =  3m 55.513s
YAFU 1.06 64bit MSVC           =  4m 02.683s
MSIEVE 1.40 32bit MSVC         =  4m 21.863s
MSIEVE 1.40 32bit              =  4m 56.946s
YAFU 1.08 32bit gcc-k8 32k     =  4m 57.582s
YAFU 1.08 32bit gcc 32k        =  4m 51.829s
YAFU 1.06 32bit gcc-k8         =  4m 57.278s
ALPERTRON 3/28/09 Java (4 CPU) =  5m 05.600s
YAFU 1.06 32bit gcc            =  5m 06.302s
YAFU 1.08 32bit MSVC 32k       =  5m 13.631s
MSIEVE 1.40 64bit MSVC         =  5m 26.337s
MSIEVE 1.39 32bit              =  5m 26.477s
YAFU 1.06 32bit MSVC           =  5m 29.903s
MSIEVE 1.39 64bit MSVC         =  6m 07.678s
ALPERTRON 3/28/09 Java (2 CPU) =  8m 45.600s
ALPERTRON 3/28/09 Java (1 CPU) = 15m 19.900s
ALPERTRON 3/16/09 Java         = 16m 45.100s


SIQS (C75 = 281396163585532137380297959872159569353696836686080935550459706878100362721)
========================================================================================
ALPERTRON 3/28/09 Java (4 CPU) =  1m 19.300s
YAFU 1.08 64bit MSVC 32k       =  1m 35.469s
YAFU 1.06 64bit MSVC           =  1m 36.408s
MSIEVE 1.40 32bit MSVC         =  1m 42.414s
MSIEVE 1.40 32bit              =  1m 55.472s
YAFU 1.08 32bit gcc-k8 32k     =  1m 58.079s
YAFU 1.08 32bit gcc 32k        =  1m 56.374s
YAFU 1.06 32bit gcc-k8         =  2m 00.339s
MSIEVE 1.39 32bit              =  2m 02.102s
YAFU 1.06 32bit gcc            =  2m 02.787s
YAFU 1.08 32bit MSVC 32k       =  2m 04.064s
YAFU 1.06 32bit MSVC           =  2m 09.434s
MSIEVE 1.40 64bit MSVC         =  2m 10.401s
ALPERTRON 3/28/09 Java (2 CPU) =  2m 12.800s
MSIEVE 1.39 64bit MSVC         =  2m 20.447s
ALPERTRON 3/28/09 Java (1 CPU) =  4m 02.500s
ALPERTRON 3/16/09 Java         =  4m 30.200s


SIQS (C65 = 34053408309992030649212497354061832056920539397279047809781589871)
==============================================================================
YAFU 1.08 64bit MSVC 32k       =  0m 11.926s
YAFU 1.06 64bit MSVC           =  0m 12.355s
YAFU 1.08 32bit MSVC 32k       =  0m 14.335s
YAFU 1.08 32bit gcc 32k        =  0m 14.641s
MSIEVE 1.40 32bit              =  0m 14.711s
MSIEVE 1.40 32bit MSVC         =  0m 14.929s
ALPERTRON 3/28/09 Java (4 CPU) =  0m 15.000s
YAFU 1.08 32bit gcc-k8 32k     =  0m 15.160s
MSIEVE 1.39 32bit              =  0m 15.429s
YAFU 1.06 32bit gcc-k8         =  0m 15.568s
YAFU 1.06 32bit gcc            =  0m 15.631s
YAFU 1.06 32bit MSVC           =  0m 15.662s
MSIEVE 1.40 64bit MSVC         =  0m 15.912s
MSIEVE 1.39 64bit MSVC         =  0m 16.240s
ALPERTRON 3/28/09 Java (2 CPU) =  0m 24.600s
ALPERTRON 3/16/09 Java         =  0m 49.800s
ALPERTRON 3/28/09 Java (1 CPU) =  0m 44.800s

Congrats on the multi-threaded version Dario.

Jeff.

alpertron · 2009-03-29, 23:37

Thanks Jeff. There are still some errors which can be easily spotted when using batch factoring, because it can run a lot of factorizations until the applet hangs.

From the thread analysis I found that each worker thread is blocked 25% of the time when there are 4 threads sieving, so the applet can be optimized.

alpertron · 2009-07-07, 02:46

On 1 July 2009 Karl Vago hit the jackpot and found a 51-digit prime factor of 69 + 70 * 71⁷² using the curve number 19049. This is the first prime factor found by the applet with more than 50 digits. See http://www.alpertron.com.ar/ECMREC.HTM to get the current records.

alpertron · 2010-02-25, 19:43

I found an error on the applet about the Knuth-Schroeppel multiplier, where in some places I was not multiplying the original number by this multiplier so SIQS proceeded slowly when the multiplier is high. The timing is not changed when the multiplier equals 1.

This effect is very noticeable using Jeff Gilchrist's C65 because the multiplier equals 47.

SIQS time before correction in Core 2 Duo 1.8 GHz: 2min 9 sec.
After correction: 1 min 1.8sec

So in this particular case it runs more than twice as fast.

rekcahx · 2010-03-09, 21:24

Hello.

I'm unable to run this applet. These lines are from Java Console:

Quote:

load: class ecm.class not found.
java.lang.ClassNotFoundException: ecm.class
at sun.plugin2.applet.Applet2ClassLoader.findClass(Applet2ClassLoader.java:152)
at java.lang.ClassLoader.loadClass(ClassLoader.java:303)
at java.lang.ClassLoader.loadClass(ClassLoader.java:248)
at sun.plugin2.applet.Plugin2ClassLoader.loadCode(Plugin2ClassLoader.java:447)
at sun.plugin2.applet.Plugin2Manager.createApplet(Plugin2Manager.java:2880)
at sun.plugin2.applet.Plugin2Manager$AppletExecutionRunnable.run(Plugin2Manager.java:1397)
at java.lang.Thread.run(Thread.java:619)
Caused by: java.net.ConnectException: Network is unreachable
at java.net.PlainSocketImpl.socketConnect(Native Method)
at java.net.PlainSocketImpl.doConnect(PlainSocketImpl.java:333)
at java.net.PlainSocketImpl.connectToAddress(PlainSocketImpl.java:195)
at java.net.PlainSocketImpl.connect(PlainSocketImpl.java:182)
at java.net.SocksSocketImpl.connect(SocksSocketImpl.java:366)
at java.net.Socket.connect(Socket.java:525)
at sun.net.NetworkClient.doConnect(NetworkClient.java:161)
at sun.net.http://www.http.HttpClient.openServe...lient.java:394)
at sun.net.http://www.http.HttpClient.openServe...lient.java:529)
at sun.net.www.http.HttpClient.<init>(HttpClient.java:233)
at sun.net.www.http.HttpClient.New(HttpClient.java:306)
at sun.net.www.http.HttpClient.New(HttpClient.java:323)
at sun.net.http://www.protocol.http.HttpURLConn...ction.java:860)
at sun.net.http://www.protocol.http.HttpURLConn...ction.java:801)
at sun.net.http://www.protocol.http.HttpURLConn...ction.java:726)
at sun.net.http://www.protocol.http.HttpURLConn...tion.java:1049)
at java.net.HttpURLConnection.getResponseCode(HttpURLConnection.java:373)
at sun.plugin2.applet.Applet2ClassLoader.getBytes(Applet2ClassLoader.java:458)
at sun.plugin2.applet.Applet2ClassLoader.access$000(Applet2ClassLoader.java:46)
at sun.plugin2.applet.Applet2ClassLoader$1.run(Applet2ClassLoader.java:126)
at java.security.AccessController.doPrivileged(Native Method)
at sun.plugin2.applet.Applet2ClassLoader.findClass(Applet2ClassLoader.java:123)
... 6 more
Exception: java.lang.ClassNotFoundException: ecm.class

alpertron · 2010-03-09, 21:32

The file ecm.class is present. I don't know what Web browser you have, but I suggest you to download the latest Java plugin from http://www.java.com

Notice also the line: Caused by: java.net.ConnectException: Network is unreachable which means a problem in the client side.

2009-03-24, 20:43	#23
VolMike Jun 2007 Moscow,Russia 205₈ Posts	strange behaviour at siqs While factoring 55293490455562934504190087591724059219231190853 siqs application hangs on matrix step. Any time I tried to factor this number applet stopped at Solving 1306x1174 congruence matrix using Block Lanczos algorithm, but ammount of found congruences was diffferent from time to time.

2009-03-29, 23:37	#29
alpertron Aug 2002 Buenos Aires, Argentina 3²×149 Posts	Thanks Jeff. There are still some errors which can be easily spotted when using batch factoring, because it can run a lot of factorizations until the applet hangs. From the thread analysis I found that each worker thread is blocked 25% of the time when there are 4 threads sieving, so the applet can be optimized. Last fiddled with by alpertron on 2009-03-29 at 23:37

2009-07-07, 02:46	#30
alpertron Aug 2002 Buenos Aires, Argentina 3²·149 Posts	New factorization record for the applet On 1 July 2009 Karl Vago hit the jackpot and found a 51-digit prime factor of 69 + 70 * 71⁷² using the curve number 19049. This is the first prime factor found by the applet with more than 50 digits. See http://www.alpertron.com.ar/ECMREC.HTM to get the current records.

2010-03-09, 21:32	#33
alpertron Aug 2002 Buenos Aires, Argentina 1341₁₀ Posts	The file ecm.class is present. I don't know what Web browser you have, but I suggest you to download the latest Java plugin from http://www.java.com Notice also the line: Caused by: java.net.ConnectException: Network is unreachable which means a problem in the client side. Last fiddled with by alpertron on 2010-03-09 at 21:37

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Java applet alternative	a1call	Programming	19	2019-11-08 22:31
New online applet for factorization	ET_	Lone Mersenne Hunters	69	2014-06-01 17:34
A strange applet:	3.14159	Miscellaneous Math	7	2010-06-01 01:29
Faster factorization applet	alpertron	Factoring	14	2006-01-01 04:00
Binomial Expansion Applet	jinydu	Lounge	2	2004-05-05 08:33

2009-03-25, 12:16	#24
alpertron Aug 2002 Buenos Aires, Argentina 3²·149 Posts	Yes, it appears that I performed an error in my last optimization so the SIQS fails for several numbers. At this moment I'm changing the applet to support multithread. In my first attempt the timings for 2 threads on 10^59+213 changed from 19 sec. to about 12 sec on the Core 2 Duo 1.86 GHz. After the multithreading code works ok I will continue fixing other errors.

2009-03-25, 12:48	#25
VolMike Jun 2007 Moscow,Russia 7·19 Posts	Ok. That's great about multithread realization.

2010-02-25, 19:43	#31
alpertron Aug 2002 Buenos Aires, Argentina 3²·149 Posts	I found an error on the applet about the Knuth-Schroeppel multiplier, where in some places I was not multiplying the original number by this multiplier so SIQS proceeded slowly when the multiplier is high. The timing is not changed when the multiplier equals 1. This effect is very noticeable using Jeff Gilchrist's C65 because the multiplier equals 47. SIQS time before correction in Core 2 Duo 1.8 GHz: 2min 9 sec. After correction: 1 min 1.8sec So in this particular case it runs more than twice as fast.