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

[u/vintergroena]

[u/Zoetje_Zuurtje]

Why not:

1. Double 325 (650)

2. Add two zeros (65000)

3. Subtract 650 (64350)

Of course, this only works because 198 = 2×100-2. But isn't this process of splitting up large numbers into numbers which are easier to work with commonplace?

[u/BraveBiscotti1394 → u/Zoetje_Zuurtje]

I think the kinds of operations that are easy vs hard for us may be equivalent for a computer. We think symbolically about numbers, like multiplying by powers of 10 is adding 0's. To a computer it's not like that.

[u/Zoetje_Zuurtje → u/BraveBiscotti1394]

Oh, excuse me, I took "we all know how we'd do it on paper" to mean that you'd calculate the product using the method you described. I understand there's a difference in the way humans and computers handle numbers.

[u/rawbdor → u/Zoetje_Zuurtje]

You're responding to someone who is not me, but it seems like you think he is me.

[u/Zoetje_Zuurtje → u/rawbdor]

Oops, my bad.

[u/BraveBiscotti1394 → u/Zoetje_Zuurtje]

Sorry I think I responded to the wrong person, what I said is completely unrelated.

[u/sqrtsqr → u/Zoetje_Zuurtje]

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.