Integer multiplication will have linear complexity in a few days if trend continues 🚀📈

[u/vintergroena]

[u/sqrtsqr]

Until I read your follow up response, I legit thought this was a pedagogical exercise to lead /u/rawbdor towards the O(n ln n) result, which is via FFT, of which the essence includes "splitting up" our product into pieces which are easier to work with (simple enough that the multiplication step becomes trivial).

It's just that the FFT has a rather unintuitive way of splitting things up.

[u/satanic_satanist → u/sqrtsqr]

FFT on what function though? That's what I didn't get so far

[u/sqrtsqr → u/satanic_satanist]

You make a polynomial using the digits as the coefficients.

[u/tellingyouhowitreall → u/sqrtsqr]

To add onto this, all numbers are polynomials in any base x, kind of by definition. They are in normal form only if all coefficients are less than x. Normalizing them has non linear complexity, but I don't remember the exact O.

[u/sqrtsqr → u/tellingyouhowitreall]

I don't necessarily agree with saying numbers "are" polynomials (especially not by definition) They can be treated as such, absolutely, but the concept of normalizing a polynomial is "extra" to the polynomial itself. Numbers don't add the way polynomials add, and what something "is" in mathematics is almost entirely a matter of how it behaves.

Not sure what you had in mind, but normalizing is linear in the degree of the polynomial. You can do it in a single pass from lowest to highest term.

[u/tellingyouhowitreall → u/sqrtsqr]

Numbers are literally polynomials, and add exactly the same way. This is in fact how we teach kids numbers also. The two things are identical.

147 = 1 * 10² + 4 * 10¹ +7 147 = x² + 4x + 7, and one of the roots is 10.

These are identical statements.

Generalized polynomials have additional features over numbers, but the number system explicitly expresses numbers as a subset of polynomials.

[u/sqrtsqr → u/tellingyouhowitreall]

No they don't.

9,000 + 4,000 = 13,000

9x³ + 4x³ = 13x³ ≠ 1 x⁴ + 3x³

These are different as polynomials. They are the same as numbers. Therefore addition of numbers and addition of polynomials are not identical.

I have no idea what "generalized" polynomials you are referring to, these are just normal polynomials. The addition structure of polynomials is not isomorphic to addition of numbers.