I'm generating permutations with a generalized Feistel network which will output integer values $r_j$ in a specified range $[0,period]$ pseudo-randomly, according to the counter input, which will then cycle after having reached each of them all exactly once.
Rather than splitting the counter into two equally sized bitvectors $L$ and $R$, I'm operating on a quotient and remainder, with the ambition of generating permutations of arbitrary length, unlike the $2^n$ that a balanced network or maximal LSFR might generate.
uint16_t feistel(uint16_t counter, unsigned period)
{
uint16_t d = sqrt(period);
uint16_t s = period - d*d;
uint16_t q = counter / d;
uint16_t r = counter % s;
for (int i = 0; i < 3; i++)
{
uint16_t nr = r;
uint16_t F = (i * r + q);
r = F % d;
q = nr;
}
return q*d + r;
}
This code can correctly generate some maximal permutations. However, it only does so for periods that are square numbers (where s
= 0).
Can this be changed so that any choice of period generates a complete permutation? Also, are there any broader numerical issues surrounding the choice of how a number is split and manipulated in an unbalanced Feistal network (divisor * quotient + remainder, sum of two primes, left and right bitvectors, etc)?
d = sqrt(period)
, thenperiod = d*d
, and the lines = d + period - d*d
becomess = d + period - period
which is simply equal tod
? Is that supposed to be that way? $\endgroup$d
is an unsigned number however so it's effectivelyfloor(sqrt(period))
.s
is whats leftover. e.g, for period = 113, d = 10 and s = 13. $\endgroup$