misc: how random is 'random'?...
cr88192
right now, I am wondering if there is any "good" way to measure/estimate the
amount of "randomness" in an RNG's state.
the particular approach I am using looks about like this:
I have a 1024 bit state consisting of 32 32-bit numbers.
this state is seeded, initially, using rand, which is seeded using the rdtsc
instruction (x86 and friends, tells how many clock cycles the CPU has
currently gone through).
on each iteration:
the current rdtsc value is read, and added to the low-end of the array.
a linear multiply is pulled off between the array and the mersenne prime
near 2^31 (this multiply "wraps around", feeding the high end of the array
back into the bottom);
a hash is computed (multiplying each element by this prime and accumulating)
of which the upper half is used as the result.
likewise, a thread is also spawned that every 10ms goes through the above
process, and every second stores the current state to a file (this is used
as the input state the next time the thing is initialized). it is expected
that system events will cause the exact timing to vary...
theoretically, entropy should 'accumulate' in this array, so that over time
it becomes ever more random.
the problem is, I am not sure how quickly or reliably this will occur.
any thoughts?...
Gene
This is a bit like asking how high is up. It depends what you are
trying to do.
cr88192
"Gene" <gene.r...@gmail.com> wrote in message
news:0fd5f7ee-6b13-4841...@i76g2000hsf.googlegroups.com...
well, people can measure up, but it is not clear how to measure accumulated
randomness...
the idea is to generate random numbers with a low probability of clash.
examples would be GUIDs/UUIDs, PUIDs (a term I use: Probably Unique IDs,
...).
in this particular case, the intended task is to generate 48 bit PUIDs with
the intention of being used as "segment" addresses in a 128 bit address
space (the practicality of which is debated, basically the idea is to have a
128 bit space which can represent both stores and shared-memory segments on
a potentially arbitrary, but likely small, number of nodes...). randomness
is desired as an attempt to minimize any two nodes accidentally picking the
same address...
theoretically, the chances are 1/(2^48) if I have a decent RNG, but are much
lower if the RNG lacks sufficient "unique" entropy.
one crude way I guess would be to do statistical analysis of my current main
entropy source, namely rdtsc, and try to make an estimate as to the amount
of entropy I am getting from it...
or such...
John Reiser
>>trying to do.
> well, people can measure up, but it is not clear how to measure accumulated
> randomness...
There are several exceedingly good measures of randomness.
Consult: Knuth, Seminumerical Algorithms, vol.2 of The Art of Computer Programming.
> the idea is to generate random numbers with a low probability of clash.
If "avoid generating the same number twice" is the only measure, then
the guaranteed *BEST* method is to generate ascending consecutive integers
1, 2, 3, ... modulo some wide but efficient word size for your machine.
If you don't like the very high correlation between consecutive terms,
then simulate a ring counter having period 2**n -1. Consult any textbook
on "linear feedback shift register".
--
Neil
for distribution and how long before it repeats.
cr88192
"John Reiser" <jre...@BitWagon.com> wrote in message
news:fv8m3...@enews2.newsguy.com...
>>>This is a bit like asking how high is up. It depends what you are
>>>trying to do.
>
>> well, people can measure up, but it is not clear how to measure
>> accumulated
>> randomness...
>
> There are several exceedingly good measures of randomness.
> Consult: Knuth, Seminumerical Algorithms, vol.2 of The Art of Computer
> Programming.
>
I don't have, nor can I likely get ahold of, this book (unless it is online
somewhere as a free download).
>
>> the idea is to generate random numbers with a low probability of clash.
>
> If "avoid generating the same number twice" is the only measure, then
> the guaranteed *BEST* method is to generate ascending consecutive integers
> 1, 2, 3, ... modulo some wide but efficient word size for your machine.
> If you don't like the very high correlation between consecutive terms,
> then simulate a ring counter having period 2**n -1. Consult any textbook
> on "linear feedback shift register".
>
this only works on a single machine...
if the algo is being used independently on many independent machines (for
example, in the case of a bottom-up/self-organizing system), then it is not
possible to avoid clashes this way...
as noted, I may resort to using statistical analysis of the input (rdtsc
deltas, ...) in order to estimate the approximate entropy, where from this I
can estimate how much and how quickly entropy is being accumulated in the
RNG state.
potentially, I could dump some of this out in an auditory form as well,
since the ear may be able to hear patterns that the mind may miss (a hiss
would be a good sign, buzzes or tones being not so good, with silence being
the worst though...).
but, I will mostly just have to do said analysis...
> --
cr88192
"Neil" <Neil...@worldnet.att.net> wrote in message
news:4817f20b$0$11599$607e...@cv.net...
> cr88192 wrote:
>> well, this is once again in response to one of my RNG/PRNG issues...
>>
>> right now, I am wondering if there is any "good" way to measure/estimate
>> the amount of "randomness" in an RNG's state.
>>
<snip>
>>
>> theoretically, entropy should 'accumulate' in this array, so that over
>> time it becomes ever more random.
>> the problem is, I am not sure how quickly or reliably this will occur.
>>
>> any thoughts?...
>>
>>
>>
> Yes, but you are not going to find a short answer. There are measures for
> distribution and how long before it repeats.
distribution, yes...
howeve, should this thing ever repeat, that shows that this whole effort has
failed.
the point is that I am attempting to make a "true" RNG, not a PRNG, which is
where rdtsc and the monitor thread come in: they are an attempt to mine
entropy from the system itself, expected in the form of non-deterministic
noise resulting from the interactions of the hardware, the OS, and the
processor...
it is a similar approach to my former "clock() masturbation" approaches,
except that rdtsc returns elapsed processor cycles, which give much larger
and much more likely choatic numbers (especially considering that I
endlessly call sleep in order to maximize scheduler effects).
I will see though, I will have to analyze the signal.
worst case it is "silent", which would mean that there is almost no choas in
these events...
or such...
rossum
<cr8...@NOSPAM.hotmail.com> wrote:
>
>"John Reiser" <jre...@BitWagon.com> wrote in message
>news:fv8m3...@enews2.newsguy.com...
>>>>This is a bit like asking how high is up. It depends what you are
>>>>trying to do.
>>
>>> well, people can measure up, but it is not clear how to measure
>>> accumulated
>>> randomness...
>>
>> There are several exceedingly good measures of randomness.
>> Consult: Knuth, Seminumerical Algorithms, vol.2 of The Art of Computer
>> Programming.
>>
>
>I don't have, nor can I likely get ahold of, this book (unless it is online
>somewhere as a free download).
Does your town have a library? Alternatively google for the Diehard
tests.
>
>>
>>> the idea is to generate random numbers with a low probability of clash.
>>
>> If "avoid generating the same number twice" is the only measure, then
>> the guaranteed *BEST* method is to generate ascending consecutive integers
>> 1, 2, 3, ... modulo some wide but efficient word size for your machine.
>> If you don't like the very high correlation between consecutive terms,
>> then simulate a ring counter having period 2**n -1. Consult any textbook
>> on "linear feedback shift register".
>>
>
>this only works on a single machine...
Either use a central server to allocate numbers serially to all other
machines ...
>
>if the algo is being used independently on many independent machines (for
>example, in the case of a bottom-up/self-organizing system), then it is not
>possible to avoid clashes this way...
... or assign part of your 48 bits as a fixed unique number for each
machine and use the rest of the 48 bits for the incrementing counter.
The resulting 48 bits will be unique across all machines. For example
with sixteen machines you could use four bits to uniquely number each
machine and 44 bits for the incrementing counter.
rossum
Thomas Richter
> well, this is once again in response to one of my RNG/PRNG issues...
>
> right now, I am wondering if there is any "good" way to measure/estimate the
> amount of "randomness" in an RNG's state.
There is a full book chapter (several hundred pages) about this question
in Knuth's seminal work "The Art of Programming". You want to look into
volume 2, "Numerical and Seminumerical Algorithms"; the entire first
half of the book is devoted to the question of Pseudo-RG and measuring
their performance.
Despite some ad-hoc methods, I recommend highly to look into the
spectral test, i.e. how well are the outputs of the rng are spread in a
multi-dimensional space, and the chi-square test, i.e. how well does the
rng approach the statistics of a "truely random" signal.
I cannot repeat Knuth here, there is simply too much material in this
book. I can only recommend going into a library and check it, or
actually buying the series (if you're serious in computer science,
there's probably no way around that step in first place).
So long,
Thomas
cr88192
"cr88192" <cr8...@NOSPAM.hotmail.com> wrote in message
news:af21d$48167ec4$ca83b482$19...@saipan.com...
> well, this is once again in response to one of my RNG/PRNG issues...
>
> right now, I am wondering if there is any "good" way to measure/estimate
> the amount of "randomness" in an RNG's state.
>
<snip>
>
> theoretically, entropy should 'accumulate' in this array, so that over
> time it becomes ever more random.
> the problem is, I am not sure how quickly or reliably this will occur.
>
> any thoughts?...
>
ok, so here is an update:
did a whole lot of fiddling and looking at the values (rdtsc deltas).
please excuse my horridly crude treatment of statistics (and me ignoring the
risk of there being some pattern in the values returned, which at present
would require LPC filtering and similar to eliminate).
(there is enough noise to make me suspect that at least a good part of this
is actual entropy, a recording sounding about like a broken radio...).
here is a ranking in terms of value probability distribution (the actual
values in question are not displayed, rather what is visible is the counts
from the top ranking members in a histogram).
rank: count lower/higher=low/high,high/low
0: 931011 931011/3263293=0.2853,3.5051
1: 506751 1437762/2756542=0.5216,1.9172
2: 380757 1818519/2375785=0.7654,1.3064
3: 217757 2036276/2158028=0.9436,1.0598
4: 170588 2206864/1987440=1.1104,0.9006
5: 91644 2298508/1895796=1.2124,0.8248
6: 87101 2385609/1808695=1.3190,0.7582
7: 76866 2462475/1731829=1.4219,0.7033
8: 75809 2538284/1656020=1.5328,0.6524
9: 69182 2607466/1586838=1.6432,0.6086
10: 67574 2675040/1519264=1.7607,0.5679
11: 67506 2742546/1451758=1.8891,0.5293
12: 62471 2805017/1389287=2.0190,0.4953
13: 62367 2867384/1326920=2.1609,0.4628
14: 61064 2928448/1265856=2.3134,0.4323
15: 60482 2988930/1205374=2.4797,0.4033
as can be noted, the ratio is closest to 1 at about index 3.
as a crude estimate, I will assert that I am getting at least about
log2(3)=1.584962 bits of entropy per step.
so, if I call rdtsc() 64 times, I get around 101 bits of entropy, and 646
calls is sufficient to completely seed a 1024 bit RNG state (1024 steps
would play it safe).
this should be more than sufficient for generating probably-unique random
numbers...
cr88192
"rossum" <ross...@coldmail.com> wrote in message
news:bqjg14l6881q2t0ob...@4ax.com...
> On Wed, 30 Apr 2008 16:35:28 +1000, "cr88192"
> <cr8...@NOSPAM.hotmail.com> wrote:
>
>>
>>"John Reiser" <jre...@BitWagon.com> wrote in message
>>news:fv8m3...@enews2.newsguy.com...
>>>>>This is a bit like asking how high is up. It depends what you are
>>>>>trying to do.
>>>
>>>> well, people can measure up, but it is not clear how to measure
>>>> accumulated
>>>> randomness...
>>>
>>> There are several exceedingly good measures of randomness.
>>> Consult: Knuth, Seminumerical Algorithms, vol.2 of The Art of Computer
>>> Programming.
>>>
>>
>>I don't have, nor can I likely get ahold of, this book (unless it is
>>online
>>somewhere as a free download).
> Does your town have a library? Alternatively google for the Diehard
> tests.
>
libraries: not one that would have this kind of book...
diehard tests:
I know of these, but these are good for testing the statistical randomness
of a PRNG, but have will not say much of anything WRT the "true" randomness
of a TRNG, which is what is in question here...
>>
>>>
>>>> the idea is to generate random numbers with a low probability of clash.
>>>
>>> If "avoid generating the same number twice" is the only measure, then
>>> the guaranteed *BEST* method is to generate ascending consecutive
>>> integers
>>> 1, 2, 3, ... modulo some wide but efficient word size for your machine.
>>> If you don't like the very high correlation between consecutive terms,
>>> then simulate a ring counter having period 2**n -1. Consult any
>>> textbook
>>> on "linear feedback shift register".
>>>
>>
>>this only works on a single machine...
> Either use a central server to allocate numbers serially to all other
> machines ...
>
>
>>
>>if the algo is being used independently on many independent machines (for
>>example, in the case of a bottom-up/self-organizing system), then it is
>>not
>>possible to avoid clashes this way...
> ... or assign part of your 48 bits as a fixed unique number for each
> machine and use the rest of the 48 bits for the incrementing counter.
> The resulting 48 bits will be unique across all machines. For example
> with sixteen machines you could use four bits to uniquely number each
> machine and 44 bits for the incrementing counter.
>
of course, there is a big problem here:
you need a unique number for each machine (for example, the MAC address),
however, what if such a number is not conviniently available?...
this is where a TRNG works well.
if the output is truely random, there is a much higher chance of having a
unique value...
the big problem of a TRNG however, is the reliability of the entropy source.
I am not certain how random rdtsc deltas are (for example, what if the
processor, OS, and devices, are not actually generating truely random
variability, but are instead showing a psuedo-random result of the complex
interactions of the components?...).
even MS apparently messed up here, having a TRNG that could be exploited and
predicted...
cr88192
"Thomas Richter" <th...@math.tu-berlin.de> wrote in message
news:fv9jof$tdq$1...@infosun2.rus.uni-stuttgart.de...
> cr88192 wrote:
>> well, this is once again in response to one of my RNG/PRNG issues...
>>
>> right now, I am wondering if there is any "good" way to measure/estimate
>> the amount of "randomness" in an RNG's state.
>
> There is a full book chapter (several hundred pages) about this question
> in Knuth's seminal work "The Art of Programming". You want to look into
> volume 2, "Numerical and Seminumerical Algorithms"; the entire first half
> of the book is devoted to the question of Pseudo-RG and measuring their
> performance.
>
I should not have written PRNG there, or made it clearer:
TRNG+PRNG
TRNG is used to drive a PRNG, but it is a joint RNG.
I have a 1024 bit state being regularly fed by theoretically random entropy
sources...
the TRNG aspect tries to keep the current state in a unique and continually
varying stste, wheras the PRNG aspect tries to generate good statistically
random numbers (the actual sources not generating very statistically-good
results).
> Despite some ad-hoc methods, I recommend highly to look into the spectral
> test, i.e. how well are the outputs of the rng are spread in a
> multi-dimensional space, and the chi-square test, i.e. how well does the
> rng approach the statistics of a "truely random" signal.
>
and, that is the misconception here:
I already know how to test for statistical randomness, I wanted a measure of
the "true" randomness, however, a clear answer remains elusive...
> I cannot repeat Knuth here, there is simply too much material in this
> book. I can only recommend going into a library and check it, or actually
> buying the series (if you're serious in computer science, there's probably
> no way around that step in first place).
>
sadly, I have no real libraries of this sort available, nor do I currently
have the means of buying any books...
> So long,
> Thomas
>
rossum
<cr8...@NOSPAM.hotmail.com> wrote:
>libraries: not one that would have this kind of book...
Inter library loan? Knuth really is worth reading.
>
>diehard tests:
>I know of these, but these are good for testing the statistical randomness
>of a PRNG, but have will not say much of anything WRT the "true" randomness
>of a TRNG, which is what is in question here...
Diehard tests a file of bytes, it does not test how those bytes were
generated.
rossum
Ed Prochak
> "Thomas Richter" <t...@math.tu-berlin.de> wrote in message
>
> news:fv9jof$tdq$1...@infosun2.rus.uni-stuttgart.de...
>
[]
>
> > Despite some ad-hoc methods, I recommend highly to look into the spectral
> > test, i.e. how well are the outputs of the rng are spread in a
> > multi-dimensional space, and the chi-square test, i.e. how well does the
> > rng approach the statistics of a "truely random" signal.
>
> and, that is the misconception here:
> I already know how to test for statistical randomness, I wanted a measure of
> the "true" randomness, however, a clear answer remains elusive...
Statistical tests of randomness are tests of "true" randomness.
Something random merely means the outcome of the next trial is
independent of any previous trial. In your opinion, how random is
Brownian motion? (Is it random when, in classical physics, it is
theoretically possible to calculate the motion, given, of course,
information on ALL the interacting particles.)
If you want to be extreme about randomness, you would use some quantum
mechanical input. You need to decide, since you apparently do not
agree with the mathematical definition.
have a nice day,
Ed
jacko
still wonder why a windowed ladder for disk algorithm is not common.
maybe it's the task stalling effect. better throughput though when
thrashing onsets.
cheers jacko
cr88192
yes, but it also only tells how statistically random they are, not how
truely random they are, and this difference is fairly important.
actually, I already ran the diehard tests, and I think the results are
acceptable.
ended up changing to primes other than the mersenne primes though, having
noticed what their hex values were, and then running a few example tests,
make me think they are not so good for RNG purposes (actually, exponents of
smaller primes seem more effective, for example, 251^12, rather than, for
example, 2^107-1).
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.
meanwhile, a noise pattern with a strong bias towards 0, can infact be
truely far more random, but statistically it is not so random seeming (we
need PRNG-like "amplifier" logic in the mix to make it seem a lot more
random, which is what I had done).
> rossum
>
cr88192
"jacko" <jacko...@gmail.com> wrote in message
news:f03ccc8b-f5ef-4639...@c65g2000hsa.googlegroups.com...
interesting, however, this will only really work as well within the kernel,
since in userspace most often files are being accesses from the
buffer-cache...
my current approach attempts to mine entropy from the scheduler
(theoretically, any chaotic system events, such as the minor delays
introduced by disk activity, ... should show up as slight interferences in
the timing).
> cheers jacko
cr88192
"Ed Prochak" <edpr...@gmail.com> wrote in message
news:e0af602e-e095-4bda...@k13g2000hse.googlegroups.com...
> On Apr 30, 3:34 pm, "cr88192" <cr88...@NOSPAM.hotmail.com> wrote:
>> "Thomas Richter" <t...@math.tu-berlin.de> wrote in message
>>
>> news:fv9jof$tdq$1...@infosun2.rus.uni-stuttgart.de...
>>
> []
>>
>> > Despite some ad-hoc methods, I recommend highly to look into the
>> > spectral
>> > test, i.e. how well are the outputs of the rng are spread in a
>> > multi-dimensional space, and the chi-square test, i.e. how well does
>> > the
>> > rng approach the statistics of a "truely random" signal.
>>
>> and, that is the misconception here:
>> I already know how to test for statistical randomness, I wanted a measure
>> of
>> the "true" randomness, however, a clear answer remains elusive...
>
> Statistical tests of randomness are tests of "true" randomness.
> Something random merely means the outcome of the next trial is
> independent of any previous trial. In your opinion, how random is
> Brownian motion? (Is it random when, in classical physics, it is
> theoretically possible to calculate the motion, given, of course,
> information on ALL the interacting particles.)
>
from the POV of this system: no.
for my uses: yes.
the reason: even if the universe itself were/is deterministic, the amount of
internal entropy is sufficient to allow us to assume that it is random (go
find one reasonably-sized chunk of matter, such as a small rock, and then go
and look for another that is identical, how long until one is found?... very
possibly the internal state of this rock is far greater than the number of
rocks on earth...).
however, the mathematical definition is not useful for my purposes:
in my case, randomness means uniqueness and a non-deterministic outcome,
rather than an ideally-random statistical distribution.
two PRNGs with the same algo, and the same seed, will produce the same
output.
for my uses, this is not useful.
the reason is my usage:
that the numbers themselves are maximally unique, and may be generated from
any number of possible systems, each needing to generate numbers with a very
low probability of clash with any produced by any of the other systems.
so, the algo and initial state needs to be allowed to be the same, but the
output needs to be different.
what I want is not possible with a PRNG, since a PRNG produces a sequence no
more unique than the uniqueness of its input seed.
so, a non-deterministic entropy source is needed.
usually this would be a hardware device, but currently the only real device
I have (directly) available is the processor (OS-specific sources also
existing).
however, the processor contains its own unintentional entropy source: the
rdtsc instruction.
the reason this is an entropy source, is that nearly any system event,
generates an interrupt, which minorly disrupts the processor's instruction
count, and at unpredictable times, thus causing this value to be chaotic
(this choas being measurable and accumulatable...).
on linux, '/dev/random' also exists, as does CAPI on windows.
I can then siphon off these values, and feed them into the current seed
value (something resembling a PRNG is used, since otherwise the output of
rdtsc is not very exciting...), thus making it work like a kind of
statistical randomness-amplifier (me getting a non-deterministic stream of
also statistically-random values).
> If you want to be extreme about randomness, you would use some quantum
> mechanical input. You need to decide, since you apparently do not
> agree with the mathematical definition.
>
my point is being missed...
I don't demand a higher statistical randomness than is allowed by the
mathematical definition, but rather, I am demanding a somewhat different
property...
of course, QM would be a good source of the kind of entropy I am looking
for, but I don't have this, thus I have to get by with what theoretically
non-deteministic sources I have available, and sadly, the inability to
determine about how much of this is non-deterministic, and how much is
deterministic...
however, I will just have to go and assume that it is "sufficient".
maybe I will at least gain as much as a few-hundred-bits worth, which is
enough...
Greg Herlihy
> "Ed Prochak" <edproc...@gmail.com> wrote in message
But randomness does not imply uniqueness - on the contrary. A set of
random numbers has a surprisingly high chance of containing duplicates
(the well-known "birthday paradox"). So reducing the likelihood of
duplicates in a set of generated numbers - necessarily requires
reducing the randomness of the method that generated the numbers in
the first place. So, extended to its logical conclusion, any
distributed system for generating unique values ultimately must rely
on a deterministic method of some sort to generate unique values.
Otherwise, relying on random number generation all by itself - could
not guarantee the set of generated numbers contains no duplicates.
In fact, the time and the location that each number is generated
happens to provide a nearly unique identification for that number
(across all time and locations). So it would make sense to incorporate
time and place information into any kind of GUID-generating scheme.
And in fact, the proposed standard for generating universally unique
identifiers relies does exactly that:
http://www.ietf.org/rfc/rfc4122.txt?number=4122
Greg
cr88192
"Greg Herlihy" <gre...@mac.com> wrote in message
news:da0ea59f-9b30-4693...@r9g2000prd.googlegroups.com...
On May 2, 6:47 pm, "cr88192" <cr88...@NOSPAM.hotmail.com> wrote:
> "Ed Prochak" <edproc...@gmail.com> wrote in message
>
<
But randomness does not imply uniqueness - on the contrary. A set of
random numbers has a surprisingly high chance of containing duplicates
(the well-known "birthday paradox"). So reducing the likelihood of
duplicates in a set of generated numbers - necessarily requires
reducing the randomness of the method that generated the numbers in
the first place. So, extended to its logical conclusion, any
distributed system for generating unique values ultimately must rely
on a deterministic method of some sort to generate unique values.
Otherwise, relying on random number generation all by itself - could
not guarantee the set of generated numbers contains no duplicates.
In fact, the time and the location that each number is generated
happens to provide a nearly unique identification for that number
(across all time and locations). So it would make sense to incorporate
time and place information into any kind of GUID-generating scheme.
And in fact, the proposed standard for generating universally unique
identifiers relies does exactly that:
http://www.ietf.org/rfc/rfc4122.txt?number=4122
Greg
>
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...).
rossum
<cr8...@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.
rossum
cr88192
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
>
Thomas Richter
> "rossum" <ross...@coldmail.com> wrote in message
> news:s6sl14hkv1jiirco8...@4ax.com...
>> On Thu, 1 May 2008 05:12:45 +1000, "cr88192"
>> <cr8...@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
cr88192
> cr88192 wrote:
>> "rossum" <ross...@coldmail.com> wrote in message
>> news:s6sl14hkv1jiirco8...@4ax.com...
>>> On Thu, 1 May 2008 05:12:45 +1000, "cr88192"
>>> <cr8...@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
>
Thomas Richter
> 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
rossum
Knuth, Vol 2, Algorithm 3.4.2 P
An alternative shuffling algorithm would be an encryption as I
suggested elsethread.
rossum
>
>So long,
> Thomas
cr88192
no, for the reason that a random permutation requires some amount of
centralization (for example, the segment addresses being generated from a
centralized source, wheras in this case, this is not possible).
> So long,
> Thomas