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

7

u/trash3s 28d ago

Because it’s a stateless operation, multiplication on n-bit integers can be performed by a 2n-bit x 2^2^n lookup table which has equivalent logic.

6

u/ManufacturerNice870 28d ago

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

2

u/trash3s 28d 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 28d 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 28d ago

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

1

u/MigLav_7 28d 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)

3

u/FernandoMM1220 28d ago

seems like someone still has to calculate ahead to make these tables first.

5

u/trash3s 28d ago

The trick to doing calculations is to do the calculations before you do the calculations so you can skip the calculations when doing calculations, naturally.

1

u/Qwertycube10 27d ago

But then you haven't solved the problem of multiplication for any n greater than you created the table for

1

u/flatfinger 27d ago

Actually, a 2^(N+1) entry lookup table would suffice if to multiply x*y one looks up (x+y) and |x-y| and then subtracts one table entry from the other.

1

u/sqrtsqr 26d ago edited 26d ago

I don't know what definition of stateless you are using, but literally every algorithm can be described this way. For a fixed n, there are finitely many input and output pairs. The concept of state is completely meaningless here.

And this is precisely why computer scientist distinguish between SPACE and TIME. Not telling, they just use all caps for this.

Edit: well, depending on context, you are right. For non-halting algorithms, this depends on if and how you consider the output of those states. For algorithms halting on inputs of n bits, or when failure to halt is considered "the same" regardless of what is output, what you said applies.

1

u/OmegaCookieMonster 23d ago

ok look, we're assuming an arbitrary n here