[phaker]

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 algorithms are based on FFT and why everyone was looking for O(n log n) one, which was found like a year ago.

(Though from what i can tell in "Faster Convolutions" section the article claims you can easily build O(n log n) multiplication using FFT which doesn't work as it ignores carries)

[nickcw]

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]

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

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]

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]

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

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]

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]

Those are equivalent statements.

[rualca]

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

Let me show you some things: https://en.wikipedia.org/wiki/Multiplication_algorithm#Fouri... https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strasse...

[antonfire]

What's 111111111*111111111?