mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Operation Billion Digits

Reply
 
Thread Tools
Old 2007-03-07, 12:46   #1
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

112338 Posts
Smile Factor5 !

Happy birthday to me! Instead of getting presents, I decided to release my new piece of softwre to you today!

Cygwin environment required for the provided executables.

The C code has been successfully compiled under Windows XP after installing GMP library

(from www.swox.com/gmp)

Factor5 asks for the exponent of the Mersenne number to be tested, for starting and ending bit depths, and number of threads.

It writes statistical lines on the screen, and outputs results on the "results.txt" file.

Each 150 seconds a stand-alone thread updates the "status.txt" file.

Factor5 implements a --resume switch to resume from the status file and a --version switch to show version.

I implemented multi-threading with pthreads technology: is now possible to communicate how many threads the program must use. Dual cores machines will improve their performance with 2 threads, quad cores will run faster with 4 threads, Beowulf clusters may adopt 8 or 16 threads. As I do not owe Beowulf clusters or multi-processor machines, tests from users are kindly requested (HINT! HINT!)

Also, if you compile the source for different environments, please let me have the executable to update our download page: you will be credited there for your work.

The program runs as a command-line executable. It is easy to create a batch file to run a search on a group of exponents: simply entry the following lines:

Code:
factor5 <exponent> <start_bit> <stop_bit> <number of threads to use>
factor5 <exponent> <start_bit> <stop_bit> <number of threads to use>
factor5 <exponent> <start_bit> <stop_bit> <number of threads to use>
into a batch or cmd or shell file.

Source, executable and Cygwin1.dll files are available here.

Note that this file has no limitation regarding bit depth or exponent size. A somewhat slower version to check for factors lower than the max_prime element used for sieving is available (I.E. 2^233-1 has 1399 as a factor...) commenting line nr. 541 and decommenting line 540.

As I wrote FACTOR for my own pleasure, the program has very few functions for syntax-checking, anyway, if you think that this software could be used in some distributed projects, or you simply "desire" an option to be added, just send me a line (L.Morelli@mclink.it), and I will try to set it up.

If you have ideas on how to improve it, I will gladily try to add them, giving you the right acknowledgement on the source code.

I would like to acknowledge the following people, who helped me during the development of this program:

- George Woltman, who directed my passion towards Mersenne numbers;
- Ernst Mayer, who wrote Mfactor: I considered his program and directions as my guide;
- Andreas Pipp, who wrote the first factorization program i studied using MP libraries;
- Arjan Koek, who compiled a version under PowerPC and MAC OSX;
- Andres Aitsen who contributed a version for BSD;
- Dmitri Gribenko who worked on version 4.0 for Linux;
- Xenon, Nick Fortino and Peter Nelson, who spotted bugs and showed tricks to improve efficiency;
- Mark Rodenkirch who compiled a version for MAC G5 64 bit on OSX;
- Daniele Forsi who developed a more elegant and user-friendly code;
- Patrizia Colombo, who gave me her patience and a powerful idea during development;
- All the partecipants to Operation Billion Digits.

Have fun and let me know about your comments!

Luigi

Last fiddled with by ET_ on 2007-03-07 at 12:52
ET_ is offline   Reply With Quote
Old 2007-03-07, 17:42   #2
gribozavr
 
gribozavr's Avatar
 
Mar 2005
Internet; Ukraine, Kiev

11×37 Posts
Default

A minor mistake in readme.txt (or a typo):
Quote:
Originally Posted by readme.txt
Luigi Morelli, March 7th, 2006
It is 2007 now...

Edit: compiled successfully on 64-bit Linux, will test it now.

From the code:
fprintf(stderr, "\nnum_threads must be 1, 2, 4, 8, 16");
It might be a good idea to put a final \n there.

Last fiddled with by gribozavr on 2007-03-07 at 17:48
gribozavr is offline   Reply With Quote
Old 2007-03-08, 17:31   #3
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

11×433 Posts
Default

Quote:
Originally Posted by gribozavr View Post
A minor mistake in readme.txt (or a typo):

It is 2007 now...

Edit: compiled successfully on 64-bit Linux, will test it now.

From the code:
fprintf(stderr, "\nnum_threads must be 1, 2, 4, 8, 16");
It might be a good idea to put a final \n there.
Thank you gribozavr! It will soon be done.

Luigi

P.S. let me know how it behaves in a 64 bit environment... and eventually send me a copy of the executable.
ET_ is offline   Reply With Quote
Old 2007-03-08, 21:29   #4
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

3·1,951 Posts
Default

For some unknown reason pthread_create() segfaults upon starting the factorize thread on a 64-bit PPC system. I haven't been able to track down the problem, but there seems to be an inability to start a thread that uses 64-bit registers. Could you modify factor5 so that if the user specifies one thread, that it does not use pthread for anything?
rogue is offline   Reply With Quote
Old 2007-03-08, 22:30   #5
gribozavr
 
gribozavr's Avatar
 
Mar 2005
Internet; Ukraine, Kiev

11·37 Posts
Default

I run Ernst's standard test: M2147483647 from 1 to 68 bits:
Quote:
Originally Posted by results.txt
Trial-factoring M2147483647 in [2^1, 2^68-1]
M2147483647 has a factor: 87054709261955177 - Program: L5.0x
M2147483647 has a factor: 295257526626031 - Program: L5.0x
M2147483647 has a factor: 242557615644693265201 - Program: L5.0x
M2147483647 has 3 factors in [2^1, 2^68-1].
Is this enough testing? Can I send you the binary already? I compiled it like this:
$ gcc -W -Wall -O2 -lgmp -lpthread factor5.c -o factor5
gribozavr is offline   Reply With Quote
Old 2007-03-09, 00:26   #6
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

3×1,951 Posts
Default

Quote:
Originally Posted by gribozavr View Post
I run Ernst's standard test: M2147483647 from 1 to 68 bits:


Is this enough testing? Can I send you the binary already? I compiled it like this:
$ gcc -W -Wall -O2 -lgmp -lpthread factor5.c -o factor5
Could you give the total time for that test? It would be interesting to compare different CPUs.
rogue is offline   Reply With Quote
Old 2007-03-09, 00:37   #7
gribozavr
 
gribozavr's Avatar
 
Mar 2005
Internet; Ukraine, Kiev

40710 Posts
Default

No, I didn't measure it... Besides, it is a heavily-loaded machine with much disk activity, so it would be incorrect (~ +10%) anyway.

factor5.tar.gz: http://www.sendspace.com/file/7oew3n

Last fiddled with by gribozavr on 2007-03-09 at 00:40
gribozavr is offline   Reply With Quote
Old 2007-03-09, 18:19   #8
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

476310 Posts
Default

Quote:
Originally Posted by gribozavr View Post
No, I didn't measure it... Besides, it is a heavily-loaded machine with much disk activity, so it would be incorrect (~ +10%) anyway.

factor5.tar.gz: http://www.sendspace.com/file/7oew3n
Thank you! Tomorrow I will update my website.

Luigi
ET_ is offline   Reply With Quote
Old 2007-03-09, 18:21   #9
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

112338 Posts
Default

Quote:
Originally Posted by rogue View Post
Could you give the total time for that test? It would be interesting to compare different CPUs.
You can subtract dates printed after the program starts and before it ends. This timing is not "optimal", but I had headaches working with threads and timers...

Maybe in next release, and with some help.

Luigi
ET_ is offline   Reply With Quote
Old 2007-03-09, 18:24   #10
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

11·433 Posts
Default

Quote:
Originally Posted by rogue View Post
For some unknown reason pthread_create() segfaults upon starting the factorize thread on a 64-bit PPC system. I haven't been able to track down the problem, but there seems to be an inability to start a thread that uses 64-bit registers. Could you modify factor5 so that if the user specifies one thread, that it does not use pthread for anything?
I have a file named Factor5st (single-thread) that does not use threads (I used it to test the base algorithm). PM your actual email and I will send it to you.

Thank you for your collaboation.

Luigi

Last fiddled with by ET_ on 2007-03-09 at 18:24
ET_ is offline   Reply With Quote
Old 2007-03-11, 22:11   #11
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

3·1,951 Posts
Default Benchmark

time ./factor5 2147483647 1 68

M2147483647 has a factor: 87054709261955177 - Program: L5.0x
M2147483647 has a factor: 295257526626031 - Program: L5.0x
M2147483647 has a factor: 242557615644693265201 - Program: L5.0x

Performed 2740271748 powmod operations
Used 100021 primes, max. prime = 1299989
Current date Sun Mar 11 16:55:44 2007

real 201m44.702s
user 199m9.627s
sys 0m35.742s

on 64-bit PowerPC.

I think that the time could be improved by possibly as much as 10% by unrolling some of the loops in the factorize() procedure, but I can't speak for certain on that.
rogue is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factor5 revamping ET_ Operation Billion Digits 35 2017-09-25 02:29
Factor5 on Multicore Machines Rodrigo Operation Billion Digits 4 2011-01-02 04:50
Factor5 source code thread ET_ Operation Billion Digits 10 2008-09-17 12:28

All times are UTC. The time now is 11:47.

Thu Aug 13 11:47:17 UTC 2020 up 8:22, 0 users, load averages: 1.19, 1.41, 1.33

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.