2
$\begingroup$

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)?

$\endgroup$
  • $\begingroup$ if d = sqrt(period), then period = d*d, and the line s = d + period - d*d becomes s = d + period - period which is simply equal to d? Is that supposed to be that way? $\endgroup$ – Ella Rose Jun 24 '18 at 0:35
  • 1
    $\begingroup$ That's almost correct, d is an unsigned number however so it's effectively floor(sqrt(period)). s is whats leftover. e.g, for period = 113, d = 10 and s = 13. $\endgroup$ – ŹV - Jun 24 '18 at 2:36
  • $\begingroup$ @EllaRose I am such a moron, I can't believe I "corrected" you -- you are absolutely right, that was a typo on my behalf. $\endgroup$ – ŹV - Jun 25 '18 at 18:40
1
$\begingroup$

I think that this method of yours will not work out. The reason is the way you compute $r = counter$ mod $s$.
Take a simple example of $(counter_1, period) = (3, 11)$ and $(counter_2, period) = (5, 11)$. Here $d=3$ and $s=5$.
You get initial $(q_1, r_1) = (1,3)$ and $(q_2, r_2) = (1,0)$.
After first iteration of the loop, you have $(q_1, r_1) = (3,1)$ and $(q_2, r_2) = (0,1)$.
After the second interation of the loop, you will get $(q_1, r_1) = (1,1)$ and $(q_2, r_2) = (1,1)$.
Now, for the remaining iterations, both $(q_1,r_1)$ and $(q_2,r_2)$ will always go along being equal and will finally result in equal values being returned by the function for 2 different counter values with the same period sabotaging the maximal permutation.
You should get rid of the above mentioned issue by computing initial $r$ as $r = counter$ mod $d$.

$\endgroup$
  • 1
    $\begingroup$ The reason you get a maximal permutation when period is a complete square is because then $s=d$. $\endgroup$ – Mayank Jun 24 '18 at 22:20
  • $\begingroup$ So is the problem impossible? $\endgroup$ – ŹV - Jun 25 '18 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.