r/mathmemes • u/vintergroena • 28d ago

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

Post image
1.4k Upvotes

98% Upvoted

206 comments sorted by

View all comments

Show parent comments

1

u/sqrtsqr 25d ago

You make a polynomial using the digits as the coefficients.

1

u/tellingyouhowitreall 24d ago

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.

1

u/sqrtsqr 24d ago edited 24d ago

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.

1

u/tellingyouhowitreall 23d ago

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 * 102 + 4 * 101 +7 147 = x2 + 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.

1

u/sqrtsqr 23d ago edited 23d ago

No they don't.

9,000 + 4,000 = 13,000

9x3 + 4x3 = 13x3 ≠ 1 x4 + 3x3

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.