Мне нужен портативный, последовательный генератор псевдослучайных чисел - PullRequest
Новая
       8

Мне нужен портативный, последовательный генератор псевдослучайных чисел

5 голосов
/ 27 марта 2009

Я пишу сестринскую функцию шифрования , и мне нужен PRNG, который дает согласованные результаты для всех операционных систем (поэтому не требуется математических вычислений с плавающей запятой, использование аппаратного обеспечения или программного обеспечения системного уровня). Было бы неплохо, но не обязательно, потому что у PRNG был период, превышающий 2 30 .

В настоящее время я использую 32-разрядную 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;

Но я волнуюсь, потому что я действительно не понимаю, как это работает. Например, исходный источник не имел возможности установить начальное число, поэтому я добавил его, но я не знаю, выбрал ли я правильную переменную для начального числа.

Итак, все это сводится к

  1. Вам известен модуль на CPAN, который соответствует моим потребностям?
  2. Если нет, знаете ли вы алгоритм, который соответствует моим потребностям?

Ответы [ 2 ]

7 голосов
/ 27 марта 2009

Попробуйте использовать LFSR - Регистр сдвига с линейной обратной связью. . T у первой ссылки на внешних ссылках есть все, что нужно для получения любого количества бит случайности. Приятно то, что это легко реализовать и можно сделать, используя все целочисленные математические вычисления.

Я успешно использовал его в проекте 8051. С Perl это будет несложно.

Обновление:

Вот быстрая реализация 8-битного LFSR на Perl: 

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;
    }
}

Этот код является всего лишь прототипом. Если бы я хотел использовать его в производстве, я бы, вероятно, обернул его в объект и сделал бы настраиваемый размер регистра. Тогда мы избавимся от этих надоедливых общих переменных.

7 голосов
/ 27 марта 2009

Math :: Random :: Auto - это модуль CPAN, реализующий известный Mersenne twister PRNG.

...