20060406, 19:29  #23 
∂^{2}ω=0
Sep 2002
República de California
3×5×727 Posts 
Tony Reix just brought to my attention a bug in the sievebitclearing code inside Mfactor  if the NUM_SIEVING_PRIME value used by the code is such that the largest sieve prime >= Mersenne exponent p, the sieveclearing routine winds up sending a zero argument to the 32bit 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 Last fiddled with by ewmayer on 20060406 at 19:38 
20060413, 16:12  #24 
Dec 2003
2^{3}×3^{3} Posts 
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 32bit 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. # 34567th 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 project is mersfacgmp, which is able to factor higher and talk to a server, but mersfacgmp is much harder to crosscompile. 
20060413, 17:50  #25 
∂^{2}ω=0
Sep 2002
República de California
3·5·727 Posts 
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 64bit 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 32bit 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 64bit hardware running around 2GHz  even factoring in the clock speed difference that's nearly an order of magntiude faster in terms of percycle performance. My intention is not to discourage you from playing with this, but just to say that optimizing for 32bit isn't where I'll be spending my own time. Oh, here's the onscreen 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 selftests: Testing 63bit factors... Testing 64bit factors... Testing 65bit factors... Testing 96bit factors... Factoring selftests 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 015 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 20060413 at 18:04 
20060417, 21:17  #26  
Dec 2003
2^{3}×3^{3} Posts 
Quote:
Quote:
Quote:


20060418, 19:05  #27  
∂^{2}ω=0
Sep 2002
República de California
3×5×727 Posts 
Quote:


20061103, 08:05  #28 
Dec 2003
Hopefully Near M48
1758_{10} Posts 
http://home.earthlink.net/~elevensmooth/Billion.html
(I thought it would be useful to post this link in a Sticky thread) 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Easiest working Quadratic Sieve code?  skan  Programming  4  20180324 09:54 
Sieve Benchmark Thread  Historian  Twin Prime Search  105  20130205 01:35 
Factor5 source code thread  ET_  Operation Billion Digits  10  20080917 12:28 
Where I should write C code (thread moved)  maqableh  Programming  9  20060512 16:22 
New Sieve Thread Discussion  Citrix  Prime Sierpinski Project  15  20050829 13:56 