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$
3
  • $\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, 2018 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$
    – zetavolt
    Jun 24, 2018 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$
    – zetavolt
    Jun 25, 2018 at 18:40

1 Answer 1

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$
2
  • 1
    $\begingroup$ The reason you get a maximal permutation when period is a complete square is because then $s=d$. $\endgroup$
    – Mayank
    Jun 24, 2018 at 22:20
  • $\begingroup$ So is the problem impossible? $\endgroup$
    – zetavolt
    Jun 25, 2018 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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