There are several types of "psuedo-random number generators" out there. 
Most of them work by having some sort of "seed", and a function that 
takes the seed and generates a new random number and a new seed.

This is great if you just want to produce a really long stream of random 
numbers. But are there any PRNGs out there which offer random (!) access 
to the stream of numbers? In other words, the ability to compute the Nth 
random number without needing to compute any of the preceding ones?

Post a reply to this message

Am 22.06.2011 14:52, schrieb Invisible:
> There are several types of "psuedo-random number generators" out there.
> Most of them work by having some sort of "seed", and a function that
> takes the seed and generates a new random number and a new seed.
>
> This is great if you just want to produce a really long stream of random
> numbers. But are there any PRNGs out there which offer random (!) access
> to the stream of numbers? In other words, the ability to compute the Nth
> random number without needing to compute any of the preceding ones?

(Would that be a Random Access Pseudo-Random Number Generator then? :-))

Depends on what properties you need the PRNs to have.

For instance, if what you really want is to generate a sequence of 
numbers with a low discrepancy distribution (and be able to pick 
individual ones from the sequence), a Halton sequence would be a good 
option.

Then again, if all you want is a value that does not depend on the seed 
in any obvious fashion, you might want to look at some cryptographic 
hashing algorithms.

Post a reply to this message

On 6/22/2011 5:52, Invisible wrote:
> But are there any PRNGs out there which offer random (!) access to
> the stream of numbers?

Take a look at eliptical curve cryptography.

Otherwise, yes, sure.

SHA(concat("mysecret", myseed, myindex))

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

Invisible <voi### [at] devnull> wrote:
> This is great if you just want to produce a really long stream of random 
> numbers. But are there any PRNGs out there which offer random (!) access 
> to the stream of numbers? In other words, the ability to compute the Nth 
> random number without needing to compute any of the preceding ones?

  You could use a hashing function to convert N to a pseudorandom number,
and it should work exactly as you describe.

-- 
                                                          - Warp

Post a reply to this message

On 22/06/2011 06:50 PM, Warp wrote:
> Invisible<voi### [at] devnull>  wrote:
>> This is great if you just want to produce a really long stream of random
>> numbers. But are there any PRNGs out there which offer random (!) access
>> to the stream of numbers? In other words, the ability to compute the Nth
>> random number without needing to compute any of the preceding ones?
>
>    You could use a hashing function to convert N to a pseudorandom number,
> and it should work exactly as you describe.

Yeah, that's about what I figured.

You could use a cryptographic hash function, but these usually provide 
strong guarantees about secrecy, etc. which aren't required if you just 
want psuedo-random numbers for simulation purposes. I'm wondering if 
anybody has looked specifically at functions which are cheap to compute 
but still look "reasonably random".

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

On 6/22/2011 13:23, Orchid XP v8 wrote:
> looked specifically at functions which are cheap to compute but still look
> "reasonably random".

Yes. They're called "non-cryptographic hashes". ;-)

-- 
Darren New, San Diego CA, USA (PST)
   "Coding without comments is like
    driving without turn signals."

Post a reply to this message

Am 22.06.2011 23:04, schrieb Darren New:
> On 6/22/2011 13:23, Orchid XP v8 wrote:
>> looked specifically at functions which are cheap to compute but still
>> look
>> "reasonably random".
>
> Yes. They're called "non-cryptographic hashes". ;-)

... but beware - there are some pretty simple algorithms out there that 
probably don't suit your needs. E.g., "hash(data) := data mod N" 
qualifies as a hash function, but probably not as "reasonably random".

Post a reply to this message

On 22/06/2011 11:24 PM, clipka wrote:
> Am 22.06.2011 23:04, schrieb Darren New:
>> On 6/22/2011 13:23, Orchid XP v8 wrote:
>>> looked specifically at functions which are cheap to compute but still
>>> look
>>> "reasonably random".
>>
>> Yes. They're called "non-cryptographic hashes". ;-)
>
> ... but beware - there are some pretty simple algorithms out there that
> probably don't suit your needs. E.g., "hash(data) := data mod N"
> qualifies as a hash function, but probably not as "reasonably random".

Yeah, a hash function for a hash table just needs to avoid collisions if 
possible. The results don't need to "look random" at all.

Post a reply to this message