Earlier quoted context omitted.
Printing it on paper and manually looking it up is probably cheaper with today’s ram-prices
The problem is that you also need multiplication to implement OCR.
Recursion is such a beautiful thing
Mathematicians still don't know the fastest way to multiply numbers
121–130 of 152 posts
Re: Mathematicians still don't know the fastest way to multiply numbers
#122Earlier quoted context omitted.
I am against statements like: A: "X people don't know how to do Y" B: "Why not do Z?" A: "Z is too easy and boring so they actually added more restrictions to how you are allowed to do Y so that solution doesn't count"
Maybe I'm not communicating the point clearly. In order to use a table to do the whole multiplication it has to be much larger than the largest number you would want to multiply with it. A lot of the analysis of algorithms, especially multiplication as discussed here, is about astronomically large numbers, so you don't want the existence of an even more astronomically large table as a prerequisite.
We are talking about mathematicians. We are not talking about computer engineers trying to implement a physical GPU that can multiply matrices as fast as possible. You don't have to physically build the astronomically look up table by hand. One can simply state that it exists. Proofs do not have to be clean to be a proof. You might not "want" something in a proof, but if it works then it works.
Re: Mathematicians still don't know the fastest way to multiply numbers
#123Earlier quoted context omitted.
True but addition becomes a lot less efficient in this representation :)
To make both addition and multiplication O(n), you can store numbers as their residues modulo a bunch of different primes and appeal to the Chinese Remainder Theorem. However, then size comparison becomes difficult.
I think the problem comes when you do a multiplication and you need more primes for uniqueness.
Re: Mathematicians still don't know the fastest way to multiply numbers
#124Earlier quoted context omitted.
This is a problem I have a lot in modern programming ecosystems: How do I tell the difference between a library written by a team of experts who have spent decades optimizing everything to do with the task and a library written by one guy that's an unnecessary straightforward wrapper over the obvious implementation?
Or increasingly, a library written by an LLM referencing a pile of such “one guy” projects of varying levels of suck (from actually good to good-got-it-is-full-of-suck).
What I have been seeing recently is having a great LLM rewrite the library leads to fewer bugs and also optimized for your use case. More expensive for sure than pulling something like epub.js but when the library has infinite open issues it can be a lot better.
Re: Mathematicians still don't know the fastest way to multiply numbers
#125Earlier quoted context omitted.
It's still a modified base 4, because the significance of the i'th digit is 4^i, not 5^i. Edited to add: I'm also not sure whether real-life implementations have -0 as an option. Of course -0 could be normalized to +0, but it might be cheaper not to bother if the sign is applied after the digit selection.
No, balanced ternary, for example, uses {-1, 0, 1}. The system you're discussing is balanced quinary (base 5). https://en.wikipedia.org/wiki/Signed-digit_representation
It isn't balanced quinary, but rather redundant balanced quaternary (base 4). In balanced quinary (base 5), each digit has 5x the significance of the previous one, but in Booth's encoding algorithm it's 4x.
If digit i has significance b^i, then b (the base of the exponentiation) is the base (or radix) of the number system.
The page you linked explicitly mentions the binary version of Booth encoding as having base b=2 and three signed digits {-1, 0, 1}. The quaternary version similarly has b=4 and five signed digits {-2, -1, 0, 1, 2} ... and possibly sometimes -0 in practice, not sure.
Re: Mathematicians still don't know the fastest way to multiply numbers
#126Earlier quoted context omitted.
In a sense, they do exactly that! But since there are only two single-digit numbers in binary, it makes for a pretty short table.
Hardware multipliers often use a sort of base-4-ish lookup table trick as well, using the Booth-Wallace algorithm. Booth's idea is to rewrite one of the inputs in base (usually) "4", except that the digits go from -2 to +2 instead of 0 to 3. (That's five possible digits! This helps the rewriting stage not have to propagate carries. Carry propagation is very expensive.) You can use Booth in a base higher than 4, espec…
If carry propagation is so expensive, why are the mathematicians, like Karatsuba, ignoring it? It seems like we need a better complexity measure.
Re: Mathematicians still don't know the fastest way to multiply numbers
#127Earlier quoted context omitted.
Maybe I'm not communicating the point clearly. In order to use a table to do the whole multiplication it has to be much larger than the largest number you would want to multiply with it. A lot of the analysis of algorithms, especially multiplication as discussed here, is about astronomically large numbers, so you don't want the existence of an even more astronomically large table as a prerequisite.
We are talking about mathematicians. We are not talking about computer engineers trying to implement a physical GPU that can multiply matrices as fast as possible. You don't have to physically build the astronomically look up table by hand. One can simply state that it exists. Proofs do not have to be clean to be a proof. You might not "want" something in a proof, but if it works then it works.
What you are stating is simply that any algorithm whose inputs are bounded can be solved in O(1) time with a lookup table. That's known and obvious, which makes it not interesting.
Moreover it only works with bounded inputs. If your input is unbounded (as is this case with multiplication over arbitrarily large numbers) then an infinitely big lookup table is just not possible because it's part of the algorithm and hence needs to be finite.
If infinitely-big lookup tables were allowed you could for example write an algorithm that solves the halting problem, just index into the lookup table for its solution. And actually you could do this for any problem! So any problem, even so called "non computable" ones, admit a solution that runs in time linear to their input. I hope you see that this is nonsensical and it's why lookup tables are considered part of the algorithm and hence need to be finite.
> You might not "want" something in a proof, but if it works then it works.
And at the same time you don't get to change the definition of algorithm to allow your "proof" to be valid, otherwise you're just talking about nonsense.
Re: Mathematicians still don't know the fastest way to multiply numbers
#128Earlier 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.
Yup, and everyone measures it to be part of the algorithm, otherwise you start getting nonsensical results.
Re: Mathematicians still don't know the fastest way to multiply numbers
#129Re: Mathematicians still don't know the fastest way to multiply numbers
#130I was under the impression that because the grade school technique we learn is really just convolution over the digits, the fastest algorithms achieve o(n logn) via fourier transforms. Is that not the case?