Running Msieve - Page 23

ewmayer · 2008-03-19, 19:33

Jason, another pair of data points: Mlucas' exponent limit for 28672Kdouble FFTs is 519932856, and for 30720K the limit is 556194824, which bracket your figure of 512 megabits [assuming by that you mean 512 *2^20.]

Are you using balanced digits for these?

akruppa · 2008-03-19, 19:49

You could try a Schönhage-Strassen multiplication on top of the complex FFT. A basic implementation should be very easy to write and yet would be sufficient to eliminate problems with input size. If your complex DWT for multiplication modulo (2^N+1) allows, say, N=2^20, you could use a transform length of 2^22 for Schönhage-Strassen and so should be able to multiply two numbers of up to 2^40 bits each.

[/shame][plug]In case you're interested, I know of a recent publication on the subject.

[/plug][shame]

Alex

jasonp · 2008-03-20, 02:35

Ernst, the code does use balanced representation. I could possibly get an extra power of two by using a complete list of premultiplied twiddle factors, instead of the two-square-root-size-plus-one-multiply table as was used in the F24 code, but that would double the already excessive memory use.

Alex, I've read the paper and was quite impressed. Even easier than implementing Schonhage-Strassen is to make the large-integer portion of msieve depend on GMP :) A middle ground would be to implement something like the nice system of multi-prime NTTs with CRT reconstruction as used in GMP-ECM. It's been something I've wanted to do for a long time, and makes multithreading and saving intermediate results to disk very easy.

2008-03-19, 19:33	#243
ewmayer ∂²ω=0 Sep 2002 República de California 103×113 Posts	Jason, another pair of data points: Mlucas' exponent limit for 28672Kdouble FFTs is 519932856, and for 30720K the limit is 556194824, which bracket your figure of 512 megabits [assuming by that you mean 512 2^20.] Are you using balanced digits for these? Last fiddled with by ewmayer on 2008-03-19 at 19:35*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
error when running msieve 1.53 with cuda	aein	Msieve	9	2019-02-25 14:09
Help need to running Msieve	appleseed	Msieve	12	2016-04-10 02:31
Problem in running msieve with CUDA	mohamed	Msieve	20	2013-08-01 08:27
CUDA_ERROR_LAUNCH_OUT_OF_RESOURCES when running msieve 1.5.0 with CUDA	ryanp	Msieve	3	2012-06-12 03:27
Trouble Running Msieve	Sab	Msieve	4	2009-07-07 06:19

2008-03-19, 19:49	#244
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	You could try a Schönhage-Strassen multiplication on top of the complex FFT. A basic implementation should be very easy to write and yet would be sufficient to eliminate problems with input size. If your complex DWT for multiplication modulo (2^N+1) allows, say, N=2^20, you could use a transform length of 2^22 for Schönhage-Strassen and so should be able to multiply two numbers of up to 2^40 bits each. [/shame][plug]In case you're interested, I know of a recent publication on the subject. [/plug][shame] Alex

2008-03-20, 02:35	#245
jasonp Tribal Bullet Oct 2004 3,541 Posts	Ernst, the code does use balanced representation. I could possibly get an extra power of two by using a complete list of premultiplied twiddle factors, instead of the two-square-root-size-plus-one-multiply table as was used in the F24 code, but that would double the already excessive memory use. Alex, I've read the paper and was quite impressed. Even easier than implementing Schonhage-Strassen is to make the large-integer portion of msieve depend on GMP :) A middle ground would be to implement something like the nice system of multi-prime NTTs with CRT reconstruction as used in GMP-ECM. It's been something I've wanted to do for a long time, and makes multithreading and saving intermediate results to disk very easy.