2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Initial thought: one-byte pointers, except FF means "add another byte to the pointer". Or possibly the first 2 or 3 bits of the pointer say how many bytes it is. $\endgroup$ – timtfj Feb 9 at 19:28
0
$\begingroup$

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.

... 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.

There are many types of heap algorithms optimized for different goals: sorting, access speed, rebalancing, etc. You'll need to decide if you want more than a trivial solution.

The only limits you have offered are: 8-bit (or less) integers, address space of approximately several billion but less than 32-bits (huh?), you want to be able to address each location (with a resolution of one) but obviously not every location.

First off several billion, 7000000000, equals 110100001001110111000011000000000 in binary, that's over 32 bits. One terabyte is $2^{40}\!$, and as you mentioned 8 bits can count to 255 (256 different values). $2^{32}\!$ equals 4,294,967,295.

Trivial solution:

  • If you use 7 bits you can count to 127.
    For the first location, the root:

    1. Leave the high bit at zero to terminate the list, so that's your end location.
      That permits you to address any location up to 127 with one 8 bit byte.

    2. Set the high bit to one, that indicates that the value is a pointer to the next location, a location which has the high bit set or cleared.
      The use of the second 7 bit byte gives you 14 bits, these can be split to address 127+127 locations or concatenated to access $2^{14}\!$ locations depending upon whether you want to rigidly adhere to 8 bit bytes (due to hardware limitations) or are able to deal with arbitrary bit lengths.

    3. Additional bytes are similarly coded.
      8 bytes (normally $2^{64}\!$), instead of accessing $2^{64}\!$ bytes, would be able to address $2^{64}\!-8$ ($2^{56}\!$) or 127*8=1016 bytes, depending on the implementation. Of course you aren't limited to trees 8 nodes long and thus would have an infinity sized memory addressability; provided enough real memory existed to hold the pointer chain.

    4. Where one pointer collides with another, pointing to a leaf (ending node) instead of a branch, simply decrement or increment the prior value and do the opposite with the following location; where one backwards is at its limit you can only go forward and where both the preceding and current pointer is at their limits simply add an additional node.
      While you'll have great capacity and a simple to implement solution, thus far, where the difficulty will lie is with the necessary garbage collection and optimization co-routines.

See also:

I hope to think it's mostly a math problem.

It seems to me more of a computer problem, one of implementation, the mathematics are rather trivial in some respects and NP hard in others (depending on the algorithm chosen and compromises accepted). While I've explained what you've asked to implement you might also ask on one of our several computer Q&A sites if there's another aspect you want an optimization for.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.