mersenneforum.org  

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

Reply
 
Thread Tools
Old 2006-04-06, 19:29   #23
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

3×5×727 Posts
Default

Tony Reix just brought to my attention a bug in the sieve-bit-clearing code inside Mfactor - if the NUM_SIEVING_PRIME value used by the code is such that the largest sieve prime >= Mersenne exponent p, the sieve-clearing routine winds up sending a zero argument to the 32-bit extended GCD routine used to calculate sieve bit offsets, causing an error, for instance invoking the code with

Mfactor -m 100003 -bmin 10 -bmax 50

gives the following error:

Code:
INFO: No factoring savefile t100003 found ... starting from scratch.
searching in the interval k=[0, 1475695268087040], i.e. q=[1.000000e+00, 2.951479e+20]
each of 16 (p mod 60) passes will consist of 90332172 intervals of length 272272
ERROR: eGCD called with zero input: x = 0, y = 100003
ERROR: At line 825 of file ../util.c
Assertion failed: 0
The fix is simple - in such cases the sieve-clearing routine should just skip over p as it processes the sieving primes (since p can never divide a factor candidate of form q = 2*k*p+1 anyway), and this will be included in the next release, but in the meanwhile you should be able to run any prime > 1299721 (the maximum sieving prime used when NUM_SIEVING_PRIME = 100000 as in most of the builds I posted - if you happen to have a build with the default value of NUM_SIEVING_PRIME = 50000, p must be > 611957) without problems. I'd been so focused on large p's I neglected to run some small ones.

Last fiddled with by ewmayer on 2006-04-06 at 19:38
ewmayer is offline   Reply With Quote
Old 2006-04-13, 16:12   #24
S00113
 
S00113's Avatar
 
Dec 2003

23×33 Posts
Default Mfactor on Linksys WRT54G wireless router

I compiled Mfactor (an old version I found on the web) for my Linksys WRT54G router, and it works! The router runs Linux, and I have changed to the OpenWRT distribution to get a more user friendly version. (At least it is more friendly to old unix users like me.) The CPU is a BCM4712 which runs the MIPS32 instruction set at 216MHz. The router also has 16 MiB RAM and 8 MiB flash memory. Frequenzy, RAM and amount of flash varies between versions, and not all versions run Linux. Go to http://www.openwrt.org/ for more information on this and other wireless routers with similar hardware.

This version limits factoring to 60 bits with 32bit integer arithmetic. Here is the result of one of my first tests (the 59 bit factor is known):

Code:
root@line:~# time ./Mfactor -h factorlog 77485997 3 1152921504606846975
# Mersenne factorer.  Author:  Peter L. Montgomery, pmontgom@cwi.nl
# $Id: Mfactor.c,v 1.2 1999/03/24 05:45:50 pmontgom Exp pmontgom $
# Compiled by GCC on 32-bit MIPS under IRIX.
sh: hinv: not found
# ARITHMETIC_MODEL = ARITHMETIC_INT32
# NUM_SIEVING_PRIME = 34567,   SIEVE_LENGTH_BITS = 204800
# SIEVE_STEP_BIT = 840
# TRYQ_BLOCKING = 3,     USING_ASSEMBLY = 0,    USING_POPULATION_COUNT = 0
# VECTOR = 0,    SHORT_VECTOR_LENGTH = 20
# Type sieving_prime_t has 32 bits.
# Type wsieve_t has 32 bits, of which all 32 are used.
# Type natural_t is signed and has 32 bits.
# Type uint32 has 32 bits.  Type uint64 has 64 bits.
# QBITSMAX = 60
#
# Invoked as ./Mfactor -h factorlog 77485997 3 1152921504606846975
# Running on line.(none) at Thu Apr 13 14:04:57 2006
#
# p = 77485997.  Searching q in [154971995, 1152921504488807235]
# The isieve loop in tryp sieves an interval of length
#    13330071035904000 = 1.333e+16  in NSIEVE = 96 pieces.
# It will need   86.49 passes to search from 154971995 to 1152921504488807235.
# 34567-th sieving prime is 409639.  9791 are below SIEVE_LENGTH_BITS/2,
# 8562 more below SIEVE_LENGTH_BITS, 16214 above.
M( 77485997 )C: 1152331426770601081  # line.(none)  @  Thu Apr 13 15:26:51 2006
# 323699721 values of q tried out of 1700467991 sieved.
#  80.96% of potential q's (mod 840*p) were eliminated by sieving.
M( 77485997 )U: 1152921504488807235  # line.(none)  @  Thu Apr 13 15:27:09 2006
real    1h 22m 12s
user    1h 21m 38s
sys     0m 33.76s
Next I'll try to make it faster by adjusting various defines in the source. Are there newer versions of Mfactor out there with new optimizations which may work on 32bit hardware?

Next project is mersfacgmp, which is able to factor higher and talk to a server, but mersfacgmp is much harder to cross-compile.
S00113 is offline   Reply With Quote
Old 2006-04-13, 17:50   #25
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

3×5×727 Posts
Default

Sorry about the nomenclatural confusion (Peter Montgomery and I have last names beginning with the same letter, after all), but that's a different Mfactor than the one being discussed in this thread. Peter's code is very fast on a small set of 64-bit hardware (Alpha and SGI MIPS) for which Peter wrote custom assembly code subroutines for key operations, but be aware that that code can go only up to 63 bits, and even less on some platforms (as you note). Should be fine for using on slower hardware though, since you're not going to want to be factoring very deep there, to begin with.

To reiterate: although the 2 codes are intended for the same purpose and use similary underlying algorithms, the implementations are completely independent, i.e.

M(ayer)factor != M(ontgomery)factor

As to the question about optimizations for 32-bit hardware, I have no plans for my mfactor code along these lines - just not worth the effort. Your same test example to 60 bits needs around a minute on decent 64-bit hardware running around 2GHz - even factoring in the clock speed difference that's nearly an order of magntiude faster in terms of per-cycle performance. My intention is not to discourage you from playing with this, but just to say that optimizing for 32-bit isn't where I'll be spending my own time.

Oh, here's the on-screen output from my run, just to illustrate that we're talking about different codes:

Code:
Mfactor build flags:
TRYQ = 4
THREE_OP128 = FALSE
NUM_SIEVING_PRIME = 100000
USE_FLOAT not defined
USE_FMADD not defined
FACTOR_STANDALONE = 1
FAC_DEBUG = 0
DBG_SIEVE not defined
NOBRANCH = 1
QUIT_WHEN_FACTOR_FOUND not defined
USE_65BIT not defined
USE_128x96 = 1
P2WORD not defined
P3WORD not defined
P4WORD not defined
Mfactor self-tests:
Testing 63-bit factors...
Testing 64-bit factors...
Testing 65-bit factors...
Testing 96-bit factors...
Factoring self-tests completed successfully.
INFO: No factoring savefile t77485997 found ... starting from scratch.
searching in the interval k=[0, 7449361920], i.e. q=[1.000000e+00, 1.154442e+18]
each of 16 (p mod 60) passes will consist of 456 intervals of length 272272
max sieving prime = 1299721
Time to set up sieve = 00:00:00.080
pass = 0....
pass = 1....
pass = 2....
pass = 3....
pass = 4....
pass = 5....
pass = 6....
pass = 7....
pass = 8....
pass = 9....
pass = 10....
pass = 11....
pass = 12....
pass = 13....
pass = 14....
pass = 15....M77485997 has a factor: 1152331426770601081. Program: E2.8x

M77485997 has 1 factors in [1.000000e+00, 1.154442e+18], passes 0-15
Performed 299545084 trial divides
checksum1 = 03A973A58DED4EBE
Clocks = 00:01:12.439
73.910u 0.013s 1:14.64 99.0%    0+0k 0+0io 17pf+0w

Last fiddled with by ewmayer on 2006-04-13 at 18:04
ewmayer is offline   Reply With Quote
Old 2006-04-17, 21:17   #26
S00113
 
S00113's Avatar
 
Dec 2003

3308 Posts
Default

Quote:
Originally Posted by ewmayer
Sorry about the nomenclatural confusion (Peter Montgomery and I have last names beginning with the same letter, after all), but that's a different Mfactor than the one being discussed in this thread.
I should have guessed that. I have used your Mfactor before on AMD64, and noticed the output was very different. Great program btw. Once found a 70-bit factor for me.
Quote:
As to the question about optimizations for 32-bit hardware, I have no plans for my mfactor code along these lines - just not worth the effort.
Completely understandable. I'm just doing this for fun. it is not high priority in any way.
Quote:
Your same test example to 60 bits needs around a minute on decent 64-bit hardware running around 2GHz - even factoring in the clock speed difference that's nearly an order of magntiude faster in terms of per-cycle performance. My intention is not to discourage you from playing with this, but just to say that optimizing for 32-bit isn't where I'll be spending my own time.
My intentions with my wireless router is have fun and to fill gaps in factoring. Find more factors of exponents with known small factors, double check factoring from clients with bugs which may have caused them to miss a factor, etc. Trial factoring such composites is low priority work. Most, probably all, of the factors my slow wireless router find will already have been found by P-1, ECM or by trial factoring because the client wasn't buggy after all. I wouldn't use my precious 64-bit CPUs on this. Old 386s, 486s, PentiumIIIs, SGI Indys, DecStations and my cheap wireless router will do the job just fine while our modern machines use their resources on heavier crunching.
S00113 is offline   Reply With Quote
Old 2006-04-18, 19:05   #27
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

1090510 Posts
Default

Quote:
Originally Posted by S00113
My intentions with my wireless router is have fun and to fill gaps in factoring. Find more factors of exponents with known small factors, double check factoring from clients with bugs which may have caused them to miss a factor, etc. Trial factoring such composites is low priority work. Most, probably all, of the factors my slow wireless router find will already have been found by P-1, ECM or by trial factoring because the client wasn't buggy after all. I wouldn't use my precious 64-bit CPUs on this. Old 386s, 486s, PentiumIIIs, SGI Indys, DecStations and my cheap wireless router will do the job just fine while our modern machines use their resources on heavier crunching.
Well have fun, and keep us posted on your progress! As you say, since we're not talking the "race for the cure" for some disease here, it's more about having fun and learning interesting/useful things than anything else.
ewmayer is offline   Reply With Quote
Old 2006-11-03, 08:05   #28
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

2·3·293 Posts
Default

http://home.earthlink.net/~elevensmooth/Billion.html

(I thought it would be useful to post this link in a Sticky thread)
jinydu is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Easiest working Quadratic Sieve code? skan Programming 4 2018-03-24 09:54
Sieve Benchmark Thread Historian Twin Prime Search 105 2013-02-05 01:35
Factor5 source code thread ET_ Operation Billion Digits 10 2008-09-17 12:28
Where I should write C code (thread moved) maqableh Programming 9 2006-05-12 16:22
New Sieve Thread Discussion Citrix Prime Sierpinski Project 15 2005-08-29 13:56

All times are UTC. The time now is 05:07.

Wed Apr 1 05:07:59 UTC 2020 up 7 days, 2:41, 0 users, load averages: 1.22, 1.41, 1.46

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.