Prev: Requesting critique of spec of my new MayLoad utility (similar to Unix 'make')
Next: Linked List confusion
From: mathieu on 6 May 2008 06:25
On May 4, 12:33 am, Kalle Olavi Niemitalo <k...(a)iki.fi> wrote:
> mathieu <mathieu.malate...(a)gmail.com> writes:
> > 1. I am allowed to use the '.' character but as a separator so this
> > mean I could potentially have a base 11 to convert my number (except
> > that '.' is invalid, as well as '..' ... ). I have not yet find a true
> > mapping to this fake base 11.
>
> (* (log 11 2) 37)
> => 127.99897
>
> So, with 37 digits in base 11, you can't store all 128 bits.
> 0.07% of the possible bit combinations cannot be represented.
> However, if shorter strings are also allowed:
>
> (log (loop for length from 1 to 37 sum (expt 11 length)) 2)
> => 128.13647
>
> (log (loop for length from 36 to 37 sum (- (expt 11 length) 1)) 2)
> => 128.1245
>
> So strings of 36 and 37 characters together give you enough bits,
> even if strings consisting solely of dots are disallowed.
> Such a mapping would be pretty easy to implement, at least if it
> doesn't have to be extremely fast.
>
> If you also cannot use dots at the beginning, at the end, nor
> adjacent to each other:
>
> (let ((cache (make-hash-table)))
> (defun combinations (length)
> (or (gethash length cache)
> (setf (gethash length cache)
> (+ (expt 10 length)
> (loop for piece from 1 to (- length 2)
> sum (* (expt 10 piece)
> (combinations (- length 2 piece)))))))))
> (log (loop for length from 1 to 37 sum (combinations length)) 2)
> => 123.55496
>
> which is much worse.

Thanks, but I think I am pretty lucky since most implementation are
storing the version number, see

http://en.wikipedia.org/wiki/UUID#Random_UUID_probability_of_duplicates

So I can just discard this version number (I believe this is perfectly
valid).

And: 2^122 - 10^37 < 0

-M
 | 
Pages: 1
Prev: Requesting critique of spec of my new MayLoad utility (similar to Unix 'make')
Next: Linked List confusion