Msieve 1.44 feedback - Page 3

jasonp · 2010-02-28, 03:16

Basically if the input is over about 145 digits, then each of the large and small ranges is split into a variable number of pieces, and one piece is chosen randomly to be searched for the large and small ranges. It does throw way a lot of the range, but most of the range was not searchable in a reasonable amount of time anyway (especially without a GPU). At the 155-digit input size, each range is split into 5 pieces, so you would need maybe 5 machines searching the same group of A5's before needing to worry about work being duplicated at random.

Once the ranges are chosen, p and q values are chosen inside them; I started out using a sieve, but that gets very slow for large problems, so degree 6 polynomials use explicit enumeration with pruning (it's enormously faster, and should be used most of the time for degree 5 too). The enumeration means that values are picked from all over the range in a haphazard order, but nothing in the search code really depends on things being sorted.

xilman · 2010-02-28, 09:37

Quote:

Originally Posted by jasonp

Basically if the input is over about 145 digits, then each of the large and small ranges is split into a variable number of pieces, and one piece is chosen randomly to be searched for the large and small ranges. It does throw way a lot of the range, but most of the range was not searchable in a reasonable amount of time anyway (especially without a GPU). At the 155-digit input size, each range is split into 5 pieces, so you would need maybe 5 machines searching the same group of A5's before needing to worry about work being duplicated at random.

Once the ranges are chosen, p and q values are chosen inside them; I started out using a sieve, but that gets very slow for large problems, so degree 6 polynomials use explicit enumeration with pruning (it's enormously faster, and should be used most of the time for degree 5 too). The enumeration means that values are picked from all over the range in a haphazard order, but nothing in the search code really depends on things being sorted.

Hint: coupon collector.

If you need more than a hint I'll post I'll post a more detailed explanation.

Paul

jasonp · 2010-02-28, 20:37

Paul, I'm afraid I've never had the patience to be good at puzzles...

xilman · 2010-02-28, 20:41

Quote:

Originally Posted by jasonp

Paul, I'm afraid I've never had the patience to be good at puzzles...

I'll PM you with the answer. Let's give others the chance to solve it for themselves.

Paul

Brian Gladman · 2010-02-28, 21:15

Quote:

Originally Posted by jasonp

Paul, I'm afraid I've never had the patience to be good at puzzles...

Also known as the 'classical occupancy problem' - see the attached

jasonp · 2010-02-28, 22:32

Note that in the case of poly selection we have two groups of ranges, each of which is split into pieces. Machines pick one choice for each range and search the combination for hits, so it's not immediately silly to set 5 machines loose on 25 combinations of search space.

PS: Brian, please tell me you didn't type that up just now :)

jrk · 2010-03-01, 00:00

Jason, that's a lot of cool improvements you've done in the last few days. I will check them out later.

Brian Gladman · 2010-03-01, 07:57

I wish, Jason!

In the UK the Sunday Times publishes a weekly puzzle and I run a Google Group called 'Sunday Times Teaser Solutions' where people discuss these puzzles.

A puzzle came up a couple of years ago involving this issue so I wrote up the maths behind the solution.

Brian

frmky · 2010-03-02, 03:07

I have a feature request. Can msieve keep two checkpoint files? That is, rather than overwriting an existing chk file, move an existing chk to ch2, then create a new chk?

I ask because I just had about the worst possible msieve scenario happen. The LA for 2,899- has been running since Jan. 30. Another process was recently started on the computer. Today, while writing the checkpoint, which apparently uses slightly more memory than just running the LA, the computer ran out of memory so the Linux kernel decided to kill msieve. In the middle of writing the checkpoint. So it is now corrupt. With about 130 hours remaining until completion. And of course this is on the scratch partition so there's no backup. Time to start over.

jasonp · 2010-03-02, 12:41

Yuck, I figured that was so rare that it wasn't worth worrying about. The changes are easy and I'll make them.

Can low-level disk access with 'dd' find the unlinked inodes and recover the file? It probably would not be overwritten on disk...

PS: split checkpoint writes now available in SVN

xilman · 2010-03-02, 14:00

Quote:

Originally Posted by jasonp

Can low-level disk access with 'dd' find the unlinked inodes and recover the file? It probably would not be overwritten on disk..

dd(1) is unlikely to be of much use. You could, I suppose, access the raw disk device and use a tool (grep(1) perhaps?) to look for disk blocks which look as if they might contain the data. However, recognizing the data, finding it all, and then putting it back together correctly is rather implausible IMO.

It's rather more likely that if something could be put together it would consist of the first portion of the second checkpoint followed by the second portion of the first. The reason being that if you open an existing file for writing its disk blocks are usually re-used.

Paul

2010-02-28, 03:16	#23
jasonp Tribal Bullet Oct 2004 3,541 Posts	Basically if the input is over about 145 digits, then each of the large and small ranges is split into a variable number of pieces, and one piece is chosen randomly to be searched for the large and small ranges. It does throw way a lot of the range, but most of the range was not searchable in a reasonable amount of time anyway (especially without a GPU). At the 155-digit input size, each range is split into 5 pieces, so you would need maybe 5 machines searching the same group of A5's before needing to worry about work being duplicated at random. Once the ranges are chosen, p and q values are chosen inside them; I started out using a sieve, but that gets very slow for large problems, so degree 6 polynomials use explicit enumeration with pruning (it's enormously faster, and should be used most of the time for degree 5 too). The enumeration means that values are picked from all over the range in a haphazard order, but nothing in the search code really depends on things being sorted. Last fiddled with by jasonp on 2010-02-28 at 03:19

2010-02-28, 22:32	#28
jasonp Tribal Bullet Oct 2004 DD5₁₆ Posts	Note that in the case of poly selection we have two groups of ranges, each of which is split into pieces. Machines pick one choice for each range and search the combination for hits, so it's not immediately silly to set 5 machines loose on 25 combinations of search space. PS: Brian, please tell me you didn't type that up just now :) Last fiddled with by jasonp on 2010-02-28 at 22:33

2010-03-02, 12:41	#32
jasonp Tribal Bullet Oct 2004 3541₁₀ Posts	Yuck, I figured that was so rare that it wasn't worth worrying about. The changes are easy and I'll make them. Can low-level disk access with 'dd' find the unlinked inodes and recover the file? It probably would not be overwritten on disk... PS: split checkpoint writes now available in SVN Last fiddled with by jasonp on 2010-03-02 at 13:19

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Msieve 1.53 feedback	xilman	Msieve	149	2018-11-12 06:37
Msieve 1.50 feedback	firejuggler	Msieve	99	2013-02-17 11:53
Msieve 1.43 feedback	Jeff Gilchrist	Msieve	47	2009-11-24 15:53
Msieve 1.42 feedback	Andi47	Msieve	167	2009-10-18 19:37
Msieve 1.41 Feedback	Batalov	Msieve	130	2009-06-09 16:01

2010-02-28, 20:37	#25
jasonp Tribal Bullet Oct 2004 3,541 Posts	Paul, I'm afraid I've never had the patience to be good at puzzles...

2010-03-01, 00:00	#29
jrk May 2008 1095₁₀ Posts	Jason, that's a lot of cool improvements you've done in the last few days. I will check them out later.

2010-03-01, 07:57	#30
Brian Gladman May 2008 Worcester, United Kingdom 2²·7·19 Posts	I wish, Jason! In the UK the Sunday Times publishes a weekly puzzle and I run a Google Group called 'Sunday Times Teaser Solutions' where people discuss these puzzles. A puzzle came up a couple of years ago involving this issue so I wrote up the maths behind the solution. Brian

2010-03-02, 03:07	#31
frmky Jul 2003 So Cal 2×3⁴×13 Posts	I have a feature request. Can msieve keep two checkpoint files? That is, rather than overwriting an existing chk file, move an existing chk to ch2, then create a new chk? I ask because I just had about the worst possible msieve scenario happen. The LA for 2,899- has been running since Jan. 30. Another process was recently started on the computer. Today, while writing the checkpoint, which apparently uses slightly more memory than just running the LA, the computer ran out of memory so the Linux kernel decided to kill msieve. In the middle of writing the checkpoint. So it is now corrupt. With about 130 hours remaining until completion. And of course this is on the scratch partition so there's no backup. Time to start over.