10

I would like a schema to represent integer numbers starting with 0, without any limit (assuming access to infinite linear storage).

Here's a schema that can represent numbers from 0 to 255:

Use the first byte of the storage (address 0) to store the integer.

Now, suppose I want to represent numbers larger than 255. Of course, I could use more than 1 byte to represent the integer, but as long as it's a fixed number, there will be eventually an integer so large that it cannot be represented by the original schema.

Here's another schema that should be able to do the task, but it's probably far from efficient.

Just use some sort of unique "end of number" byte, and use all the previous bytes to represent the number. Obviously, this "end of number" byte cannot be used anywhere in the number representation, but this can be achieved by using a base-255 (instead of base-256) numbering system.

However, that's slow and probably inefficient. I want to have a better one that performs better with low values and scales well.

Essentially, it's a UUID system. I want to see if it's possible to create a fast-performing UUID system that can theoretically scale to use for years, thousands of years, millions of years, without having to be redesigned.

Improve this question
11
  • 1
    Do you want something that can scale infinitely (as in your opening), or for millions of years (as in your closing)? The two requirements are (obviously) completely different. Twos complement on a 64-bit machine will scale for millions of years.
    – user16764
    Commented Jan 16, 2012 at 16:29
  • 1
    @user16764, do you mean a single 64-bit integer variable? That certainly won't work: if 6 million people are consuming 1 million UUIDs per second, it will barely last more than a month.
    – Dmitri Shuralyov
    Commented Jan 16, 2012 at 16:36
  • 1
    And how long would it take on a 128-bit machine?
    – user16764
    Commented Jan 16, 2012 at 16:53
  • 2
    The ideas in RFC 2550, which provides a lexicographical-ordered ASCII representation for arbitrarily large positive integers, may be adaptable to this. Ultimately it breaks down to a unary segment which encodes the length of a base-26 segment which encodes the length of a base-10 segment - the latter two bases being more to do with the ASCII representation than anything fundamental to the scheme.
    – Random832
    Commented Jan 16, 2012 at 17:18
  • 1
    Assuming you generate 128 bit numbers sequentially: if we upper-bound the computation capacity of all computers by giving every human a petaflop-computer, then it would take 9 million years before these numbers run out. If on the other hand every human would randomly generate 600 million 128 bit numbers, there's a 50% chance they generate 1 duplicate. Is that good enough for you? (en.wikipedia.org/wiki/Universally_unique_identifier) If not, using 256 bits multiplies both these figures by 2^128=3.4*10^38, which is more than the square of the age of the universe in seconds.
    – Alex ten Brink
    Commented Jan 16, 2012 at 18:52

8 Answers 8

Reset to default
13

An approach I've used: count the number of leading 1 bits, say n. The size of the number is then 2^n bytes (including the leading 1 bits). Take the bits after the first 0 bit as an integer, and add the maximum value (plus one) that can be represented by a number using this encoding in 2^(n-1) bytes.

Thus, 

                  0 = 0b00000000
                   ...
                127 = 0b01111111
                128 = 0b1000000000000000
                   ...
              16511 = 0b1011111111111111
              16512 = 0b11000000000000000000000000000000
                   ...
          536887423 = 0b11011111111111111111111111111111
          536887424 = 0b1110000000000000000000000000000000000000000000000000000000000000
                   ...
1152921505143734399 = 0b1110111111111111111111111111111111111111111111111111111111111111
1152921505143734400 = 0b111100000000000000000000000000000000000000000000 ...

This scheme allows any non-negative value to be represented in exactly one way.

(Equivalently, used the number of leading 0 bits.)

Improve this answer
2
  • 1
    It was hard for me to figure out which answer to mark as accepted, because I think many of them are very informative and good. But I think this one is the best fit for the question I asked (possibly not the underlying one I had in mind, which is harder to express).
    – Dmitri Shuralyov
    Commented Jan 16, 2012 at 20:04
  • 2
    I wrote a more in-depth article with an example implementation and design considerations.
    – retracile
    Commented Jan 20, 2012 at 14:59
10

There is a whole lot of theory based around what you are trying to do. Take a look at wiki page about universal codes - there is rather exhaustive list of integer encoding methods (some of which are actually being used in practice).

In data compression, a universal code for integers is a prefix code that maps the positive integers onto binary codewords

Or you could just use first 8 bytes to store the number's length in some units (most likely bytes) and then put the data bytes. It would be very easy to implement, but rather inefficient for small numbers. And you would be able to code integer long enough to fill all data drives available to humanity :)

Improve this answer
1
  • Thanks for that, that's very interesting. I wanted to mark this as accepted answer, but it took 2nd place. This is a very good answer from a theoretical point of view, IMO.
    – Dmitri Shuralyov
    Commented Jan 16, 2012 at 20:06
4

How about let the number of leading 1's plus the first 0 be the size (sizeSize) of the number size (numSize) in bits. The numSize is a binary number that gives the size of the number representation in bytes including the size bits. The remaining bits are the number (num) in binary. For a positive integer scheme, here are some sample example numbers:

Number              sizeSize  numSize    num
63:                 0 (1)     1 (1)      111111
1048575:            10 (2)    11 (3)     1111 11111111 11111111
1125899906842623:   110 (3)   111 (7)    11 11111111 11111111 11111111 11111111 11111111 11111111
5.19.. e+33:        1110 (4)  1111 (15)  11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111
Improve this answer
4

How about that: One byte for length, then n bytes for the number (least significant byte first). Repeat length+number as long as the previous length was 255.

This allows for arbitrarily large numbers, but is still easy to handle and doesn't waste too much memory.

Improve this answer
2
  • fNek: There is no upper limit. For example, if you need 513 bytes for the number, the byte sequence is [255,b0,...,b255,255,b256,...,b511,2,b512,b513]
    – user281377
    Commented Mar 12, 2014 at 20:18
  • Sorry. Should learn to read more carefully.
    – elaforma
    Commented Mar 12, 2014 at 20:19
3

Why not just use 7 bits out of each byte, and use the 8th bit to indicate whether there is another byte to follow? So 1-127 would be in one byte, 128 would be represented by 0x80 0x01, etc.

Improve this answer
3
  • 1
    This scheme encodes just 128 values in every 8 bits, which is actually less space efficient than the second encoding scheme proposed by the questioner, where 255 values are encoded in every 8 bits. Both schemes suffer from the fact that you need to read in the whole number to find out how much storage you need to store it.
    – Mark Booth
    Commented Jan 16, 2012 at 18:07
  • 3
    So you need to scan the number twice to make a copy of it, so what? If I can wait for one infinitely large number, I can wait for it twice.
    – Russell Borogove
    Commented Jan 16, 2012 at 19:51
  • Although I did not specify it very carefully, I am looking for a solution that performs as efficiently as possible (instead of a solution that simply matches the requirements; I've already described one potential inefficient answer in my question).
    – Dmitri Shuralyov
    Commented Jan 16, 2012 at 20:02
3

UUID systems are based on finite (but large) computing power in a finite (but large) universe. The number of UUIDs is large even when compared to absurdly large things like the number of particles in the universe. The number of UUIDs, with any number of fixed bits, is small, however, compared to infinity.

The problem with using 0xFFFF to represent your end of number flag is that it makes your number encoding less efficient when numbers are large. However, it seems that your UUID scheme makes this problem even worse. Instead of one out of 256 bytes skipped, you now have the entire UUID space wasted. Efficiency of computation/recognition (instead of space) depends a lot on your theoretical computer (which, I assume you have if you are talking about infinity). For a TM with a tape and a finite state controller, any UUID scheme is impossible to scale efficiently (basically, the pumping lemma screws you from moving beyond a fixed-bit-length end marker efficiently). If you don't assume a Finite State controller, this might not apply, but you do have to think about where the bits go in the decoding/recognition process.

If you just want better efficiency than 1 out of 256 bytes, you can use whatever bit-length of 1s you were going to use for your UUID scheme. That's 1 out of 2^bit-length in inefficiency.

Note that there are other encoding schemes, though. Byte encoding with delimiters just happens to be the easiest to implement.

Improve this answer
0
2

I'd suggest having a array of bytes (or ints or longs) and a length field that says how long the number is.

This is roughly the approach used by Java's BigInteger. The address space possible from this is massive - easily enough to give a different UUID to every individual atom in the universe :-)

Unless you have a very good reason to do otherwise, I'd suggest just using BigInteger directly (or its equivalent in other languages). No particular need to reinvent the big number wheel....

Improve this answer
3
  • You can't encode length of the array when number of fields can be infinite.
    – Slawek
    Commented Jan 16, 2012 at 17:29
  • I agree that using an existing solution (especially one that has been through professional scrutiny) for a given problem, when possible, is preferred. Thanks.
    – Dmitri Shuralyov
    Commented Jan 16, 2012 at 20:10
  • @Slawek: true, but for the use case the OP is describing (i.e. UUIDs), a BigInteger is effectively infinite. You can't encode infinite information in any computer with finite sized memory anyway, so BigInteger is as good as anything else you are likely to achieve.
    – mikera
    Commented Jan 17, 2012 at 1:04
2

First of all, thanks to everyone who contributed great answers to my relatively vague and abstract question.

I'd like to contribute a potential answer that I've thought of after thinking about other answers. It's not a direct answer to the question asked, but it is relevant.

As some people pointed out, using an integer of 64/128/256 bit size already gives you a very large space for UUIDs. Obviously it is not infinite, but...

Perhaps it might be a good idea to just use a fixed size int (say, 64-bit to begin) until 64-bits is not enough (or close to it). Then, assuming you have such access to all previous instances of the UUIDs, just upgrade them all to 128-bit ints and take that to be your fixed-size of integer.

If the system allows such pauses/interruption of service, and because such "rebuild" operations should occur quite infrequently, perhaps the benefits (a very simple, fast, easy to implement system) will overweigh the disadvantages (having to rebuild all previously allocated integers to a new integer bit size).

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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