Loading ...
Sorry, an error occurred while loading the content.

Semi-OT FFT for multiplying

Expand Messages
  • Jose Ramón Brox
    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]
    • Décio Luiz Gazzoni Filho
      ... 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-----
      • Ben Bradley
        ... 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?

          ---
          http://mindspring.com/~benbradley
        • Décio Luiz Gazzoni Filho
          ... 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-----
          • Carl Devore
            ... _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.