Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

I need a portable, consistent pseudorandom number generator

Tags:

perl

prng

I am writing a kid sister encryption function and I need a PRNG that produces consistent results across OSes (so no floating point math, taking advantage of hardware, or system level software). It would be nice, but not necessary, for the PRNG had a period longer than 230.

I am currently using a 32 bit Xorshift:

#!/usr/bin/perl

use strict;
use warnings;

{
    use integer; #use integer math
    my $x = 123456789;
    my $y = 362436069;
    my $w = 88675123; 
    my $z = 521288629;

    sub set_random_seed {
        $w = shift;
    }

    sub random { 
        my $t = $x ^ ($x << 11);
        $x = $y;
        $y = $z;
        $z = $w;
        my $rand = $w = ($w ^ ($w >> 19)) ^ ($t ^ ($t >> 8)); 
        return $rand % 256; #scale it back to a byte at a time
    }
}

set_random_seed(5);
print map { random(), "\n" } 1 .. 10;

But I am worried because I don't really understand how it works. For example, the original source did not have an ability to set the seed, so I added one, but I don't know if I chose the correct variable for the seed.

So, all of that boils down to

  1. Do you know of a module on CPAN that fits my needs?
  2. If not, do you know of an algorithm that fits my needs?
like image 749
Chas. Owens Avatar asked Mar 27 '09 14:03

Chas. Owens


2 Answers

Math::Random::Auto is a CPAN module implementing the well-known Mersenne twister PRNG.

like image 159
unwind Avatar answered Oct 13 '22 04:10

unwind


Try using an LFSR - Linear Feedback Shift Register.. The first link on the external links has everything you need to produce any number of bits of randomness. The nice thing about this is that it is easy to implement and can be done using all integer math.

I've used it with success on an 8051 project. With perl it will be a snap.

Update:

Here's a quick perl implementation of an 8 bit LFSR:

use strict;
use warnings;

use List::Util qw(reduce);
use vars qw($a $b);

print 'Taps: ', set_taps( 8, 7, 2, 1 ), "\n";
print 'Seed: ', seed_lfsr( 1 ), "\n";
print read_lfsr(), "\n" for 1..10;

BEGIN {
    my $tap_mask;
    my $lfsr = 0;

    sub read_lfsr {
        $lfsr = ($lfsr >> 1) ^ (-($lfsr & 1) & $tap_mask );

        return $lfsr;
    }

    sub seed_lfsr {
        $lfsr = shift || 0;
        $lfsr &= 0xFF;
    }

    sub set_taps {
        my @taps = @_;

        $tap_mask = reduce { $a + 2**$b } 0, @taps;

        $tap_mask >>= 1;

        $tap_mask &= 0xFF;

        return $tap_mask;
    }
}

This code is just a prototype. If I wanted to use it in production I'd probably wrap it in a object and make register size configurable. Then we'd be rid of those pesky shared variables.

like image 7
daotoad Avatar answered Oct 13 '22 04:10

daotoad