6 ms·

And multiplication is a fancy convolution (with carries). Fast convolution algorithms use FFT and run in O(n log n) time, which is why fast multiplication algo

• nickcw 6y ago
  You can build a O(n log n) multiplication with FFT based convolutions. The trick is to only put as many bits into each number as are guaranteed not to overflow. So if the convolution is n long and you put B bits in to each "digit" then the output needs to be able to hold log(n)+2*B bits. So if your convolution is done with double precision with 56 bits of precision and n = 1 million, log(n) = 20 so you put (56 -20)/2 = 18 bits into each "digit". You do your convolution, and ripple the carries at the end. This is the way Prime95 does its maths, though it uses a IBDWT which through a bit of extra maths magic halves the length of the FFT needed. While it is rippling the carries at the end it checks to see if each number is pretty nearly an integer - if it isn't them something has gone wrong and it blows up with "FATAL ERROR: Rounding was 0.5, expected less than 0.4".
  • xiphias2 6y ago
    Good luck trying to explain this 43 paper the parent comment was refering to in a HN comment: https://hal.archives-ouvertes.fr/hal-02070778/document https://hal.archives-ouvertes.fr/hal-02070778/document Basically, you can't. It's the overflows that make it so hard. It's complex, even though we all had the intuition that it should be done (and it should be simple to do)
  • SamReidHughes 6y ago
    This requires padding out an O(n)-digit number to memory size O(n log n), with addition operations of numbers with log(n) bits deemed to take O(1) time. If this is allowed by your model of computation, then you could use this magical O(1) addition to to implement multiplication in O(n).
    • antonfire 6y ago
      > If this is allowed by your model of computation, then you could use this magical O(1) addition to to implement multiplication in O(n). How's that?
      • SamReidHughes 6y ago
        For example, starting from decimal representation, you can calculate the product of five digit numbers, ("abcde" * "fghij") with the following, where capitalized variables X and S are the magic O(1)-addition integer types: let X = to_magic_integer("abcde") let y = "fghij".reverse() let S = to_magic_integer("0") for d = 0 to 4 for i = 1 to y[d] S += X end X = X+X+X+X+X + X+X+X+X+X end return S (You can implement to_magic_integer with basically the same algorithm in O(n).)
        • antonfire 6y ago
          The premise was > addition operations of numbers with log(n) bits deemed to take O(1) time. not > addition operations of numbers with n bits deemed to take O(1) time.
          • SamReidHughes 6y ago
            Those are equivalent statements.
            • antonfire 6y ago
              Do you interpret both as > addition operations of numbers with an arbitrary number of bits deemed to take O(1) time ? I was picturing a more restrictive model of computation in which your claim is along the lines of > There's an O(n)-time algorithm, which, given two numbers with n digits and a magic black box that can add log(n)-digit numbers together in O(1) time, will output the product of those two numbers.
              • 6y ago
• rualca 6y ago
  > And multiplication is a fancy convolution (with carries). It really isn't. Just because you see different digits being multiplied that doesn't mean you're convolving functions.
  • knappa 6y ago
    Let me show you some things: https://en.wikipedia.org/wiki/Multiplication_algorithm#Fourier_transform_methods https://en.wikipedia.org/wiki/Multiplication_algorithm#Fouri... https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strasse...
  • antonfire 6y ago
    What's 111111111*111111111?