- 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] - -----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----- - 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

I'm familiar with Knuth ("The Art of Computer Programming," several

>

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

volumes), but not C&P. Could someone tell me what authors and book "C&P" is

shorthand for?

---

http://mindspring.com/~benbradley - -----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----- - On Sat, 17 Jan 2004, Ben Bradley wrote:
> I'm familiar with Knuth ("The Art of Computer Programming," several

_Prime Numbers: A Computational Perspective_ by Richard Crandall and Carl

> volumes), but not C&P. Could someone tell me what authors and book "C&P" is

> shorthand for?

Pomerance (Springer, 2001)