4. The strategy used.
I'll now describe the strategy I ended up settling on. But first some
notation to make this simpler.
Suppose I have a convolution length 2*n where n is a power of 2. A
standard Fermat transform with coefficients mod p = 2^{w*n}+1 can
support such a transform length. Here 2^w
3. Why a new FFT?
The timings I just posted probably justify writing a new FFT. However
that is not what concretely motivated me to write one.
I began thinking about writing a new FFT about the end of September
this year. At the time I skimmed through a huge number of papers on
the FFT for someth
I've done some more timings. This time I turned off MPIR's sqrt2 trick
which I don't have yet.
For some multiplications this causes MPIR to take way too long due to
tuning issues. For example, there are points where larger numbers take
less time to multiply.
I made a comparison showing how much f
2. FFT's for nitwits (like me)
I will explain why I am a nitwit in a later section. But to understand
that, you need to understand some FFT basics first. So I describe them
here.
2a. Description of the FFT
===
An FFT is not an integer multiplication routine p
1. Formal release of code.
I have included two new files in the top source directory of mpir in
svn. The first is new_fft_with_flint.c, the second new_fft.c. They are
isomorphic except that the second does not need to be linked against
FLINT to run. There will be no difference in timings or result
On Thu, Dec 31, 2009 at 9:04 PM, Bill Hart wrote:
> As the code for this FFT is quite involved, I plan to incrementally
> release a set of notes about it, starting tomorrow morning (today
> already), which may take hours to days for me to complete. I got the
> code working for the first time this
As the code for this FFT is quite involved, I plan to incrementally
release a set of notes about it, starting tomorrow morning (today
already), which may take hours to days for me to complete. I got the
code working for the first time this afternoon, so please be patient
with me.
Here is the rough
Ha! I forgot to mention, those numbers represent the size of the
integers in bits. I multiply two different integers with the same
number of bits, though that is not a limitation of the code. It will
accept integers of different lengths and adjust accordingly.
Bill.
2010/1/1 Bill Hart :
> I re-ti
I re-timed that point and I believe I may have just mistranscribed it.
Here it is with the corrected time. Thanks for pointing it out!
I've also included some times from the FLINT FFT, though only
non-truncated ones (i.e. where FLINT uses a convolution which is an
exact power of 2 length - not a l
It's either a tuning issue or timing instability on the machine.
Bill.
On 31/12/2009, Robert Gerbicz wrote:
> Hi!
>
> How is it possible that to multiple longer numbers takes less time, for
> example:
>
> 12546048: 14.7s / 15.3s
> 13591552: 14.0s / 14.2s
>
> --
>
> You received this message beca
Hi!
How is it possible that to multiple longer numbers takes less time, for
example:
12546048: 14.7s / 15.3s
13591552: 14.0s / 14.2s
--
You received this message because you are subscribed to the Google Groups
"mpir-devel" group.
To post to this group, send email to mpir-de...@googlegroups.com
Happy New Year!
I've written a new FFT for integer multiplication for MPIR. I'll write
a series of posts over the next couple of days describing the
strategy, what remains to be done, etc.
To whet your appetite, I include some timings for multiplying various
sized integers.
There is a trick call
12 matches
Mail list logo
