So this is mostly a computer problem but this aspect is really math heavy and could probably be easily solved with some math insight so I thought I'd ask here. It might seem a little computery at first, but I hope to think it's mostly a math problem.
I am thinking about Memory Address Spaces, which you can imagine as like a page of monospaced text. Essentially it's a grid like a cartesian grid, where the content flows from left to right. So it's essentially one lone line. Each "slot" in this line is an address (1 byte let's say, but I don't think it matters for this question).
What I'm thinking about is how to effectively "point" to different areas in the address space from other areas in the address space. You can visualize it as a line like this....
___________________________________________ | | |8| | | | | | | | | | | | | | | | | | | | |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_| 1 2 3 4 5 6 7 8 ^
So basically, address 3 points to address 8 by containing a 1-byte value 8 in its slot. I would draw it with more slots but there's not enough room. But on a typical computer there could be several billion I think. But lets just say there are a lot of addressable slots and that this line is very long, like DNA perhaps.
The problem is this. While the above example "works" because the number 8 is less than 1 byte, if we instead wanted to point to position 1000 we couldn't because for our purposes, we are limited to 1-byte or position 256. The way this is typically solved in computer science is to just have 4-byte pointers (32-bits) instead of 1-byte (8-bit) pointers. This gives sufficiently large values so you can't really use them all without running into unrelated problems like memory limits and such. But I would like to try to solve this differently in this example. Instead of using 32-bit pointers, I'm wondering if there is a way to somehow use a bundle of 8-bit pointers in some way which I have been having a hard time imagining and so it will be hard to explain.
Basically, say you are at slot 10,000 (10k), and want to point to something at position 1 million (1M). If it was 32-bits, then we could just plop in a large integer 1M and we are done. But since we are limited to 8-bit integers only (or 7 or 6-bit, etc., I don't mind either way, but 8 makes it easy, just something small), we have to do something tricky, which in some sense seems sort of like hashing in a hashing function.
What I'm wondering is if you can do something like the following....
50 (some other 8-bit value) jump a few / times / we can navigate here value ----------> / --------> / 123 | jumps... | ____________________|_______________v___________|______________________ | | | | | | | | | | ||| | | | | | | | | | | | | | | | | | | | | | | | | | |_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_| 1 2 3 4 5 6 7 8 ... 10k ... ... 1M ^ ^
To explain, in the address slot 10k we have value 123. This allows us to jump in some way to some other slot. We do this jumping a few times, by grabbing values at the next address slot we land at, until we get to the destination address point of 1M.
That is to say, there is a way to point from 10k to 1M using only 8-bit values.
This would be easy and have an obvious solution if it wasn't limited by the fact that I left out: there can only be one value in a slot at a time.
So after a program runs for a while, you can imagine that the slots would be filled, with holes here and there like Swiss cheese. So you might not be able to guarantee that you can reach within 256 from your current location to the next location along the line.
What I'm imagining instead is somehow structuring the system sort of like an R-tree or Octree. So it would look something like this, where the line in the next diagram is zoomed out to be just 1 dimention.
1 / 2 .... 256 ________________________________________________/ _________________ ... ______/ / | 1.1 1.2 || 2.1 | | __________________/ __________________/ ____||___________/ | | | || || || | | | | || || || | | -|--|------------------||------------------||-----||-----------|- ... ----------|----------- | | || || || | | | |__________________||__________________||_____||___________| | | || | |________________________________________________||_________________ ... ______|
So basically, you have sort of nested boxes which are numbered within the range of 1-256. Then here's where I get totally lost....
It seems like you could somehow combine your current value (say we were at 123 again) with this "box encoding system", and you would end up with 1M.
Or if not that, then maybe you could imagine multiplying 123 by its containing box to get some offset and wallah, you are at 1M.
That's basically what I'm wondering. If there is any mathematical way to encode these 8-bit numbers, perhaps by segmenting the lines into conceptual rectangles or some other grouping mechanism, such that you could obtain a value outside of the range. Some way of organizing them. In the computer sense, you could use an 8-bit value to point to a value far outside the 8-bit range, seemingly in the 24 or 32 bit range.
Sidenote, there are all kinds of ways you could technically make this work by adding extra data around the nodes, but I don't want to do that, I want to see if it's possible to somehow create an encoding, perhaps along the lines of the R-tree or Octree, that can solve this problem.