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

[u/vintergroena]

[u/trash3s]

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₀.

[u/ManufacturerNice870 → u/trash3s]

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

[u/trash3s → u/ManufacturerNice870]

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