[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.

[antonfire]

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.