Maximum density data storage

[dvgrn]

Looking over a chronology of slow-salvo technology that I wrote up recently, I realized that Calcyman's O(sqrt(log t)) diameter pattern had slipped my mind. It showed up just a month before the Gemini spaceship appeared, so it's not surprising that Life research changed direction then. It was suddenly clear that it was enormously more efficient to store construction information in glider streams, rather than in stable binary patterns on "data tapes".

Osqrtlogt.mc can be downloaded from within Golly 2.6: Help > Online Archives > Very Large Patterns. It was a last (and also very nearly first!) experiment with stable two-dimensional data storage. After early prototypes with 32x32 and 32x16 storage densities, I came up with a set of slow-salvo operations that worked inside a 16x16 diamond. This was a quick manual search, and the results now look incredibly inefficient to me -- but this is what ended up getting built into osqrtlogt.mc:

Code: Select all

#C WRITE and destructive READ salvos in a 2D grid of bits
#C with 16fd x 16fd spacing.  28G read, 10G write from a honeyfarm.
x = 332, y = 329, rule = LifeHistory
145.A$144.A.A$145.2A14$129.A31.A$128.A.A29.A.A$129.2A30.2A14$113.A31.
A31.A$112.A.A29.A.A29.A.A$113.2A30.2A30.2A12$150.E$149.E.E$97.A31.A
19.E.E9.D31.A$96.A.A29.A.A19.E9.D.D29.A.A$97.2A30.2A30.2D30.2A$145.2E
7.2E$144.E2.E5.E2.E$145.2E7.2E2$150.E$149.E.E$149.E.E$150.E6$81.A31.A
31.A31.A$80.A.A29.A.A29.A.A29.A.A$81.2A30.2A30.2A30.2A12$118.E$117.E.
E$65.A31.A19.E.E9.A31.A$64.A.A29.A.A19.E9.A.A29.A.A$65.2A30.2A30.2A
30.2A$113.2E7.2E$112.E2.E5.E2.E54.3A$113.2E7.2E55.A$180.A$118.E$117.E
.E$117.E.E$118.E$186.2A$186.A.A2.3A$186.A4.A$192.A2$49.A31.A31.A31.A$
48.A.A29.A.A29.A.A29.A.A$49.2A30.2A30.2A30.2A7$205.2A$205.A.A$205.A3$
86.E$85.E.E64.3A$33.A31.A19.E.E9.D31.A22.A59.2A$32.A.A29.A.A19.E9.D.D
29.A.A22.A58.A.A$33.2A30.2A30.2D30.2A81.A$81.2E7.2E$80.E2.E5.E2.E$81.
2E7.2E2$86.E$85.E.E$85.E.E$86.E5$220.2A$17.A31.A31.A31.A42.2A62.A.A$
16.A.A29.A.A29.A.A29.A.A41.A.A61.A$17.2A30.2A30.2A30.2A41.A11.2A$167.
2A$169.A55.2A9.2A$225.A.A8.A.A$225.A10.A7$238.2A$54.D183.A.A$53.D.D
64.3A49.A65.A$.A31.A19.D.D9.A31.A22.A50.2A$A.A29.A.A19.D9.A.A29.A.A
22.A49.A.A$.2A30.2A30.2A30.2A$49.2D7.2D182.2A$48.D2.D5.D2.D111.2A68.A
.A$49.2D7.2D112.A.A67.A$172.A$54.D$53.D.D$53.D.D$54.D$183.3A$183.A$
184.A3$17.A31.A31.A42.2A$16.A.A29.A.A29.A.A41.A.A$17.2A30.2A30.2A41.A
11.2A$135.2A$137.A3$199.2A$199.A.A$199.A4$211.3A$211.A$140.A71.A$33.A
31.A73.2A$32.A.A29.A.A72.A.A$33.2A30.2A2$88.3E49.2A$20.2E66.E51.A.A$
21.2E66.E50.A$20.E$214.3A22.2A$214.A24.A.A$215.A23.A$151.3A$151.A92.
2A$152.A91.A.A$244.A2$49.A199.2A$48.A.A198.A.A$49.2A198.A$218.2A$218.
A.A33.2A$218.A35.A.A$226.3A25.A$167.2A57.A$167.A.A57.A31.2A$167.A91.A
.A$259.A$231.3A$231.A32.2A$179.3A50.A31.A.A$179.A84.A$180.A$269.2A$
269.A.A$269.A4$245.3A$245.A$182.3A22.2A37.A$182.A24.A.A$183.A23.A2$
212.2A$212.A.A$212.A2$217.2A39.2A$217.A.A38.A.A$217.A40.A$186.2A$186.
A.A33.2A$186.A35.A.A$194.3A25.A$194.A$195.A31.2A$227.A.A$227.A$199.3A
$199.A32.2A$200.A31.A.A$232.A2$237.2A$237.A.A$237.A4$213.3A64.2A$213.
A66.A.A$214.A65.A6$295.2A$295.A.A$226.2A67.A$226.A.A$226.A2$298.2A$
298.A.A$298.A14$311.3A$311.A$248.2A62.A$248.A.A69.3A$248.A71.A$321.A
4$320.3A$263.2A55.A$263.A.A55.A$263.A4$266.2A$266.A.A$266.A62.3A$329.
A$330.A12$279.3A$279.A$280.A$288.3A$288.A$289.A4$288.3A$288.A$289.A7$
297.3A$297.A$298.A!

Now I'm wondering if the storage density can be quadrupled -- 8fd x 8fd seems as if it may just barely be enough space, at least if synchronized gliders are used. I would think there ought to be a destructive read operation out there that uses just a few gliders, coming from two directions... maybe from two synchronized Gemini-type construction arms. The presence of an object, most likely a block, would modify an exploratory spark. If a glider returns from such a reaction, another recipe would be triggered to rebuild the object in the same location. What's the minimum recipe for 8fd READ and WRITE -- three pairs of gliders? Maybe even just two pairs?

16fd x 16fd seemed like a good size for my original idea, which was to use only slow salvos from one direction to do READ and WRITE operations in 2D. This is why the above salvos are so ridiculously long -- I showed that it was possible for slow salvos to duplicate or move a target (a block or honeyfarm) from one 16fd open lane to the next, without disturbing the bit array. Calcyman adjusted the design by adding a secondary arm to re-create the honeyfarm "read head" wherever it was needed, instead of maintaining it and moving it from place to place.

No doubt 28 gliders is way too many, even for this task. Can anyone find a way to reduce the total cost of READ and WRITE to something less than 38 slow gliders? I suppose the current total is a bit more than 38, if the data processing salvos are really all unidirectional -- there has to be some junk left over somewhere after both READ and WRITE, so that the next salvo has a target to work with.

[Extrementhusiast]

Would something like this help?

Code: Select all

x = 148, y = 124, rule = LifeHistory
32.2A$32.2A15$16.2A30.2A$16.2A30.2A9$37.2C$37.2C5$2A30.2A30.2A$2A30.
2A30.2A4$53.2A$53.A.A$53.A9$16.2A30.2A$16.2A30.2A2$66.2A$66.A.A$66.A
11$32.2A$32.2A7$82.2A$82.A.A$82.A11$109.2A$108.2A$110.A6$115.2A$114.
2A$116.A4$124.2A$123.2A$125.A12$131.2A$131.A.A$131.A6$145.2A$145.A.A$
145.A!

EDIT: A couple slight changes make an eight-glider READ operation:

Code: Select all

x = 123, y = 130, rule = LifeHistory
32.3C16$16.3C29.3C16$3C29.3C29.3C$13.2C$13.2C9$28.2A$28.A.A$28.A3$16.
3C29.3C9$41.2A$41.A.A$41.A5$32.3C14$57.2A$57.A.A$57.A11$84.2A$83.2A$
85.A6$90.2A$89.2A$91.A8$98.2A$97.2A$99.A8$106.2A$105.2A$107.A6$120.2A
$120.A.A$120.A!

However, the output is inverted.

EDIT 2: And here's a seventeen-glider WRITE operation:

Code: Select all

x = 316, y = 323, rule = LifeHistory
32.3C16$16.3C29.3C16$3C29.3D29.3C$13.2C$13.2C6$25.3A$25.A$26.A4$32.3A
$32.A$16.3C14.A14.3C4$39.3A$39.A$40.A4$46.3A$46.A$47.A4$32.3C18.3A$
53.A$54.A12$67.3A$67.A$68.A28$100.3A$100.A$101.A27$122.A$121.2A$121.A
.A28$163.A$162.2A$162.A.A29$184.3A$184.A$185.A27$217.A$216.2A$216.A.A
29$247.3A$247.A$248.A14$260.3A$260.A$261.A11$272.3A$272.A$273.A$284.
3A$284.A$285.A17$303.A$302.2A$302.A.A9$313.3A$313.A$314.A!

[mscibing]

I was pondering the possibilities of 7bo$6bo$6b3o9$b2o$obo$2bo! and came up with the following:

Code: Select all

x = 309, y = 450, rule = B3/S23
307bo$306bo$306b3o4$301bo$300bo$300b3o31$268bo$267bo$267b3o23$243bo$
242bo$242b3o4$237bo$236bo$236b3o24$211bo$210bo$210b3o4$205bo$171bo32bo
$171bobo30b3o$171b2o30$139bo$139bobo$139b2o30$107bo$107bobo$107b2o30$
75bo$75bobo$75b2o16$74b2o$74b2o3$78b2o$78b2o3$66b2o14b2o$66b2o14b2o3$
70b2o14b2o$70b2o14b2o3$58b2o30b2o$58b2o30b2o3$62b2o14b2o$62b2o14b2o3$
50b2o14b2o14b2o$50b2o14b2o14b2o3$54b2o14b2o$54b2o14b2o3$58b2o14b2o$58b
2o14b2o3$62b2o$62b2o$73bo$72b2o$66b2o4bobo$49b2o15b2o$48bobo$50bo11$
105bo$104b2o$104bobo$33b2o$32bobo$34bo11$137bo$136b2o$136bobo$17b2o$
16bobo$18bo11$169bo$168b2o$168bobo$b2o$obo$2bo91$201bo$200b2o$200bobo
14$233bo$232b2o$232bobo14$265bo$264b2o$264bobo14$297bo$296b2o$296bobo!

It does require a whole row to be read and written at once, but the density very high. I'm thinking the way to use it is to read out an entire row into a delay-loop register, make any changes to the register, and then write it back to the row. It's not quite slow-salvo with a three glider salvo needed for the write of the 1 bit. I havent shown the construction arms, and I suspect the original Gemini arms would interfere with each other when putting two gliders close together on the same lane.

I've put the read row select and write row select on opposide sides of the array. It is possible to put them on the same side, but at the cost of a different endienness between read and write, and a different bit select pattern between read and write. As it is the bit select scan is identical between read and write and it is only the row gliders that differ in the two phases.

For placing the original row select block(s) for the arms to act upon I would suggest firing two gliders head on at each other, with the top glider being delayed by a variable amount. I'm thinking the top glider could be delayed by having a switch between two delay lines for each address bit as a sort of "digital to analog converter". This would obviously be a lot of circuitry, but much faster for switching between widely-separated rows than block moves of the row select blocks.

regards,
Andrew

[mscibing]

Just read up a bit on Calcyman's O(sqrt(log t)) pattern. This memory might not be directly applicable. I was envisioning the memory as a large but fixed size array.