' (Pseudo) -arbitrary features' by seeding of PRNGs?

I have an application that desires controlled arbitrary features from $\mathbb{Z}^2$ and also $\mathbb{Z}^3$ to $2^{32}$, where by controlled I primarily suggest seedable by some parameters (claim, like 3 to 5 32-bit integers) such that the very same seeds will certainly constantly generate the very same features. One of the most noticeable means of doing this (for the two-dimensional instance, claim) would certainly appear to be calculating the value at some time $(x,y)$ by utilizing $x$, $y$, and also the seed parameters as seeds for something like an LFSR generator or a Mersenne Twister, after that running the RNG for some set variety of actions and also taking the resultant value as the value of the function then.

My inquiry is, just how can I be particular that this procedure will not maintain way too much relationship in between surrounding 'seed factors', and also exists either an uncomplicated evaluation or perhaps simply some basic standard for the amount of models would certainly be essential to remove that relationship? My first back-of-the-envelope hunch would certainly be that each model about increases the decorrelation in between offered seed values, to make sure that 32 models would certainly be essential to attain the requisite decorrelation over a series of $2^{32}$ values (and also in technique I 'd possibly double it to 64 models), yet that's purely a hunch and also any kind of correct evaluation would certainly rate!

Edited for explanation: To better lay out the concern, I might be tasting this arbitrary function $f$ (for some offered seed parameters) at approximate values, and also require those examples to be the same in between passes; so as an example, if a first application calculates $f(0, 0)$, $f(437, 61)$, $f(-23, 129)$, and afterwards $f(5,3)$, and also a 2nd (possibly simultaneous) application calculates $f(1,0)$ and afterwards $f(5,3)$, both passes demand to locate the very same value of $f$ at $(5,3)$. I might additionally be tasting $f$ at approximate factors, so I would certainly such as the analysis to take constant time (and also specifically, reviewing $f(x,y)$ should not require time straight in $x+y$).

2019-05-07 00:09:35
Source Share
Answers: 2

Note that when an LFSR is made use of to create a series of $+1\;/-1$ values, the relationship in between that series and also at any time - changed variation of that series is near absolutely no : (amount from $i = 0$ to $N-1$ of $a[i]a[i+k]$) is either $N$ if $k$ is a numerous of $N$, or $-1$ or else.

The first state of an LFSR has a one - to - one mapping to the moment change - - this is similar to a distinct logarithm trouble in Galois areas ; offered a time change k, it's very easy to locate the first state of an LFSR ($\mathcal{O}(log(k))$, I assume, as it's simply calculating exponentiation in the ideal Galois area), yet offered the first state of an LFSR, it's tough to locate the moment change k in anything much shorter than $\mathcal{O}(k)$. So your PRNG can be an LFSR with long duration as an example 64 little bits or better, and also the "seed" can be a time change made use of to acquire a various first state.

Regarding $2$ - or $3$ - or $k$ - dimensional mapping, interleave the littles the works with, and also make use of a hash function to map those little bits to an integer for usage in acquiring LFSR seeds.

I'm not exactly sure what sort of relationship you're aiming to stay clear of in between features. (as an example relationship in an analytical feeling, or cryptographic freedom as an example one PRNG can not be made use of to forecast future result of an additional).

2019-05-09 03:08:00

This does not purely address your inquiry, yet could be also wish for a comment. =)

I think you need to reassess your strategy. The majority of arbitrary number generators are made to be seeded as soon as, and also than return a series of "arbitrary" numbers, as near independent and also evenly dispersed as feasible. I do not assume that there are several outcomes concerning the relationship of the 64th series component for various seeds.

Additionally, (at the very least in the executions I recognize) the duration of the algorithm is a lot longer than the variety of feasible seeds. If you need to recycle seeds in your instance, you can present relationships that are preventable.

As opposed to precomputing the whole grid, you can get an arbitrary value simply - in - time and also store it for future reference, conserving memory if you do not accessibility every node.

2019-05-08 19:47:14