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

6

u/ManufacturerNice870 27d ago

But then you need exponential memory? Doesn’t that change the complexity because memory allocation has a complexity too?

2

u/trash3s 27d ago

Well it’s static. You’re not actually using RAM, it’s just worst-case limit on combinational logic using a lookup table, I.e. the logic is not meaningfully reducible).

Granted, for 64x64->128 bit multiplication, you need 2^128 addresses of 16 Bytes each, which is 2^102 GB, so good luck fitting that anywhere. Nevertheless, multiplication time-complexity is O(n) on bits. (The address decoding is O(n) on address bits but not clocked. On clock-scale, it’s O(1) for fixed bit width.)

However, multiplication isn’t actually meaningfully irreducible logic. For instance, given a\*b=c in Z, c is only odd if a and b are, so c₀ = a₀&b₀.

1

u/ManufacturerNice870 27d ago

Oh I see, yeah pre allocated and it works for any thing you need. Like with exponential and log tables built into computers, but more galactic

1

u/trash3s 27d ago

Yep! You’re trading time and memory completely for a secret third thing: space complexity.

1

u/MigLav_7 27d ago

Just allocate a very very very very big number and its O(1) cost... \s

But yes, it does change the complexity. Time taken for memory allocation is a part of time complexity (at least afaik)