Быстрые случайные логические значения

Question

Быстрые случайные логические значения

programming mathematics

Я ищу способ быстрого создания логических значений. Для логических значений обычно используется random(0,2);, но в моем случае мне нужно около 250 логических значений, а вызов random каждый раз медленный.

Поэтому я подумал об использовании всех битов случайного числа во всем диапазоне как таковом:

randomSeed(100); // Семя, чтобы всегда сохранять одну и ту же последовательность
long rdm = random(MIN,MAX);  // Генерируем число в диапазоне MIN,MAX типа long
long mask = 1;
for(int i=0; i<32; i++){
    if((rdm>>i)&mask){
        //сделай что-нибудь
    } else {
        // сделать что-то еще
    }
}

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

Что такое MIN и MAX, чтобы LONG random использовал все биты со значением в диапазоне от -2 147 483 648 до 2 147 483 647 (длинный тип arduino). Я пробовал несколько MIN и MAX, а также просто random();, но безуспешно.
Правильный ли это подход? Ожидаю ли я, что каждый бит будет равномерно распределен? Должен ли я использовать меньше битов, например random(0, 2^16); для "лучшего" распространение?
Есть ли какие-то исходные данные, которые хорошо или плохо подходят для этого?

Мой проект

Я работаю над устройством, изготовленным из светодиодных лент Neopixel. Это для визуального нейробиологического эксперимента, в котором каждый «пиксель» либо ВКЛ, либо ВЫКЛ. Мне нужна скорость, чтобы иметь возможность достигать высокой частоты обновления (60–100 Гц) с нормальным статистическим распределением, чтобы избежать систематической ошибки при анализе ответов нейронов. С таким подходом я могу достичь желаемой скорости, но меня беспокоит статистика. Поэтому мне нужно лучше понять поведение random(), чтобы сделать это правильно!

@Tom-tbt, 👍1

Обсуждение

вы уверены, что это будет быстрее?, @Juraj

Хороших генераторов псевдослучайных чисел очень мало. Я бы не стал доверять одному из библиотек микроконтроллера, который оптимизирован для скорости, а не для оптимальных статистических свойств. В AVR я бы предпочел базовый [no-parameter random()](https://www.nongnu.org/avr-libc/user-manual/group__avr__stdlib.html#ga114aeb1751119382aaf3340355b22cfd), который имеет 31 используемый бит, по сравнению с ядром Arduino, что только добавляет ошибок. И я настоятельно рекомендую вам проверить интересующие вас статистические свойства, прежде чем приступать к любому ГПСЧ., @Edgar Bonet

@Juraj да, это быстрее. Включая связь с Neopixel, когда я рисовал одно логическое значение для каждого светодиода, я отображал на частоте около 30-40 Гц. С помощью этого метода мне нужно всего 8 случайных чисел, чтобы получить 250 бит, которые позволяют отображать с частотой 100 Гц. Быстрый тест (Arduino Uno) для присвоения значения каждому светодиоду (всего 237): Этот метод: 1,6 мс -- Один ранд на светодиод: 22 мс -- (связь Neopixel: 2,05 мс), @Tom-tbt

@EdgarBonet Спасибо за совет, я буду использовать просто random(), чтобы иметь 31 бит. Я использую фиксированные семена, поэтому я также проверяю, как они распределяются., @Tom-tbt

@Juraj Я думаю, что [это сообщение в блоге](https://martin.ankerl.com/2018/12/08/fast-random-bool/) является подходящим эталоном, @Tom-tbt

2 ответа

@*Michel Keijzers* · Answer 1 · 2020-06-22 10:26-00:00

Я не пробовал сам, но в документации указано, что максимальное значение равно 2 147 483 647, что равно 2^31-1. Я ожидаю минимальное значение -2 ^ 31, то есть -2 148 483 648. Интересно, что вы имеете в виду под "без успеха".
Да, это правильный подход. «Идеальный» генератор случайных чисел должен иметь возможность генерировать все значения с равным распределением. Поскольку значения находятся в пределах [-2 ^ 31, 2 ^ 31-1], это означает, что используются все значения в пределах 32-битного значения, что автоматически означает, что все биты также равномерно распределены. Таким образом, вы можете выбрать отдельные биты (при условии, что вы используете весь диапазон MIN/MAX).
В принципе все семена хороши, если они случайны. В документации советуют брать значение неподключенного аналогового вывода. Если у вас нет ни одного неподключенного, вы можете использовать, например, функцию millis.

@*Majenko* · Answer 2 · 2020-06-22 14:54-00:00

Функция random() возвращает число от 0 до RANDOM_MAX (0x7FFFFFFFF). Функция random(min, max) берет значение из random() и манипулирует им, чтобы оно соответствовало указанному диапазону (вычисление разницы смещения, модуль случайного значения на этот разницу, затем добавьте меньшее смещение).

Это означает, что самый широкий диапазон, который вы можете получить, напрямую связан с random(), что совпадает с random(0, RANDOM_MAX). Однако это всегда будет только 31 бит, поэтому ваш старший бит всегда будет равен нулю.

Это не то, что вам нужно.

Лучшее, что вы можете сделать, чтобы получить 32-битные случайные данные, — это взять два случайных 31-битных значения и объединить их. Возможно, будет достаточно сдвинуть одно значение на один бит и объединить их вместе XOR:

uint32_t rand1 = random();
uint32_t rand2 = random();
uint32_t fullrand = (rand1 << 1) ^ rand2;

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