81–90 of 152 posts
Earlier quoted context omitted.
I disagree. 1 step is a finite sequence of instructions.
The lookup table is part of the algorithm, and is not finite. In general any problem can be solved in 1 step with a lookup table, so here you go P=NP solved.
Earlier quoted context omitted.
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.
>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.
Earlier quoted context omitted.
The lookup table is part of the algorithm, and is not finite. In general any problem can be solved in 1 step with a lookup table, so here you go P=NP solved.
It doesn't have to be part of the algorithm. It all depends on how you measure it.
Why do we make computers multiply single digit numbers, instead of taking the result from a lookup table, like humans do? To answer my own question, I am assuming it would be because multiplying would still be faster than reading from a lookup table? Any ideas?
Even if it isn’t, it still would be a lot cheaper. With 32-bit integers, the lookup table would have 2⁶⁴ 64-bit values. If my math six right, that is 128 exabytes of read-only memory. With 64-but integers, it truly would be impractical, at 2¹²⁸ 128-bit values.
Back in 2024, I was trying to optimize PostgreSQL's NUMERIC data type, which is base-10000, using Karatsuba. The problem of finding the optimal threshold of when to switch to Karatsuba turned out to be really hard, since it depends on the size of both factors combined. After some hundreds of hours, I gave up, and started thinking about if there could be a simpler solution. I came to think about another idea I'd had b…
A bit tangential, but the folks behind the GNU Multiple Precision Library (GMPLib) have the problem of choosing algorithms more or less fleshed out. They've got some fairly approachable manual pages[1] for the various algorithms they use as operand sizes scale up, where Karatsuba is only the second of six options in terms of operational complexity. [1] https://gmplib.org/manual/Multiplication-Algorithms
Why do we make computers multiply single digit numbers, instead of taking the result from a lookup table, like humans do? To answer my own question, I am assuming it would be because multiplying would still be faster than reading from a lookup table? Any ideas?
> I am assuming it would be because multiplying would still be faster than reading from a lookup table? Even if it isn’t, it still would be a lot cheaper. With 32-bit integers, the lookup table would have 2⁶⁴ 64-bit values. If my math six right, that is 128 exabytes of read-only memory. With 64-but integers, it truly would be impractical, at 2¹²⁸ 128-bit values.
We can likely use different number representations for faster results. E.g. numbers in the form of coefficients to prime factors can be multipled at O(n) time, right?
You mean like those guaranteed-always-compresses-by-at-least-one-bit algorithm patents gzip page made fun of? In your case, doing prime factoring is where the cost would be, wouldn't it?
Okay. No problem.
(ad + bc) = d + d .. + d + c + c .. + c
There we go, zero multiplications.