Prev: Do you get paid more than you deserve?
Next: Programming to Beat the Odds in Gaming
From: rossum on 6 May 2008 12:47
On Tue, 06 May 2008 12:29:37 +0200, Thomas Richter
<thor(a)math.tu-berlin.de> wrote:

>cr88192 wrote:
>
>> the point is to generate presumably non-clashing numbers.
>> in this case, they would serve as segment numbers in some large address
>> space.
>
>In that case, you don't want "random" numbers, but a random
>*permutation* of the 48bit space, which is something different. I forgot
>the algorithm to do that, but I remember, it's in Knuth's book.
Knuth, Vol 2, Algorithm 3.4.2 P

An alternative shuffling algorithm would be an encryption as I
suggested elsethread.

rossum

>
>So long,
> Thomas

From: cr88192 on 4 May 2008 16:56

"rossum" <rossum48(a)coldmail.com> wrote in message
news:95vq14pt79mucocnt573ro3m6oo8qducuf(a)4ax.com...
> On Sun, 4 May 2008 11:31:27 +1000, "cr88192"
> <cr88192(a)NOSPAM.hotmail.com> wrote:
>
>>yes, this is technically true, but the answer is this:
>>more bits.
>>
>>while for, say, 1 billion unique items, we can get by with 32 bits and a
>>deterministic method, we can also use 64 bits and a good RNG, and have a
>>collision probability of about 1/16000000000.
>>
>>in my case, this is good enough for me to regard the numbers as unique,
>>even
>>if not provable as such (they will just work out this way in practice...).
> A different answer might be to generate a provably unique number that
> is obviously not random and then encrypt it. The resulting byte
> string is both provably unique (because it can be decrypted) and
> apparently random.
>

yes, however, we would need a provably unique number, and to extend it in a
way that is also provable not to damage its uniqueness.

for example, if we have a unique 32 bit number, we can tack on a 16 bit
number (say, a sequence number), and have a unique 48 bit number.
likelywise, we can tack 16 bits onto a MAC address, giving a unique 64 bit
number.

however, what if the spot we have is only 48 bits?
does every system have some necessarily unique 32 bit number?...
we have MAC addresses, but this would leave no space for adding a sequence
number.


all of these are problems, and using an RNG is much more practical (note, a
detail: I had been following the MAC-address formatting rules, each number
is encoded as a "locally-administered" address, thus a valid MAC address
would provably not clash with a randomly generated number).


> rossum
>


From: Thomas Richter on 5 May 2008 13:55
cr88192 wrote:
> "rossum" <rossum48(a)coldmail.com> wrote in message
> news:s6sl14hkv1jiirco8d44u0f9ileuf9mnj2(a)4ax.com...
>> On Thu, 1 May 2008 05:12:45 +1000, "cr88192"
>> <cr88192(a)NOSPAM.hotmail.com> wrote:
>>
>>> libraries: not one that would have this kind of book...
>> Inter library loan? Knuth really is worth reading.

I second this.

>> Diehard tests a file of bytes, it does not test how those bytes were
>> generated.
>>
>
> yes, but it also only tells how statistically random they are, not how
> truely random they are, and this difference is fairly important.

In that case, forget it. A) because the term "truely random" is
ill-defined, and B) in case you mean "Kolmogorov complexity", it can be
shown that you cannot determine this algorithmically, which defeats your
purpose. All you can do *is* statistical testing.

> for example, a deterministic permutation with a large period, could still
> score very well in terms of statistical randomness, and thus pass the tests,
> despite being very much deterministic.

Each Pseudo-RNG is deterministic by its very construction. There is
nothing against this. So, the question you should *really* ask is: For
which purpose do you need the numbers, and: When is random random enough?

So long,
Thomas

From: cr88192 on 5 May 2008 18:52

"Thomas Richter" <thor(a)math.tu-berlin.de> wrote in message
news:fvnhhr$e8p$1(a)infosun2.rus.uni-stuttgart.de...
> cr88192 wrote:
>> "rossum" <rossum48(a)coldmail.com> wrote in message
>> news:s6sl14hkv1jiirco8d44u0f9ileuf9mnj2(a)4ax.com...
>>> On Thu, 1 May 2008 05:12:45 +1000, "cr88192"
>>> <cr88192(a)NOSPAM.hotmail.com> wrote:
>>>
>>>> libraries: not one that would have this kind of book...
>>> Inter library loan? Knuth really is worth reading.
>
> I second this.
>
>>> Diehard tests a file of bytes, it does not test how those bytes were
>>> generated.
>>>
>>
>> yes, but it also only tells how statistically random they are, not how
>> truely random they are, and this difference is fairly important.
>
> In that case, forget it. A) because the term "truely random" is
> ill-defined, and B) in case you mean "Kolmogorov complexity", it can be
> shown that you cannot determine this algorithmically, which defeats your
> purpose. All you can do *is* statistical testing.
>

yeah.


>> for example, a deterministic permutation with a large period, could still
>> score very well in terms of statistical randomness, and thus pass the
>> tests, despite being very much deterministic.
>
> Each Pseudo-RNG is deterministic by its very construction. There is
> nothing against this. So, the question you should *really* ask is: For
> which purpose do you need the numbers, and: When is random random enough?
>

the point is to generate presumably non-clashing numbers.
in this case, they would serve as segment numbers in some large address
space.

in my case, the numbers are 48 bit and random, however, they are encoded as
locally-administered MAC addresses.


the potential risk of clashes, is that two nodes using shared memory within
a given cluster, could conflict in terms of used segment numbers. in this
context however, the risk could be reduced mostly by having each node, when
creating a segment, checking with a kind of lookup server to verify that the
segment has not been used (if by some chance a positive hit comes back, a
new number is generated).


> So long,
> Thomas
>


From: Thomas Richter on 6 May 2008 06:29
cr88192 wrote:

> the point is to generate presumably non-clashing numbers.
> in this case, they would serve as segment numbers in some large address
> space.

In that case, you don't want "random" numbers, but a random
*permutation* of the 48bit space, which is something different. I forgot
the algorithm to do that, but I remember, it's in Knuth's book.

So long,
Thomas
 |  Next  |  Last
Pages: 1 2
Prev: Do you get paid more than you deserve?
Next: Programming to Beat the Odds in Gaming