Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

For algorithms, a little memory outweighs a lot of time

quantamagazine.org

Post reply on HN
Print view View original

61–70 of 144 posts

Re: For algorithms, a little memory outweighs a lot of time

#61

Post by catoc »

golly_ned wrote: post #57

“ If the problem is solved next week, Williams will be kicking himself. Before he wrote the paper, he spent months trying and failing to extend his result” What a strange, sad way to think about this. Academia is perverse.

Nothing necessarily perverse here. I don’t know Williams but don’t image him disliking the other guy or being unhappy with progress in general, but just being someone who truly challenged himself only to find him being trumped a week later; and kicking himself for that.

Either way, the week is not yet over, at least since the quanta article, so maybe no kicking will ensue.

Re: For algorithms, a little memory outweighs a lot of time

#62

Post by vlovich123 »

whatever1 wrote: post #56
crmd wrote: post #36

Earlier quoted context omitted.

Reminds me of when I started working on storage systems as a young man and once suggested pre-computing every 4KB block once and just using pointers to the correct block as data is written, until someone pointed out that the number of unique 4KB blocks (2^32768) far exceeds the number of atoms in the universe.

We know for a fact that when we disable the cache of the processors their performance plummets, so the question is how much of computation is brand new computation (never seen before)?

While true, a small technical nitpick is that the cache also contains data that’s previously been loaded and reused, not just as a result of a previous computation (eg your executable program itself or a file being processed are examples)

Re: For algorithms, a little memory outweighs a lot of time

#63

Post by Traubenfuchs »

crmd wrote: post #36
whatever1 wrote: post #16

Lookup tables with precalculated things for the win! In fact I don’t think we would need processors anymore if we were centrally storing all of the operations ever done in our processors. Now fast retrieval is another problem for another thread.

Reminds me of when I started working on storage systems as a young man and once suggested pre-computing every 4KB block once and just using pointers to the correct block as data is written, until someone pointed out that the number of unique 4KB blocks (2^32768) far exceeds the number of atoms in the universe.

you might be interested in pifs

https://github.com/philipl/pifs

Re: For algorithms, a little memory outweighs a lot of time

#64

Post by grumbelbart2 »

shakna wrote: post #60
datameta wrote: post #44

Earlier quoted context omitted.

This might be completely naive but can a reversible time component be incorporated into distinguishing two hash calculations? Meaning when unpacked/extrapolated it is a unique signifier but when decomposed it folds back into the standard calculation - is this feasible?

Some hashes do have verification bits, that are used not just to verify intact hash, but one "identical" hash from another. However, they do tend to be slower hashes.

Do you have an example? That just sounds like a hash that is a few bits longer.

Re: For algorithms, a little memory outweighs a lot of time

#65

Post by deadfoxygrandpa »

jodrellblank wrote: post #47
crmd wrote: post #36

Earlier quoted context omitted.

Reminds me of when I started working on storage systems as a young man and once suggested pre-computing every 4KB block once and just using pointers to the correct block as data is written, until someone pointed out that the number of unique 4KB blocks (2^32768) far exceeds the number of atoms in the universe.

Reminds me of when I imagined brute-forcing every possible small picture as simply 256 shades of gray for each pixel x (640 x 480 = 307200 pixels) = 78 million possible pictures. Actually I don't have any intuition for why that's wrong, except that if we catenate the rows into one long row then the picture can be considered as a number 307200 digits long in base 256, and then I see that it could represent 256^307200…

i think at some point you should have realized that there are obviously more than 78 million possible greyscale 640x480 pictures. theres a lot of intuitive examples but just think of this:

https://images.lsnglobal.com/ZFSJiK61WTql9okXV1N5XyGtCEc=/fi...

if there were only 78 million possible pictures, how could that portrait be so recongizably one specific person? wouldnt that mean that your entire picture space wouldnt even be able to fit a single portrait of everyone in Germany?

Re: For algorithms, a little memory outweighs a lot of time

#66

Post by shakna »

grumbelbart2 wrote: post #64
shakna wrote: post #60

Earlier quoted context omitted.

Some hashes do have verification bits, that are used not just to verify intact hash, but one "identical" hash from another. However, they do tend to be slower hashes.

Do you have an example? That just sounds like a hash that is a few bits longer.

Mostly use of GCM (Galois/Counter Mode). Usually you tag the key, but you can also tag the value to check verification of collisions instead.

But as I said, slow.

Re: For algorithms, a little memory outweighs a lot of time

#68

Post by xlii »

From the „Camel Book”, one of my favorite programming books (not because it was enlightening, but because it was entertaining); on the Perl philosophy:

“If you’re running out of memory, you can buy more. But if you’re running out of time, you’re screwed.”

Re: For algorithms, a little memory outweighs a lot of time

#69

Post by handsclean »

whatever1 wrote: post #16

Lookup tables with precalculated things for the win! In fact I don’t think we would need processors anymore if we were centrally storing all of the operations ever done in our processors. Now fast retrieval is another problem for another thread.

https://conwaylife.com/wiki/HashLife is an algorithm for doing basically this in Conway’s Game of Life, which is Turing complete. I remember my first impression being complete confusion: here’s a tick-by-tick simulation too varied and complex to encapsulate in a formula, and you’re telling me I can just skip way into its future?

Re: For algorithms, a little memory outweighs a lot of time

#70

Post by awanderingmind »

ziofill wrote: post #67

At the cost of sounding ridiculous: can there be a notion of "speed of light" in the theory of computation, determining the ultimate limit of memory (space) vs runtime?

You mean something like this https://en.wikipedia.org/wiki/Bremermann%27s_limit or this https://en.wikipedia.org/wiki/Quantum_speed_limit?
Post reply on HN