141–150 of 152 posts
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 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?
Earlier quoted context omitted.
When talking informally, people often omit mentioning the base case when it's obvious or trivial. Btw, your recursion doesn't necessarily need a terminating case. See eg this definition of the list of Fibonacci numbers in Haskell: fibs :: [Integer] fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
Strictly-speaking, that's corecursion.
Earlier quoted context omitted.
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 hen…
It is other people who are trying to attack my statement who are trying to apply words like "algorithm" to it. You have such a fixed view of how things operate that you are failing to be able to take a step back and accept the existence of being able to solve any problem in a single step. You can claim that it is obvious, and trivial, and uninteresting, but that doesn't invalidate it. Sometimes thinking outside of the box is required and such strict adherence to what has come before can cloud your view of an "obvious" solution that was there the whole time.
Earlier quoted context omitted.
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 hen…
>And at the same time you don't get to change the definition of algorithm to allow your "proof" to be valid It is other people who are trying to attack my statement who are trying to apply words like "algorithm" to it. You have such a fixed view of how things operate that you are failing to be able to take a step back and accept the existence of being able to solve any problem in a single step. You can claim that it…
Then sure, go ahead. Define your own model of computation, one not based on turing machines and which somehow allows for infinitely big lookup tables, and then see what great insight it provides you.
I wonder discoveries you will be able to make in a system where you can say that the solution of a problem is just its solution.
Earlier quoted context omitted.
I think the problem comes when you do a multiplication and you need more primes for uniqueness.
I think you would probably just pick enough primes at the start to handle numbers up to the number of bits you need. If we stick with primes that fit in 32-bit unsigned integers, then using the largest k such primes covers numbers up this many bits or decimal digits: k bits digits 10 319 96 20 639 192 30 959 288 40 1279 385 50 1599 481 75 2399 722 100 3199 963 150 4799 1444 250 7999 2408 500 15999 4816 1000 31999 963…
I 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?
Can you explain some more? Thanks.
I just looked up the answer to my original question - the Fourier trick is notionally only O(N logN), but because the FFT takes you from integers to floating points, as N gets larger you need to encode more and more bits to achieve enough precision to yield absolute errors <1 after doing both Fourier transforms. The need to encode those extra bits tacks on another logN, taking you to O(N log^2 N).
Earlier quoted context omitted.
… which needs a terminating case, which cannot be not defined as the same recursion.
When talking informally, people often omit mentioning the base case when it's obvious or trivial. Btw, your recursion doesn't necessarily need a terminating case. See eg this definition of the list of Fibonacci numbers in Haskell: fibs :: [Integer] fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
Reversing arrows again, back to recursion, you have exactly the standard labeled bases case (well, cases in your code), and reversing arrows doesn't magically change algorithms or invent new structure, so it completely equivalent in the category.
For that code, the 1:1:... is exactly the terminating/starting point, reversing arrows in the category does nothing to change the requirements.
Earlier quoted context omitted.
Can you explain some more? Thanks.
If you try multiplying two numbers, say 4 digits each, using the standard grade school technique, you'll see that you end up writing the digit-wise product of each number, with a shift (adding a zero at the beginning) for each digit, followed by a sum. This is literally just a convolution operation over the digits (this is because secretly writing a number in base B is equivalent to expressing a polynomial evaluated…
Earlier quoted context omitted.
This really demonstrates the utility of pulling in a library written by experts in the field the library handles.
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?
(Maybe you'll swap out an unnecessary dependency for a simple helper function of your own).