mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2009-11-23, 04:34   #100
bdodson
 
bdodson's Avatar
 
Jun 2005
lehigh.edu

210 Posts
Default 3.2e6 extra relations found!!

Quote:
Originally Posted by bdodson View Post
4k ranges. ...

Code:
 the 180M-190M drops by

135449434 = 1205137608-1069688174 so something like
125000000 is missing, more than 10%.

It would be easier to re-sieve the entire 10M range, than to figure
out what pieces didn't run. ... -Bruce
For the record, Tom has far more persistence than I, as well as
better analytical skills. He located each 4K range with empty
outfile (as that was the source of the shortage). Also, in my PM
on 160M-170M-A I noted that that file-size appeared short as well;
and after added confusion due to an unfortunate (and un-informative)
file name, Tom tracked down those 4K ranges too.

So I'm happy to report line counts of
Code:
  1328828 2m941.add160A
  1883125 2m941.add180R
  ---
  3211953 total
showing an extra 3.2e6 relns from those two ranges. File sizes are
Code:
   85357550 Nov 22 22:28 2m941.add160A.gz
  121539038 Nov 22 22:30 2m941.add180R.gz
  ---
 1183778834 Nov 22 22:34 2m941.190M-200M-R.gz   (New)
The latter with empty outfiles located and replaced here.
Looks like 55 empty files of the first 700/2500 on 190M-200M-A,
so far.

As a side affect of Tom's persistence, and a somewhat smaller
than expected datset from 10p244 (not much, if any, over-sieving),
I double-checked the last of the 2L1646 sieving. There were 4-5
outfiles that were notably small, and re-running picked up a few more
relations. Not worth mention; except that in 33M I got sixteen
ranges that appear to remain empty, and eight others that are
reproducibly short:
Code:
 130292 Nov 22 13:19 2L1646.33.80Me-33.82M
 103917 Nov 22 12:19 2L1646.33.80Mo-33.82M
 105953 Nov 22 13:21 2L1646.33.82Me-33.84M
 272636 Nov 22 13:26 2L1646.33.82Mo-33.84M
 357209 Nov 22 13:31 2L1646.33.84Me-33.86M
 432934 Nov 22 14:40 2L1646.33.84Mo-33.86M
 539579 Nov 22 13:05 2L1646.33.86Me-33.88M
 557717 Nov 22 15:22 2L1646.33.86Mo-33.88M
All of the other files are above 1450000, until the known
15e shortfall in 67M:
Code:
  791552  2L1646.67.84Me-67.86M
  894671  2L1646.67.86Me-67.88M
  926637  2L1646.67.82Mo-67.84M
 1030733  2L1646.67.84Mo-67.86M
 1051659  2L1646.67.86Mo-67.88M
 1069317  2L1646.67.88Mo-67.90M
 1209149  2L1646.67.96Mo-67.98M
Sounds like a new half-tone? -Bruce

Last fiddled with by bdodson on 2009-11-23 at 04:37 Reason: typo
bdodson is offline   Reply With Quote
Old 2009-11-23, 08:53   #101
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

97×103 Posts
Default 33M and 67M areas

33 and 67M are exactly the old problematic areas (that's slighly above 225 and 226; and that's why I sieved the 67-69M for M941; I love standing under the bridges I've had a part in building).

Could you please mail me (or sftp you know where) the exact binary. I'll try your binary and my binary on these spots. These spots of bother are slightly important to get every last penny and dime from our sieving for the future, so I will re-debug these.
Batalov is offline   Reply With Quote
Old 2009-11-24, 20:38   #102
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2×7×461 Posts
Default Superfluous reservations-closed message

Bruce has just deposited the last batch of his relations with me, Greg says NFS@home will have its relations ready within three days; so the sieving reservations are officially closed. There'll be a filtering post when the NFS@home relations get in, and then six or so weeks of silence ...
fivemack is offline   Reply With Quote
Old 2009-11-28, 12:53   #103
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2×7×461 Posts
Default Et sic incipit ...

A50-200, R50-225; a previous run with A50-190, R50-200 produced
Code:
Wed Nov 25 08:03:59 2009  weight of 25252869 cycles is about 1767914533 (70.01/cycle)
and I didn't let it proceed to a matrix.

Code:
Fri Nov 27 21:05:40 2009  found 185171752 hash collisions in 630275922 relations
Fri Nov 27 21:05:55 2009  commencing duplicate removal, pass 2
Fri Nov 27 21:18:44 2009  found 209659308 duplicates and 420616614 unique relations
Fri Nov 27 23:48:27 2009  keeping 208685087 ideals with weight <= 20, target excess is 23792624
Fri Nov 27 23:53:06 2009  memory use: 7267.0 MB
Fri Nov 27 23:53:06 2009  commencing in-memory singleton removal
Fri Nov 27 23:53:24 2009  begin with 307924854 relations and 208685087 unique ideals
Sat Nov 28 05:17:04 2009  weight of 24591147 cycles is about 1760189328 (71.58/cycle)
Sat Nov 28 05:17:04 2009  heaviest cycle: 15 relations
Sat Nov 28 05:17:05 2009  matrix can improve, retrying
Sat Nov 28 11:00:58 2009  found 27820019 cycles, need 24259228
Sat Nov 28 11:01:06 2009  weight of 24259228 cycles is about 1698245729 (70.00/cycle)
Sat Nov 28 11:39:35 2009  matrix is 24255350 x 24259228 (7042.8 MB) with weight 2020223779 (83.28/col)
Sat Nov 28 11:39:35 2009  sparse part has weight 1579370835 (65.10/col)
Sat Nov 28 11:47:12 2009  filtering completed in 3 passes
Sat Nov 28 11:47:16 2009  matrix is 24160433 x 24160633 (7026.9 MB) with weight 2015484660 (83.42/col)
Sat Nov 28 11:47:16 2009  sparse part has weight 1576291289 (65.24/col)
Sat Nov 28 11:49:47 2009  matrix is 24160385 x 24160633 (6716.4 MB) with weight 1620450280 (67.07/col)
Sat Nov 28 11:49:47 2009  sparse part has weight 1519048439 (62.87/col)
Sat Nov 28 11:51:38 2009  commencing Lanczos iteration (4 threads)
At about 12:48: 'linear algebra completed 19985 of 24160633 dimensions (0.1%, ETA 1097h32m)';
Code:
1000     25249  108 69.0 8436436 8401376 pts/7 Rl+  Nov27 1142:34 /home/nfsworld/msieve-svn/trunk/msieve -v -nc -t 4
13 January or so, assuming no hideous hardware failures, rains of bees or similar.
fivemack is offline   Reply With Quote
Old 2009-11-28, 13:11   #104
bdodson
 
bdodson's Avatar
 
Jun 2005
lehigh.edu

210 Posts
Default

Quote:
Originally Posted by fivemack View Post
...
Code:
Wed Nov 25 08:03:59 2009  weight of 25252869 cycles is about 1767914533 (70.01/cycle)
and I didn't let it proceed to a matrix.

Code:
...
Sat Nov 28 11:47:16 2009  sparse part has weight 1576291289 (65.24/col)
Sat Nov 28 11:49:47 2009  matrix is 24160385 x 24160633 (6716.4 MB) with weight 1620450280 (67.07/col)
Sat Nov 28 11:49:47 2009  sparse part has weight 1519048439 (62.87/col)
Sat Nov 28 11:51:38 2009  commencing Lanczos iteration (4 threads)
...
13 January or so, assuming no hideous hardware failures, rains of bees or similar.
So was 25.25M^2 --> 24.16M^2 the range of improvement expected
from the extra sieving? Uhm, 7 weeks or-so; that's a fair chunk of
a season. -Bruce
bdodson is offline   Reply With Quote
Old 2009-11-28, 14:21   #105
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2·7·461 Posts
Default

To be honest, I think I was expecting the 'extra extra sieving' to give a more clear benefit. If I had another machine with 12G memory I could get a better idea of what exactly is happening with the oversieving, but I don't have space to filter a 32-bit matrix while running another 32-bit matrix.

Fourteen days (336 hours) of sieving has reduced the ETA by a bit over 400 hours over the estimate from 13 November, so in real-time terms we are winning, but it's quite possible that most of that saving came from the first week. Though the granularity of sieving requests, particularly through nfs@home, is also about two weeks, so I'm not sure I could have hoped to be very much more accurate.

My estimate is that the ETA for the 25252869 matrix would be about 1200 hours, so the extra relations saved about a hundred hours at what was probably an uneconomic cost in both human input and CPU time, but I'm not sure I could have known that before I asked for them.

Last fiddled with by fivemack on 2009-11-28 at 14:25
fivemack is offline   Reply With Quote
Old 2010-01-12, 18:18   #106
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2·7·461 Posts
Default

Code:
Sat Nov 28 11:51:38 2009  commencing Lanczos iteration (4 threads)
Sat Nov 28 11:51:38 2009  memory use: 7429.6 MB
Tue Jan 12 11:49:07 2010  lanczos halted after 382076 iterations (dim = 24160377)
Tue Jan 12 11:49:53 2010  recovered 31 nontrivial dependencies
Tue Jan 12 11:49:54 2010  BLanczosTime: 3890746
Tue Jan 12 11:49:54 2010  
Tue Jan 12 11:49:54 2010  commencing square root phase
Tue Jan 12 11:49:54 2010  reading relations for dependency 1
Tue Jan 12 11:49:58 2010  read 12076814 cycles
Tue Jan 12 11:50:15 2010  cycles contain 30629470 unique relations
Tue Jan 12 11:59:09 2010  read 30629470 relations
Tue Jan 12 12:02:21 2010  multiplying 30629470 relations
Tue Jan 12 14:05:15 2010  multiply complete, coefficients have about 840.51 million bits
Tue Jan 12 14:05:21 2010  initial square root is modulo 34727179
Tue Jan 12 17:55:37 2010  sqrtTime: 21943
Tue Jan 12 17:55:37 2010  prp69 factor: 291983755553764871342375393389946327216860539710043646803168061464937
Tue Jan 12 17:55:37 2010  prp211 factor: 8455317738915029332836546129127934525635911633112049506484021189656732761477917928066642920655772761906174274194886739339117985369155731002748545164386439429680781748936209199967240680501700327506014575490435087
Tue Jan 12 17:55:37 2010  elapsed time 1102:31:34
So a rather disappointingly small factor; admittedly, it would have been an excitingly large record ECM. I've informed Sam.

Thanks to all the contributors.

Last fiddled with by fivemack on 2010-01-12 at 18:21
fivemack is offline   Reply With Quote
Old 2010-01-12, 18:23   #107
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

144668 Posts
Default

Maybe I should just have posted

Code:
74896795367581381053453969340505850368405148521712648155642697641617137495840
78672636860928716644050239630664362558150628953665700398945869384866268490148
58180742265583174681812610790077380746258911123185486992652565408092747860639
7795223205353346710841088467051069941033991331706718^2 = 19 mod (2^941-1)
which I think proves I have the factorisation without being of any use whatsoever to anybody else.

Last fiddled with by fivemack on 2010-01-12 at 18:24
fivemack is offline   Reply With Quote
Old 2010-01-12, 18:40   #108
FactorEyes
 
FactorEyes's Avatar
 
Oct 2006
vomit_frame_pointer

1011010002 Posts
Default

Quote:
Originally Posted by fivemack View Post
So a rather disappointingly small factor; admittedly, it would have been an excitingly large record ECM. I've informed Sam.
I don't apologize for p69 factors.

I really, really wouldn't apologize for a p69 factor of a 941-bit SNFS, were I to enjoy such a thing.

Nice!

Postscript: Are you out of the collaborative factoring business, or do you still plan to do the occasional 16e job? What was the peak memory usage during filtering?

Last fiddled with by FactorEyes on 2010-01-12 at 18:46
FactorEyes is offline   Reply With Quote
Old 2010-01-12, 18:45   #109
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

270716 Posts
Default

Congratulations! What is so bad about 69?

"wink-wink-nudge-nudge-say no more-say no more"
Batalov is offline   Reply With Quote
Old 2010-01-12, 19:03   #110
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

72148 Posts
Default

Congrats! Nice job to everyone involved!

Some scribbles on this napkin I have handy say that even if we were clairvoyant and used 69 digit optimal ECM parameters (~1.94e9 B1), we would have needed ~ 4 Gigaseconds to do ECM to t69 (and this on a top of the line workstation). 125 CPU years and still less than 1 chance in 3 of finding the factor... kinda puts things in perspective
bsquared is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Possible response to "only uploading is lawsuit-worthy." jasong jasong 3 2012-12-27 16:40
New Computation JohnFullspeed Miscellaneous Math 8 2011-07-13 10:54
New Pi Computation Record ldesnogu Lounge 11 2010-01-07 14:42
Value of computation fivemack Lounge 0 2008-09-05 20:23
Saving computation in ECM dave_dm Factoring 8 2004-06-12 14:18

All times are UTC. The time now is 01:42.


Sat Dec 10 01:42:51 UTC 2022 up 113 days, 23:11, 0 users, load averages: 1.26, 0.88, 0.79

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

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔