Какой самый быстрый способ генерации псевдослучайного числа с помощью 8-битного MCU?

Линейный конгруэнтный генератор - хороший алгоритм. Но есть ли более быстрый алгоритм?

Источник

3 ответа

Решение

Насколько я помню, 8051 имеет множитель 8x8=16 бит, поэтому может быть целесообразным реализовать генератор умножения с переносом с задержкой. Преимущество этого метода заключается в том, что если вы можете найти подходящее безопасное простое число, вы можете получить очень длинный период с очень малой арифметикой.

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

Я просто собрал это вместе, и хотя я не уверен на 100%, что он правильно реализует MWC, он на самом деле проходит удивительное количество тестов:

#define STATE_BYTES 7
#define MULT 0x13B /* for STATE_BYTES==6 only */
#define MULT_LO (MULT & 255)
#define MULT_HI (MULT & 256)

uint8_t rand8(void)
{
    static uint8_t state[STATE_BYTES] =
    { 0x87, 0xdd, 0xdc, 0x10, 0x35, 0xbc, 0x5c };
    static uint16_t c = 0x42;
    static int i = 0;
    uint16_t t;
    uint8_t x;

    x = state[i];
    t = (uint16_t)x * MULT_LO + c;
    c = t >> 8;
#if MULT_HI
    c += x;
#endif
    x = t & 255;
    state[i] = x;
    if (++i >= sizeof(state))
        i = 0;
    return x;
}

Как видите, множитель на самом деле равен девяти битам, но мы используем shift-and-add для реализации последнего бита, с которым аппаратный множитель не может справиться.

При дальнейшем тестировании я обнаружил подходящее безопасное простое число в 89 битов, которое пропускает почти все жесткие диски. Измените эти строки:

#define STATE_BYTES 10
#define MULT 0x153 /* for STATE_BYTES==10 only */

и я использовал это семя для тестирования:

static uint8_t state[STATE_BYTES] =
{ 0x87, 0xdd, 0xdc, 0x10, 0x35, 0xbc, 0x5c, 0xb6, 0xca, 0x0a, };
static uint16_t c = 0x42;

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

Источник

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

Регистр сдвига с линейной обратной связью (LFSR) использует только сдвиг и логические операции.

Если вы используете массив, он становится Обобщенным регистром сдвига с линейной обратной связью (GLFSR), основным методом, который использует Mersenne Twister. Он циклически перебирает массив вместо сдвига всех битов на каждом шаге, так что вы можете иметь большое пространство состояний (от сотен до тысяч битов) с минимальными вычислительными затратами.

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

Источник

Нет, нет хороших значительно более быстрых алгоритмов через процессоры общего назначения. Как упоминали @Joachim Isaksson и @Michael Burr, мало что можно сделать, не снижая качества и не делая что-то странное. g: вычислить во время компиляции огромный список случайных чисел, тогда генерация во время выполнения будет быстрой.

Любой очень быстрый генератор случайных чисел использует специализированное оборудование. Поскольку вы пометили [микроконтроллер], проверьте процессор, который вы используете, чтобы увидеть, какие специализированные функции он может предоставить.

Далее: предоставление дополнительной информации для вашей потребности в PRN может помочь выявить некоторые новые идеи (длина числа, скорость: O(n) или время, степень случайности и т. Д.), Например, использование счетчика времени на основе микроконтроллера, модифицированного большим простым числом.,

Источник
Другие вопросы по тегам