## Semi-OT FFT for multiplying

Expand Messages
• Hi (long time no write...): When one asks how to multiply big numbers, I think that the answer that the experts give is something like that: If the numbers are
Message 1 of 5 , Jan 15, 2004
• 0 Attachment
Hi (long time no write...):

When one asks how to multiply big numbers, I think that the answer that the experts give is something like that:

If the numbers are up to... in size, then make the usual binary multiplication;

from that point to <that> size choose <that> modular method; (or something else I don't remember very well :S)

and from that point on go doing the FFT method for multiplication.

Am I mistaken? If not, I want to know how is that FFT method and why it is recommended for the biggest numbers. I think that it can be to do a convolution in the discrete frequency domain, with DFT and IDFT to change domains (you can enter in details here, I think I know enough Fourier theory), but that process would be a lot slower... if it is done in this way, then what do we win? Accuracy?

It would be cool if you can send me good links to this material (also the multiplication of big numbers in general, but mostly using FFT for multiplication).

Thanks. Jose Brox
http://espanol.groups.yahoo.com/group/Telecomunicacion/

[Non-text portions of this message have been removed]
• ... Hash: SHA1 ... Yes, the FFT is the only to go when you re multiplying huge numbers. There s accuracy and speed gains. The FFT is an O(n log n) algorithm,
Message 2 of 5 , Jan 15, 2004
• 0 Attachment
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Thursday 15 January 2004 17:21, Jose Ramón Brox wrote:
> Hi (long time no write...):
>
> When one asks how to multiply big numbers, I think that the answer that the
> experts give is something like that:
>
> If the numbers are up to... in size, then make the usual binary
> multiplication;
>
> from that point to <that> size choose <that> modular method; (or something
> else I don't remember very well :S)
>
> and from that point on go doing the FFT method for multiplication.
>
> Am I mistaken? If not, I want to know how is that FFT method and why it is
> recommended for the biggest numbers. I think that it can be to do a
> convolution in the discrete frequency domain, with DFT and IDFT to change
> domains (you can enter in details here, I think I know enough Fourier
> theory), but that process would be a lot slower... if it is done in this
> way, then what do we win? Accuracy?

Yes, the FFT is the only to go when you're multiplying huge numbers.

There's accuracy and speed gains. The FFT is an O(n log n) algorithm, and so
is the IFFT. Convolution in the frequency domain is pointwise multiplication,
an O(n) task. So the FFTs dominate the cost, for a runtime of O(n log n). The
remainder of tasks are constant-time or O(n) at most.

Now schoolboy multiplication is O(n^2), but it starts off well (when the
number of digits is small) given the small constant implied in the O()
notation. But for a few thousand digits, FFT methods jump ahead.

However, you waste a lot of memory and the transform size is somewhat limited.
If you need to go very far (like billions of digits), you're better off with
a so-called Number Theoretical Transform (NTT). That's like a generalized
FFT, where you replace the complex roots of unity of the ordinary complex FFT
with primitive roots in Z/pZ for certain special form moduli p. The
convolution theorem holds in this domain, so the asymptotics are the same as
in the complex FFT case.

> It would be cool if you can send me good links to this material (also the
> multiplication of big numbers in general, but mostly using FFT for
> multiplication).

Have a look at www.bloodworth.org. Carey knows what he's doing. Xavier Gourdon
too; after all, he coded one of the fastest Pi computation programs on earth.
http://numbers.computation.free.fr/Constants/Algorithms/fft.html

C&P and Knuth vol. 2 are great references; C&P more so, IMO.

Alternatively, you could subscribe to the pi-hacks egroup. Some of the best
pratictioners in the field lurk there.

Décio
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.3 (GNU/Linux)

iD8DBQFABy/rFXvAfvngkOIRAoUtAJ948xFlAHZODlhLsbxfi6j+SgHB8ACaA8MT
KgGj740EpeqbNqzw9I9cNiI=
=my33
-----END PGP SIGNATURE-----
• ... Gourdon ... earth. ... I m familiar with Knuth ( The Art of Computer Programming, several volumes), but not C&P. Could someone tell me what authors and
Message 3 of 5 , Jan 17, 2004
• 0 Attachment
At 10:27 PM 1/15/04 -0200, Décio Luiz Gazzoni Filho wrote:

>Have a look at www.bloodworth.org. Carey knows what he's doing. Xavier
Gourdon
>too; after all, he coded one of the fastest Pi computation programs on
earth.
>http://numbers.computation.free.fr/Constants/Algorithms/fft.html
>
>C&P and Knuth vol. 2 are great references; C&P more so, IMO.

I'm familiar with Knuth ("The Art of Computer Programming," several
volumes), but not C&P. Could someone tell me what authors and book "C&P" is
shorthand for?

---
• ... Hash: SHA1 ... The book is Prime Numbers: A Computational Perspective, by Richard Crandall and Carl Pomerance (hence C&P). Since you don t have it, go grab
Message 4 of 5 , Jan 17, 2004
• 0 Attachment
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Saturday 17 January 2004 17:30, Ben Bradley wrote:
> I'm familiar with Knuth ("The Art of Computer Programming," several
> volumes), but not C&P. Could someone tell me what authors and book "C&P" is
> shorthand for?

The book is Prime Numbers: A Computational Perspective, by Richard Crandall
and Carl Pomerance (hence C&P). Since you don't have it, go grab it now!

<rant>
If the list newcomers checked C&P before posting their `newly-discovered'
algorithms here, so many junk postings would be avoided...
</rant>

Décio
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.3 (GNU/Linux)

iD8DBQFACY75FXvAfvngkOIRAnFSAJ9/qEs1hHVREuXo5SQ/T2ZC7hh9lwCeIT2R
Y+lXLcBCugSuMrkk/MVbyDg=
=JQ0C
-----END PGP SIGNATURE-----
• ... _Prime Numbers: A Computational Perspective_ by Richard Crandall and Carl Pomerance (Springer, 2001)
Message 5 of 5 , Jan 17, 2004
• 0 Attachment
On Sat, 17 Jan 2004, Ben Bradley wrote:
> I'm familiar with Knuth ("The Art of Computer Programming," several
> volumes), but not C&P. Could someone tell me what authors and book "C&P" is
> shorthand for?

_Prime Numbers: A Computational Perspective_ by Richard Crandall and Carl
Pomerance (Springer, 2001)
Your message has been successfully submitted and would be delivered to recipients shortly.