Re: caching of transforms used for large multiplications

2013-06-15 Thread Niels Möller
Daniel Lichtblau d...@wolfram.com writes: I'm fairly sure readers will understand that no offense was intended. Well, on a public and technical mailing list, jokes at the expense of other developers are not appropriate. Except possibly when you hold a *correct* belief that the subject of the

Re: caching of transforms used for large multiplications

2013-06-14 Thread Philip McLaughlin
Daniel Lichtblau wrote: That said, I confess I am not sure there is much need for this outside of subquadratic gcd code. If it is not more generally useful, then I guess this automation would only be of benefit to a limited set of users. (Like, maybe four of us.) Years ago I published a

Re: caching of transforms used for large multiplications

2013-06-14 Thread Torbjorn Granlund
Daniel Lichtblau d...@wolfram.com writes: If you do not manage to locate them I can scan and send a pdf. (Least I can do for someone who shared a room for two months with that Torbjörn fellow..) I started to write a reply, but decided against sending it after I read this unprovoked

Re: caching of transforms used for large multiplications

2013-06-14 Thread Daniel Lichtblau
On 06/14/2013 02:27 PM, Torbjorn Granlund wrote: Daniel Lichtblaud...@wolfram.com writes: If you do not manage to locate them I can scan and send a pdf. (Least I can do for someone who shared a room for two months with that Torbjörn fellow..) I started to write a reply, but decided

Re: caching of transforms used for large multiplications

2013-06-14 Thread Daniel Lichtblau
On 06/14/2013 12:02 PM, Philip McLaughlin wrote: Daniel Lichtblau wrote: That said, I confess I am not sure there is much need for this outside of subquadratic gcd code. If it is not more generally useful, then I guess this automation would only be of benefit to a limited set of users.

Re: caching of transforms used for large multiplications

2013-06-14 Thread Torbjorn Granlund
Daniel Lichtblau d...@wolfram.com writes: I simply have no idea why you would choose to take such offense. If it serves any purpose, it is one I quite fail to see. That said, I'll not trouble you with further communication. If you cannot assume a professional attitude on the GMP lists,

Re: caching of transforms used for large multiplications

2013-06-13 Thread Niels Möller
Daniel Lichtblau d...@wolfram.com writes: Re GCD usage, mostly I had in mind the matrix multiplications (which I believe are balanced) and a few others that, You may want to have a look at http://gmplib.org:8000/gcd-nisse/file/tip/mpn/generic/matrix22_mul.c. This code reuses transforms, and it

Re: caching of transforms used for large multiplications

2013-06-13 Thread Daniel Lichtblau
On 06/13/2013 04:50 AM, Niels Möller wrote: Daniel Lichtblaud...@wolfram.com writes: Re GCD usage, mostly I had in mind the matrix multiplications (which I believe are balanced) and a few others that, You may want to have a look at

Re: caching of transforms used for large multiplications

2013-06-12 Thread Niels Möller
Daniel Lichtblau d...@wolfram.com writes: My question(s): Are these NTT intermediate results cached? No. I have a tentative interface for this in my small-prime fft code which haven't yet been integrated with gmp. I think Paul Zimmermann may also have some patches along those lines for the

Re: caching of transforms used for large multiplications

2013-06-12 Thread Daniel Lichtblau
Niels, Torbjorn, Thank you both for your detailed responses. Re GCD usage, mostly I had in mind the matrix multiplications (which I believe are balanced) and a few others that, if memory serves, are not woefully unbalanced. Possibly one value would be a factor of two larger in size than the

caching of transforms used for large multiplications

2013-06-11 Thread Daniel Lichtblau
[This is a slightly revised version of a question I raised in direct email. Sending to list per moderator suggestion. Possibly I should have known to do that to begin with, but there was a nagging suspicion that the question might be off base.] This is in regard to operations that arise with

Re: caching of transforms used for large multiplications

2013-06-11 Thread Torbjorn Granlund
Hello Daniel! We don't yet have any transform-only interface in GMP, but this will probably change at some point. The current FFT code uses coefficient rings mod 2^m+1, as per the Schönhage-Strassen algorithm. In this algorithm, m = O(sqrt(n)) where n = O(log(a) + log(b)) for multiplication of