3 ms·
This would be the solution for any problem/algorithm, wouldn't it? Factorize big numbers, sort an array, beat stockfish at chess, create a SOTA microkernel OS
by bmacho 3mo ago
This would be the solution for any problem/algorithm, wouldn't it?
Factorize big numbers, sort an array, beat stockfish at chess, create a SOTA microkernel OS from English description. All O(1) with lookup table!
It's not how complexity works.
- charcircuit 3mo ago>This would be the solution for any problem/algorithm, wouldn't it? Yes, but it suffers from a large amount of space complexity, and probably would have high constant factors in practice.
- bmacho 3mo agoExactly. So what I wrote debunks your assumptions and proves your argument wrong. This is how conversations normally go.
- charcircuit 3mo agoWhat you wrote agreed with me. >All O(1) with lookup table!
- boomlinde 3mo agoUsing e.g. a single zettabit-sized look-up table to give the 64-bit result of a multiplication of two 32-bit numbers suffers from a similar problem. But if we're talking about practical concerns there are already faster methods than random access in >100 exabytes of memory. And if we're talking theoretical concerns your answer still hasn't addressed the question of how to multiply numbers fast.