mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2009-03-24, 20:43   #23
VolMike
 
VolMike's Avatar
 
Jun 2007
Moscow,Russia

2058 Posts
Default 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.
VolMike is offline   Reply With Quote
Old 2009-03-25, 12:16   #24
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

32·149 Posts
Default

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.
alpertron is offline   Reply With Quote
Old 2009-03-25, 12:48   #25
VolMike
 
VolMike's Avatar
 
Jun 2007
Moscow,Russia

7·19 Posts
Default

Ok. That's great about multithread realization.
VolMike is offline   Reply With Quote
Old 2009-03-25, 14:26   #26
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

Quote:
Originally Posted by VolMike View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2009-03-25, 15:40   #27
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2×3×17×103 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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

Last fiddled with by xilman on 2009-03-25 at 15:42 Reason: Clarification.
xilman is offline   Reply With Quote
Old 2009-03-29, 18:50   #28
Jeff Gilchrist
 
Jeff Gilchrist's Avatar
 
Jun 2003
Ottawa, Canada

7·167 Posts
Default

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.
Jeff Gilchrist is offline   Reply With Quote
Old 2009-03-29, 23:37   #29
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

32×149 Posts
Default

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
alpertron is offline   Reply With Quote
Old 2009-07-07, 02:46   #30
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

32·149 Posts
Default 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 * 7172 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 is offline   Reply With Quote
Old 2010-02-25, 19:43   #31
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

32·149 Posts
Default

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.
alpertron is offline   Reply With Quote
Old 2010-03-09, 21:24   #32
rekcahx
 
Oct 2009
Oulu, Finland

111102 Posts
Default Error in applet

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
rekcahx is offline   Reply With Quote
Old 2010-03-09, 21:32   #33
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

134110 Posts
Default

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

Thread Tools


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

All times are UTC. The time now is 21:39.

Thu Jan 21 21:39:49 UTC 2021 up 49 days, 17:51, 0 users, load averages: 2.21, 2.35, 2.38

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.