Same, seeing the title and having not read Bradbury for a long time I was thinking either The Veldt or that one (The Long Rain). I did remember it on reading, though, and it's an unsettling feeling.
Well, yes, which is why they don't measure it your way, as it doesn't lead to discovering anything interesting about computation to have a shortcut like that. Or if they do it's part of a larger analysis, called an oracle machine.
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.
>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 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.
> 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.
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.
> If you're a carpentry shop that just bought power tools for the first time and you're worried that your employees are sticking with hand tools because that's what they know, then you look for sawdust.
Or count the fingers, I guess. It's all fun and games until someone looses AI.
Though the ancients did recognize as occult forces magnetism (Thales, according to Aristotle, gave the motive power of magnets as an example that even apparently inanimate objects have souls) and electricity (from triboelectic effects with amber, whence comes the name, and which Thales discussed as induced magnetism, also Plato mentions the stunning caused by electric rays), though it would be a while before the connection was made between these phenomena.
Pitch is the offset between the start of consecutive rows of pixels in the image, used to convert y coordinates into the start of any given row, so you access a pixel as buffer[y*pitch+x]. Often this is the image width, but can be greater depending on required alignment.
So at the end of each run increment the relevant pointer by (pitch - w) not pitch which I'm sure it's one of the bugs they saw all the time in this interview :)
reply