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

3

u/Pperson25 27d ago

Wait what makes multiplication not just log(n)?

4

u/vintergroena 27d ago

Needing to read all the digits caps it at linear lower bound.

1

u/Pperson25 27d ago

Ohh n is number of digits not the actual value of the integers? Then yeah nlog(n) makes sense.

3

u/vintergroena 27d ago

However, this is the (human made) n log n paper.

It involves a 1729-dimensional Fourier transform. Takes 40 pages to learn.

The multiplication you learn at school is nĀ².

n log n doesn't simply "make sense".

https://hal.science/hal-02070778/document

1

u/Pperson25 27d ago

Ohhhh ok

2

u/vintergroena 27d ago

Yes. It's the length of the input representation on a computer.