|
|
  |
Простой ГСП на Си |
|
|
Guest_TSerg_*
|
Jan 17 2014, 19:28
|
Guests

|
Любой RNG на основе сдвигового регистра 8 р, но лучше - 16 р  u8 rnd8(void) { static u16 seed = 0; seed = (seed << 7) - seed + 251; return (u8)(seed + (seed>>8)); }
|
|
|
|
|
Jan 17 2014, 19:50
|

Гуру
     
Группа: Модераторы
Сообщений: 10 983
Регистрация: 23-11-05
Пользователь №: 11 287

|
Спасибо, коллеги за скорую помощь! Цитата(TSerg @ Jan 17 2014, 21:28)  Любой RNG на основе сдвигового регистра 8 р, но лучше - 16 р  u8 rnd8(void) { static u16 seed = 0; seed = (seed << 7) - seed + 251; return (u8)(seed + (seed>>8)); } Я только не пойму, если в теле функции переменная seed каждый раз обнуляется, то какой смысл в static?
|
|
|
|
|
Jan 17 2014, 22:04
|

Гуру
     
Группа: Модераторы
Сообщений: 10 983
Регистрация: 23-11-05
Пользователь №: 11 287

|
Спасибо, SM! Но, по правде говоря, ничего не понял. Вас на затруднит немного разжевать? Вот если у меня есть две переменные: Код unsigned char min = 2; unsigned char max = 30; и я вызываю функцию unsigned char rand(a, b ) : result = rand(min, max);желая получить число в указанном диапазоне. Как должно выглядеть её тело? Так? Код unsigned char rand(a, b) { static unsigned int rand_value return (unsigned char)((rand_value) % b) + a; }
|
|
|
|
|
Jan 18 2014, 07:38
|
Гуру
     
Группа: Свой
Сообщений: 7 946
Регистрация: 25-02-05
Из: Moscow, Russia
Пользователь №: 2 881

|
Цитата(Herz @ Jan 18 2014, 02:04)  Вас на затруднит немного разжевать?
желая получить число в указанном диапазоне. Как должно выглядеть её тело? Если за базу взять ф-цию, предложенную TSerg, то вот так: медленный код (он притащит библиотечную ф-цию деления с остатком): суть - тупое вычисление в лоб остатка от деления ограничиваемого числа на max. Код u8 rnd8(u8 max, u8 offset) { static u16 seed = 0; u8 temp;
seed = (seed << 7) - seed + 251;
temp = (u8)(seed + (seed>>8));
return (temp % max) + offset;
} самый быстрый код, но требующий маски, которая задается параметром ф-ции, и должна быть числом 2^n-1, ближайшим, больше либо равным "max". Суть кода - операция лог. И с маской, соответствующей требованию ближайшего, большего либо равного 2^n-1, к max, ограничивает значение неким числом 2^n-1, меньшим max*2, затем в одну итерацию вычитания по условию, число ограничивается уже max. Если требуется вычисление маски во время выполнения, то есть "max" задается не константами, и требуется максимальная скорость, то можно добавить получение маски по таблице (массиву констант на 256 значений - тут уж хотите быстро, раскошеливайтесь на память для таблиц, другие способы вычисления такой маски на АВР в любом случае будут в цикле до 8 итераций в худшем случае)... Код u8 rnd8(u8 mask, u8 max, u8 offset) { static u16 seed = 0; u8 temp;
seed = (seed << 7) - seed + 251;
temp = ((u8)(seed + (seed>>8))) & mask; if (temp >= max) temp -= max;
return temp + offset;
} вот еще вариант, с операцией вычисления остатка от деления, реализованной в теле ф-ции без использования библиотечных ф-ций, средне производительный. Суть - вычисление остатка от деления, как в первом варианте, но не "тупое в лоб", а умное, без лишних запчастей из библиотек, и без вычисления частного (которое по любому вычисляется библиотечной ф-цией, но отбрасывается при операции "%") Код u8 rnd8(u8 max, u8 offset) { static u16 seed = 0;
u8 temp, i; u16 sub;
seed = (seed << 7) - seed + 251;
temp = (u8)(seed + (seed>>8));
i=8; sub = max << 8;
do { sub >>= 1; if (sub >= temp) temp -= sub; } while (--i);
return temp + offset;
} Цитата(_Pasha @ Jan 18 2014, 11:30)  для данного случая это будет всегда выигрышнее, чем целочисленное деление Да щасссс... целочисленное деление всегда 8 итераций (см. мой третий вариант). А у вас.... прикиньте, например, для частного случая max = 3 и tmp=254.
|
|
|
|
|
Jan 18 2014, 10:55
|

Гуру
     
Группа: Модераторы
Сообщений: 10 983
Регистрация: 23-11-05
Пользователь №: 11 287

|
Странно, но вот у меня такая функция: Код unsigned char rnd8(unsigned char max) { static unsigned int seed = 0; unsigned char temp, i; unsigned int sub;
seed = (seed << 7) - seed + 251; temp = (unsigned char)(seed + (seed>>8)); i = 8; sub = max << 8;
do { sub >>= 1; if (sub >= temp) temp -= sub; } while (--i);
return temp; } (минимум опустил пока для простоты) при вызове: Код NUM = rnd8(MAX); где Код #define MAX 30 работает неверно. Диапазон не соблюдает. Более того, старший бит всегда 1.
|
|
|
|
|
Jan 18 2014, 11:30
|
Гуру
     
Группа: Свой
Сообщений: 7 946
Регистрация: 25-02-05
Из: Moscow, Russia
Пользователь №: 2 881

|
Цитата(Herz @ Jan 18 2014, 15:22)  Нет, я имею в виду, не возвращает ли функция int в этом случае вместо char после приведения? Или типом функции это задаётся строго? В контексте Вашего вопроса, приведения в "temp -= sub", это задается типом переменной temp, при присваивании в 8-битную переменную автоматически все лишнее обрезается, и оптимизатор, по идее, должен сам определить это, и использовать 8-битные операции для всего выражения (которое по ANSI должно было считаться в 16 битах, а потом обрезаться). Касаемо значения, возвращаемого функцией, да, оно строго задано типом в описании функции, и не может быть никаким, кроме заданного. UPD: PS по логике, кстати, в том выражении надо не temp приводить к типу sub, а наоборот, учитывая, что по условию там temp >= sub, что означает, что реальная разрядность числа в sub меньше либо равна 8. Т.е. для наглядности и для подсказки оптимизатору можно написать temp -= (u8) sub;
|
|
|
|
|
Jan 18 2014, 14:15
|
ʕʘ̅͜ʘ̅ʔ
    
Группа: Свой
Сообщений: 1 008
Регистрация: 3-05-05
Пользователь №: 4 691

|
Не нужно вам никакого деления и остатка от деления.
1. делаете генератор в полном диапазоне int16 или int8. с помощью LFSR. Вам написали.
2. рассматриваете выход генератора как fractional число Q1.15, если выход int16, или Q1.7, если выход int8. Таким образом у вас есть RNG с fractional выходом в диапазоне [-1; 1)
3. умножаем (fractional), прибавляем, сдвигаем, приводим типы (сделаете в удобной последовательности), чтобы получить нужный диапазон
можно обнулять старший бит и тогда на выходе RNG получать [0; 1). Дальнейшая арифметика в этом случае видится немного попроще. Будет, правда, слегка перекошенное распределение (для ненулевого числа x != 0 будет вероятность выпадения p(x); если же x = 0, то p(0) ~= 1.5*p(x) ), но для мигалки это не принципиально, мне кажется.
Итого: сдвиги, суммы, одно умножение
|
|
|
|
|
Jan 18 2014, 20:42
|
Гуру
     
Группа: Свой
Сообщений: 7 946
Регистрация: 25-02-05
Из: Moscow, Russia
Пользователь №: 2 881

|
Цитата(Fat Robot @ Jan 18 2014, 18:15)  одно умножение так вот в нем и зло. если нету ни аппаратного умножителя, ни аппаратного делителя, то и на умножение получим цикл на 8 итераций, и на нахождение остатка от деления тоже 8 итераций. При этом умножение, скорее, проиграет на 8-битном RNG и 8-битном процессоре по причине 16-битного суммирования в цикле против 8-битного вычитания, но выиграет - очень врядли (хотя, конечно, этот вопрос надо отдельно изучить, что оптимальнее на конкретной архитектуре). И при этом нахождение остатка не испортит распределение. Ну а если аппаратное умножение имеется, то тут, разумеется, совсем другой расклад по производительности. Но вроде в обычном PIC его и нету...
|
|
|
|
|
Jan 18 2014, 21:12
|

Lazy
     
Группа: Свой
Сообщений: 2 070
Регистрация: 21-06-04
Из: Ukraine
Пользователь №: 76

|
Цитата(Herz @ Jan 17 2014, 23:13)  Предположим, требуется моргать светодиодом с псевдослучайным интервалом от 2 до 30 секунд. Посоветуйте простую функцию на Си для генерации целых чисел в таком малом диапазоне. Пусть от 1 до 255 максимум. Функция rand() из библиотеки HT-PICC тяжеловата как-то... Что-то все все усложняют... На светодиод наверное человек смотреть будет? Так вот через несколько он забудет, что видел при этом моргании. Просто сделайте таблицу на пару минут и все... Или игровой автомат? Тогда запись на видео лишит всего дохода... П.С. Или Вам надо офигенно нормальное распределение? Увы - ничего не выйдет....
--------------------
"Everything should be made as simple as possible, but not simpler." - Albert Einstein
|
|
|
|
|
Jan 18 2014, 22:16
|

Гуру
     
Группа: Модераторы
Сообщений: 10 983
Регистрация: 23-11-05
Пользователь №: 11 287

|
Цитата(Fat Robot @ Jan 18 2014, 16:15)  Не нужно вам никакого деления и остатка от деления. Сразили! Я и слов-то таких не знаю: fractional.  Буде Ваша воля пояснить свою идею попроще, постараюсь разобраться... Цитата(SM @ Jan 18 2014, 22:42)  Ну а если аппаратное умножение имеется, то тут, разумеется, совсем другой расклад по производительности. Но вроде в обычном PIC его и нету... На данном этапе имеется PIC18, в котором аппаратное умножение присутствует. Но хочется перенести проект на PIC16, где на эту задачу желательно потратить минимум ресурсов. Цитата(Victor® @ Jan 18 2014, 23:12)  Что-то все все усложняют... На светодиод наверное человек смотреть будет? Так вот через несколько он забудет, что видел при этом моргании. Просто сделайте таблицу на пару минут и все... Или игровой автомат? Тогда запись на видео лишит всего дохода... П.С. Или Вам надо офигенно нормальное распределение? Увы - ничего не выйдет.... Да нет, светодиод - это пример, упрощение. На самом деле нужно посылать некий сигнал, но нерегулярно. Чтобы не привыкнуть. Таблица отпадает - памяти маловато. Хотя... Но, от добра добра не ищут: пример от ув. SM очень даже ничего.
|
|
|
|
|
Jan 18 2014, 23:55
|
ʕʘ̅͜ʘ̅ʔ
    
Группа: Свой
Сообщений: 1 008
Регистрация: 3-05-05
Пользователь №: 4 691

|
Объясню предельно просто, не жонглируя терминологией Пусть генератор после всех преобразований имеет выход X в диапазоне [0; (2^n)-1] нужно и можно найти такие постоянные значения Y и Z, чтобы значение числа round((X*Y) >> Z) лежало в диапазоне [0; max-min] Все, что для этого нужно это (((max-min) * X ) + (1 << (n - 1))) >> n. Пусть n=7, a max-min=27 X в диапазоне [0; 127] ((X*27)+64)>>7 будет лежать в диапазоне [0;27] выход операции умножения 16 бит Если операции умножения у вас нет, но есть немного свободы в выборе значения для разности max-min, то нужно выбрать такое значение, чтобы в нем было как можно меньше единиц в двоичных разрядах, тогда умножение из общего случая упростится в сумму сдвигов. пусть вместо 27 из примера вас устроит 24 = (2^4) + (2^3), тогда преобразование будет таким: (( X << 4 ) + ( X << 3 ) + 64 )>>7 и выход будет лежать в диапазоне [0;24] Цитата(Herz @ Jan 18 2014, 23:16)  Буде Ваша воля пояснить свою идею попроще, постараюсь разобраться...
|
|
|
|
Guest_TSerg_*
|
Jan 19 2014, 13:24
|
Guests

|
Использование чисто арифметических методов приведения диапазона ГСП к малым значениям может привести к весьма плачевным результатам в отношении качества их статистических свойств.
Лучше попробовать использование класса ГСП сразу генерирующего псевдо-случайные числа в желаемом амплитудном диапазоне (одновременно, к сожалению будет ограничен и период), к примеру класс LCG-генераторов: Si = ( A*Sii + B ) mod M
К примеру, при M=83, A=2, B=0 получаем простой ГСП с периодом P=M-1=82, амплитудами 1..82:
Sii = 1..82; // Например Sii := 1; --- Si := (Sii << 1) mod M; Sii := Si;
Вместо mod M: while Si<M do Si -= M;
или для данного A=2 даже: if Si > M then Si -= M;
P.S. Немногие удачные сочетания (A;M) c P=M-1: (5;22), (2,29), ..., (6;41), .., (5;167), (2,5,6,8..;227)...
|
|
|
|
Guest_TSerg_*
|
Jan 19 2014, 15:51
|
Guests

|
Цитата(SM @ Jan 19 2014, 18:40)  мои глюки повторяем  while Si>=M do Si -= M; Ну да, очепытка, т.к. все не читал  Ниже-то - правильно.
|
|
|
|
|
Jan 20 2014, 08:24
|
Гуру
     
Группа: Свой
Сообщений: 7 946
Регистрация: 25-02-05
Из: Moscow, Russia
Пользователь №: 2 881

|
Цитата(Herz @ Jan 20 2014, 02:06)  Мне кажется, результат будет ровно тем же, если часть чисел из распределения с большей амплитудой возвращать в заданный диапазон вычитанием константы по условию. Если считать саму вероятность появления того или иного кода, то тут будет выглядеть все очень просто: допустим, изначально у любого кода вероятность 1/256. Для случая, когда мы используем нахождение остатка, то для части кодов вероятность составит [256/N]/256, а для части ([256/N]-1)/256 ([] - ближайшее большее целое, тут я не знаю как спец-символ математический вставить), первому условию будут подчиняться первые 256 mod N кодов, 0....((256 mod N) - 1), второй части - оставшиеся N-(256 mod N) кодов (если я ничего не попутал). Причиной этому является то, что коды "заворачиваются в диапазон", перекрывая диапазон полностью, меньшее_целое(256/N) раз, а последний "заворот" происходит не полностью, перекрывая лишь первые (256 mod N) кодов, таким образом вероятность выпадения оставшихся кодов уменьшается. В худшем случае вдвое (1/256 и 2/256), ну и чем меньше N, тем меньше различие. UPD: Да, ну а если ГСЧ сразу строится по mod N, то у него изначально вероятности для всех генерируемых кодов равны, если, конечно, он построен правильно, то есть за весь его период каждый код выдается одинаковое кол-во раз.
|
|
|
|
|
Jan 20 2014, 13:01
|

Гуру
     
Группа: Модераторы
Сообщений: 10 983
Регистрация: 23-11-05
Пользователь №: 11 287

|
Цитата(TSerg @ Jan 19 2014, 15:24)  Лучше попробовать использование класса ГСП сразу генерирующего псевдо-случайные числа в желаемом амплитудном диапазоне (одновременно, к сожалению будет ограничен и период), к примеру класс LCG-генераторов: Si = ( A*Sii + B ) mod M
К примеру, при M=83, A=2, B=0 получаем простой ГСП с периодом P=M-1=82, амплитудами 1..82:
Sii = 1..82; // Например Sii := 1; --- Надеюсь, для А=2, В=0 и М=83 правильно записал на Си: Код unsigned char rnd8(void) { static unsigned char seed = 1; unsigned int temp;
temp = seed << 1; if(temp > 83) temp -= 83; seed = (unsigned char)temp;
return temp; } Цитата P.S. Немногие удачные сочетания (A;M) c P=M-1: (5;22), (2,29), ..., (6;41), .., (5;167), (2,5,6,8..;227)... Удачные в каком смысле? И как найдены?
|
|
|
|
Guest_TSerg_*
|
Jan 20 2014, 13:23
|
Guests

|
Сильно извиняюсь.. слегка забегаю в Инет, принимая поздравления за 58 лет  Удачные - в смысле тестирования ( автоматического подбора ) вариантов ГСП. А вообще, есть ряд достаточно объективных тестов DIEHARD, NIST - для ГСП это норма, по другому трудно судить о качестве.
|
|
|
|
Guest_TSerg_*
|
Jan 20 2014, 20:14
|
Guests

|
Спасибо за поздравление, Herz! Однако нам не пристало даже после празднования - праздновать, работаем-да  Поэтому, "special for you" - небольшой эксклюзивный тест, предложенного мной LCG-генератора. LCG/ГСП: M=83, A=2, B=0. Генерация временной последовательности порождает вот такой график: http://shot.qip.ru/00gZ9L-5OPovQkio/(изменение числа инициализации 1..82 породит только фазовый сдвиг от числа 1) Рассматривая график, понимаем, что явно присутствует зависимость ближайших от ближайших значений, а поэтому - устраиваем тест на автокорреляционную функцию: Удостоверяемся, в том, что данный ГСП не может претендовать на крипто-статус. http://shot.qip.ru/00gZ9L-6OPovQkip/С другой стороны, разговор шел, как минимум, о желательности равновероятности чисел в избранном диапазоне. Проверяем гистограмму. http://shot.qip.ru/00gZ9L-5OPovQkir/Что видим? Идеально-равномерное распределение по числам в заданном диапазоне. Т.е. каждое число из диапазона 1..81 встретилось только один раз за цикл. Что и требовалось, как понимаю. P.S. Это всего лишь небольшой экскурс в практику RNG. P.P.S. Не сомневаюсь, что здесь присутствуют специалисты более высокого класса, чем я и мои объяснения они могут трактовать по своему.
|
|
|
|
|
Jan 20 2014, 20:42
|
Гуру
     
Группа: Свой
Сообщений: 7 946
Регистрация: 25-02-05
Из: Moscow, Russia
Пользователь №: 2 881

|
Кстати, на сколько я помню, для любого линейно-конгруэнтного генератора справедливо вот это:
для генератора X(n)=( a*X(n-1) + b ) mod m; длина последовательности P = m тогда (и только тогда), когда:
- b и m взаимно просты (их НОД = 1) - a-1 кратно всем простым делителям m и a-1 кратно 4, если m кратно 4.
то есть, если эти условия выполнены, то a, b и m являются "удачными".
Ну и "претендовать на крипто-статус" линейно-конгруэнтный генератор не может в принципе... Это никак от АКФ не зависит, это зависит от того, на сколько сложно по какому-то количеству отсчетов генератора восстановить его функцию.
|
|
|
|
Guest_TSerg_*
|
Jan 20 2014, 20:53
|
Guests

|
Ну, так я и без претензий - просто сделал попытку объяснить/подобрать наипростейший RNG в диапазоне менее 8 бит с примитивным сохранением стат. значимости. Цитата(SM @ Jan 21 2014, 00:42)  Ну и "претендовать на крипто-статус" линейно-конгруэнтный генератор не может в принципе... Это никак от АКФ не зависит, Ишо как зависит
|
|
|
|
Guest_TSerg_*
|
Jan 20 2014, 21:04
|
Guests

|
Цитата(SM @ Jan 21 2014, 00:55)  Вот у M-последовательностей, генерируемых LFSR, АКФ ну очень красивая... А на "крипто-статус" им тоже претендовать ну никак не удается  Хм, кто бы сомневался  Лет так 40 назад, создал на основе всего лишь одного НИР большое подразделение - тестирование цифровых схем на основе сигнатурного анализа. Как раз M-последовательности. Как тест - работало  P.S. Когда возникла необходимость передачи данных с 6 км глубины на поверхность океана, вот тут и встала крипто-проблема в полный рост. Есс-но - решили. Это был 1988 г.
|
|
|
|
Guest_TSerg_*
|
Jan 21 2014, 07:41
|
Guests

|
Цитата Очень Вам признателен. Да не за, что - гости разошлись, а "моcк" всегда требует корма, увы  Цитата Это чтобы дельфины сообщение не перехватывали? Ага, такие небольшие дельфинчики от Office of Naval Intelligence ( ONI ).
|
|
|
|
|
Jan 22 2014, 06:04
|

Профессионал
    
Группа: Свой
Сообщений: 1 143
Регистрация: 30-09-08
Из: Новочеркасск
Пользователь №: 40 581

|
для задач типа случайного мигания светодиодом, т.е. для тех, где критерий случайности определяет человек-наблюдатель, в сильно стесненных условиях я использую тупо содержимое flash-памяти МК в качестве псевдослучайных чисел. Код char rand(void){ static __flash char *ptr; return ++ptr*; } если есть возможность - в качестве значения указателя (стартового или при обращении) использую содержимое счетчика таймера.
--------------------
Я бы взял частями... но мне надо сразу.
|
|
|
|
|
  |
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
|