43 ms·

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

by 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.
        antonfire 6y ago
        Fun fact, you can construct and store a lookup table for sums of all possible pairs of O(log(n))-digit numbers in O(n) space. (And O(n) time, probably?) So if your model of computation lets you look things up in a table like that in O(1) time, you can kind of get the situation I'm describing above. Maybe your model of computation shouldn't let you do this, but some do. Often if an algorithm takes up O(foo) space, we don't worry about the fact that lookups into that space should take Theta(log(foo)) time (to even read the address) rather than O(1) time, because things are assumed to "fit into memory". Another fun way to be fussy along these lines is that the usual algorithms for sorting a list of n distinct items only give bounds of O(n (log n)^2) time. Each item takes around log(n) bits to even store, so comparing two of those can't be done in time O(1) in the worst case (in a model that forbids the kind of "cheating" I'm describing above). The best uniform bound you can hope for is time O(log n) per comparison. (Though in some sense the extra log(n) factor might "drop back out", because it takes O(n log(n)) space to even write down an input to this algorithm.)

by nickcw 6y ago

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.
        antonfire 6y ago
        Fun fact, you can construct and store a lookup table for sums of all possible pairs of O(log(n))-digit numbers in O(n) space. (And O(n) time, probably?) So if your model of computation lets you look things up in a table like that in O(1) time, you can kind of get the situation I'm describing above. Maybe your model of computation shouldn't let you do this, but some do. Often if an algorithm takes up O(foo) space, we don't worry about the fact that lookups into that space should take Theta(log(foo)) time (to even read the address) rather than O(1) time, because things are assumed to "fit into memory". Another fun way to be fussy along these lines is that the usual algorithms for sorting a list of n distinct items only give bounds of O(n (log n)^2) time. Each item takes around log(n) bits to even store, so comparing two of those can't be done in time O(1) in the worst case (in a model that forbids the kind of "cheating" I'm describing above). The best uniform bound you can hope for is time O(log n) per comparison. (Though in some sense the extra log(n) factor might "drop back out", because it takes O(n log(n)) space to even write down an input to this algorithm.)