31–40 of 53 posts
> But 27-bit hash codes were too big: with 2^15 words, they needed 2^15 * 27 bits of memory, while the PDP-11 had only 2^15 * 16 bits (64kB) of RAM—compression was essential. I'm frustrated when people put this kind of typography on the web. HTML can do superscript.
Cool. Now move forward.
They are trying, but only seem to go backwards. See Windows, Android, iOS, Teams for examples.
How about 39kB for a video game with physics, dynamic graphics, two music tracks, sound effects, online high scores, and built-in instructions? https://news.ycombinator.com/item?id=38372936
You can write an external memory spell checker with a tiny amount of RAM: something like - sort the words in the document - eliminate unique words (they sort together) - merge the sorted words with the sorted dictionary and keep only the missing words I saw this in BASIC in Creative Computing and got it working in on my TRS-80 Color Computer which had much less than 32k of available RAM, so that was the first thing I…
Earlier quoted context omitted.
I guess you really used the fact that most words are repeated to keep the byte count in check? On the old C=64 I had it was a bit of a problem not to blow out the memory with just the text of the document once you started using it for more than a 1 or 2 page paper. Keeping a second sorted copy seems almost luxurious. I guess you could save the working copy to disk first, then do the sort, then compare, then reload th…
I may be wrong, but from "external memory" in the description I think the idea is that each of those steps can be done on disk, not RAM. An external merge sort is a pretty standard database primitive, and the other two only require purely sequential access, so are friendly to spinning disks and the like.
The old IBM 360 had a 16MB address space at best, but in 1968 there were very few installations anywhere near filling it. This kind of tape
https://en.wikipedia.org/wiki/9-track_tape
could have a capacity of 80 MB or so, which is (1) much larger than RAM, and (2) mainly sequential (it could fast forward for a bit and try to find a particular block, but it was pretty slow) Contrast this to the floppy drives in the 70-140 kb range which the 8-bit micros had. Thus there was a lot of literature on external memory algorithms that would work on tapes in the early days -- though similar methods are still of interest today for "big data" as RAM is faster by a lot when you access it sequentially, you want to minimize round trips in distributed systems, etc.
(It was funny though when I talked to computer scientists around 2004 and was told to forget about external memory algorithms because 'main memory' was the thing; people realized, for instance, that Google Maps could store all the tiles in RAM in half a rack of 1U servers and if utilization was high it was much cheaper than serving the tiles off disk; Hadoop came along and was a blast from the past that itself was obsolete in just a few years)
A Bloom filter is a specific type of superimposed code.
Calvin Mooers developed random (1) superimposed coding in his Master's thesis at MIT back in the 1940s, directly influenced by Shannon's work.
Bourne's superb 1963 book "Methods of Information Handling" gives details of the mathematics.
I've no doubt Douglas knew about the broader technique, which, for example, the author of "The Large Data Base File Structure Dilemma" (1975) at http://dx.doi.org/10.1021/ci60001a005 described as "an old technique called super-imposed coding".
(1) The "random" is an important qualifier because there were superimposed codes predating Mooers, but they were not mathematically interesting or all that practically important.
You can write an external memory spell checker with a tiny amount of RAM: something like - sort the words in the document - eliminate unique words (they sort together) - merge the sorted words with the sorted dictionary and keep only the missing words I saw this in BASIC in Creative Computing and got it working in on my TRS-80 Color Computer which had much less than 32k of available RAM, so that was the first thing I…
I had spelling checkers on the Apple ][ that ran in 48K!
Reading about this and similar techniques in Programming Pearls (Second Edition) by Jon Bentley left the younger me spellbound. Similar to the evolution of linkers up to mold.