1
$\begingroup$

I want to create a PRNG for an integer only (with a max of 32767) system and tried to use an LCG. So I've chosen as $m = 32767$ and $c = 3$ and I tried to figure out a good $a$. However for the full period I have to choose $a = 32768$ which cannot be used since the maximum is 32767.

Can anyone help me creating a "good" LCG?

Another question: Since the maximum (could be / is) 32767 I don't know how to calculate the successor because $a * y_{-1} + 3$ could become greater than 32767 and this is not allowed in the system. So should I use $a * (y_{-1} \mod ((32767+3)/a) + 3$ then?

$\endgroup$
6
  • $\begingroup$ IIRC $x_{new} = (x_{old} * a +c) \bmod m$ for all LCGs, in your example: $y_i = (a*y_{i-1}+3) \bmod m$ $\endgroup$
    – SOJPM
    Jun 6, 2015 at 16:14
  • $\begingroup$ Yeah I got this. But let's imagine my $x_{old}$ was 32766 and then (let's assume that a = 1) $32766 + 3 = 32769$ which is greater than 32767. So my system starts crashing since it cannot be stored anymore (because maximum value that can be stored is 32767). It's not a limitation I set up for fun, it's a system limit :( $\endgroup$
    – Sotnem
    Jun 6, 2015 at 16:22
  • $\begingroup$ you really get a hard fail on such an overflow and it doesn't simply get negative? Strange system... And of course standard note: Don't roll your own crypto, rather use something like the DRBGs or Fortuna as CSPRNG. If your integers support negative range, why not check before if $x_{old} - m +3 > 0$ and use $x_{new}=(x_{old}-m+3)$? (this only works for additions...) $\endgroup$
    – SOJPM
    Jun 6, 2015 at 16:29
  • $\begingroup$ Thanks for the standard note. I just need some "random" in my system, it's more for education usage than for anything else (if you want to google: nand2tetris). And okay, it does get negative but I don't get you approach. Sorry, I am really new in this topic... $\endgroup$
    – Sotnem
    Jun 6, 2015 at 16:35
  • 1
    $\begingroup$ To repeat Knuth's advice: don't build your own, you'll probably skrew up. Use one that's known to be good (e.g. from TAoCP). $\endgroup$
    – Raphael
    Jun 11, 2015 at 7:35

1 Answer 1

2
$\begingroup$

The output of an LCG with modulus $m$ is in range $[0\dots m-1]$. Hence the choice of $m=32767$ forbids the output to be $32767$. Perhaps the OP wants $m=32768$.

We want to compute $(a\cdot x+c)\bmod m$ for known constant integers $a$ $c$ $m$ on a system restricted to integers in $[0\dots32767]$ (or is it $[-32767\dots32767]$ or $[-32768\dots32767]$, but that only makes the problem easier).

We can compute $z=(x+y)\bmod m$ on this system, assuming $0\le x<m$ and $0\le y<m$, as
     if (m-x > y) z = x+y; else z = y-(m-x);   when $0<m\le32767$, or as
     if (32767-x >= y) z = x+y; else z = (y-(32767-x))-1;   when $m=32768$

From this primitive, it is easy to build $(a\cdot x)\bmod m$ by an addition chain, then $(a\cdot x+c)\bmod m$.

$\endgroup$

Your Answer

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