2
$\begingroup$

This is a 16-bit PRNG function, transcribed from assembly to C for easier reading:

#define LOW(exp)  ((exp) & 0x00FF)
#define HIGH(exp) (((exp) & 0xFF00) >> 8)

uint16_t prng(uint16_t v) {

    uint16_t low  = LOW(v);
    uint16_t high = HIGH(v);

    uint16_t mul_low  = low  * 5;
    uint16_t mul_high = high * 5;

    // need to check for overflow, since final addition is adc as well
    uint16_t v1    = LOW(mul_high) + HIGH(mul_low) + 1;
    uint8_t  carry = HIGH(v1) ? 1 : 0;

    uint16_t v2 = (LOW(v1) << 8) + LOW(mul_low);

    return (v2 + 0x11 + carry);
}

Original transcription by @sagara, according to @EternisedDragon; minor edits by me. Assembly and some explanations available at https://stackoverflow.com/questions/36745601/how-is-the-carry-flag-being-set-in-this-assembly-code.

I've been trying to identify this PRNG, wanting to find out if it falls under a common classification. I've been going through Wikipedia's list of random number generators, like the Linear feedback shift register algorithms, but all of these seem way more complex than the simple function above.

Does this function look familiar to anyone?

I'd like to research the properties of this PRNG but first wanted to see if there's any existing literature.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ You'll be more likely to get an answer to this if you can translate your C code into a mathematical formula for what the C code computes. $\endgroup$
    – Brian Borchers
    Commented Apr 20, 2016 at 14:35

1 Answer 1

Reset to default
8
$\begingroup$

A little playing with the sequence of numbers generated by the C code shows that the sequence is

$z_{i+1}=5z_{i}+273 \mod 2^{16}$

This is a linear congruential generator (LCG). It's easy to show that this LCG has full period (See theorem 7.1 in Law's Simulation Modeling and Analysis, 5th ed. and check the three conditions.)

I can't find the generator in any of the references that I checked, but that doesn't mean it hasn't been published somewhere. It will suffer from all of the faults of other LCG's (in particular it will do badly on tests of uniformity in higher dimensions.)

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thanks for looking at this! Your formula did appear to match the outputs, but when I started investigating some inconsistencies, I found that the formula failed to reproduce 766 of 65536 outputs. I found that the interval between 13055 and 13056 is 6 rather than the 5, rendering the formula off-by-1 until reaching 13311, where the interval to 13312 is another anomaly of 4. Such off-by-1 stretches reappear between 26163..26367, 39270..39423, 52377..52479, and finally, 65484..65535, adding up to 766 inputs. $\endgroup$
    – Andrew Cheong
    Commented Apr 21, 2016 at 0:51
  • $\begingroup$ I wonder whether the algorithm can still be treated as an LCG despite these offsets. I'll have to learn a little more about what makes an LCG an LCG and how its properties have been derived. $\endgroup$
    – Andrew Cheong
    Commented Apr 21, 2016 at 0:55
  • $\begingroup$ Here's an Ideone, for convenience of testing. $\endgroup$
    – Andrew Cheong
    Commented Apr 21, 2016 at 1:07
  • $\begingroup$ It isn't clear to me whether the problem with this has to do with the C translation of the original assembler code producing different output from the assembler code or whether this is also true of the original assembler code. It could also be that the assembler code was a bungled attempt to produce this sequence that just didn't work right. $\endgroup$
    – Brian Borchers
    Commented Apr 21, 2016 at 2:00
  • $\begingroup$ I've found that the anomalous intervals occur at the boundaries where LOW(high*5)+HIGH(low*5) first overflows into the 17th bit, from which point carry is set, or, first stops overflowing into the 17th bit, from which point carry is reset. At these transitions, the carry causes the result to shift or unshift by 1. I believe that it was a mistake, because this could have been avoided easily by replacing the final ADC (add-with-carry) op with a normal ADD in the assembly. (Why would an "almost-LCG" be intended? Would you agree?) $\endgroup$
    – Andrew Cheong
    Commented Apr 21, 2016 at 16:07

Your Answer

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

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