High density random strings in Javascript

Question

I'm currently generating UUIDs in Javascript with this function (Create GUID / UUID in JavaScript?):

lucid.uuid = function() {
    return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) {
        var r = Math.random()*16|0, v = c == 'x' ? r : (r&0x3|0x8);
        return v.toString(16);
    });
}

I understand that all the randomness is only coming from Javascript's Math.random() function, and I don't care if it meets an RFC for a UUID. What I want is to pack as much randomness into as few bytes as possible in a Javascript string. The above function gives about 128 bits of randomness. How small of a string (as measured in UTF8 bytes sent over the wire in an HTTP POST) could I fit 128 bits into in Javascript? And how would I generate such a string?

Edit: This string will be part of a JSON object when sent to the server, so characters that need to be escaped in a string are not very helpful.

score 2 · Accepted Answer · answered Aug 05 '11 at 22:59

Here is one potential function I came up with. The seed string is the set of unreserved URL characters (66 of them). I prefix the randomness with about a year's worth of 1-second-resolution timestamp data, which is helpful since the collision space for my particular application is only filled up reasonably slowly over time (only at MOST a few hundred of these generated per second in an extreme case).

uuidDense = function() {
    var seed = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789-_.~';

    //Start the UUID with 4 digits of seed from the current date/time in seconds
    //(which is almost a year worth of second data).
    var seconds = Math.floor((new Date().getTime())/1000);

    var ret = seed[seconds % seed.length];
    ret += seed[Math.floor(seconds/=seed.length) % seed.length];
    ret += seed[Math.floor(seconds/=seed.length) % seed.length];
    ret += seed[Math.floor(seconds/=seed.length) % seed.length];

    for(var i = 0; i < 8; i++)
        ret += seed[Math.random()*seed.length|0];

    return ret;
}

Thoughts?

score 0 · Answer 2 · answered May 03 '13 at 02:20

Your question is somewhat contradictory. Javascript strings use UCS-2 (fixed 16-bit characters) for their internal representation. However UTF-8 is variable width, but for encoding purposes I believe the most compact form would be to use 1-byte UTF8 characters, which only require the most significant bit be zero. I.e. you could pack 128 bits into 128 * 8/7 = 147 bits.

Converting to bytes and rounding up, you could do this in 19 characters.

score 0 · Answer 3 · answered Aug 05 '11 at 22:30

0

128 bits = 16 bytes -> base64 -> 16*3/2 = will give you string of 24 characters (versus 36 chars that you have)

You also can use base85 for better density but that will require URL encode so you may get even worse results than you have.

answered Aug 05 '11 at 22:30

c-smile

26,734
7
59
86

High density random strings in Javascript

3 Answers3