Hacker News Reader

Comment by Veedrac | Hacker News Reader

Here's a much simpler solution to the problem: your length is no more than ~2^48 since you're using real hardware, so prefix your string with an 8-byte base64 encoding of that 6-byte length.

View on HN

Note that you would not have an encoding for negative numbers then, and you would have to use the alternative base64 table,

  +/0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz

as the normal one is not order-preserving. Otherwise yeah, you could probably do that--and of course there are many ways to patch what you've got to handle negatives, e.g. by noticing that it is slightly wasteful (the base64 prefix ++++++++ is never used) or by using a leading character lower than + (so - is out but ! for example is available) and then encoding the rest of the string in an "ascii-reversed" way.

However I must object to the idea that "real hardware" cannot handle the petabyte scale. The in-article recursive approach of using the algorithm:

    function encode(number) {
        //calculate some base number_string
        return number < NUM_THRESHOLD?
            number_string :
            sigil + encode(number_string.length) + opt_divider + number_string;
    }

is not a particularly bad one. The only thing that maybe I'd balk at is that the given encoding requires a human editor to use an ASCII table to lookup their string lengths, which is clearly undesirable... one might instead go for the most naive case where NUM_THRESHOLD is simply 10 and have the number 123,456,789,012,345,678,901 be represented as:

    ~~2 21 123456789012345678901

so that it's clearly "there are going to be 2 length strings" (hence two tildes) -- the first always has length 1, it specifies "the next has length 2" and then "the next has length 21."

This is also pretty easy to parse and one can use a leading - sign to encode negative numbers, for example.

> However I must object to the idea that "real hardware" cannot handle the petabyte scale.

By the time I'm talking about integers that don't fit in x86 address space, I'm not talking JSON ;).

I guess that makes sense and speaks to a bigger problem here, which is that with a very large number one certainly wants to simply store it in a massive file on disk, and the encoding to do that probably shouldn't be based on the printable ASCII digits--because why.

If you use a decimal number with leading zeros instead of base64 you can have a solution that is completely human compatible. It would be 15 digits for 2^48 or 20 digits for 2^64 if you want to be future-proof.

Since the goal is to store really long numbers, it seems like a false economy to worry about a few bytes at the front.

Reply on news.ycombinator.com