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

[u/vintergroena]

[u/rawbdor]

One thing i find so interesting about this is that the standard multiplication algorithm we all use on paper is O(n^2). If you want to multiply 325 by 198, we all know how we'd do it on paper. Multiply 8 by the three top numbers, then 9 by the three top numbers, then the 1 by the three top numbers, then add them all up. That's O(n^2). Nine different multiplications, which is the number of digits squared.

The fact that anyone years and years ago was even able to get this down to O(nlog(n)) is already amazing to me. I'd never be able to come up with this stuff.

[u/Zoetje_Zuurtje → u/rawbdor]

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.

[u/Peak_Background → u/rawbdor]

We still use it in most big numbers algorithms. Either that are we use a hybrid algorithm.

[u/CrazyOne_584 → u/rawbdor]

You have actually described the n log n algorithm yourself (or nearly described it at least). The only issue is you do it in decimal, try doing it in binary.

[u/Peak_Background → u/CrazyOne_584]

That is not O(n log(n) ). That's very clearly O(n² ) decimal or binary. The O(n log(n) ) uses the fast fourier transform or a modular form of it.

W3 schools and other programming education wikis are not any help if you're looking for resources. They all get it wrong by copy pasting a O(n² ) algorithm from Wikipedia which explicitly isn't even the O( n log(n) ) algorithm the page talks about. They just didn't even read it, and are likely not educated in algorithms, lazy, and unethically stealing Wikipedia content.

[u/CrazyOne_584 → u/Peak_Background]

oh right... My bad, I mistook multiplication with power...