реклама на сайте
подробности

 
 
3 страниц V   1 2 3 >  
Reply to this topicStart new topic
> Генератор псевдослучайных чисел
DS
сообщение Sep 8 2006, 14:28
Сообщение #1


Гуру
******

Группа: СуперМодераторы
Сообщений: 3 096
Регистрация: 16-01-06
Из: Москва
Пользователь №: 13 250



Нужен генератор 9 битных псевдослучайных чисел, с периодом повторения 2 в 24 или около того.
Я так понимаю, что нужен 24 битный сдвиговый регистр с обратными связями и можно просто брать 9 бит с его разрядов. Или все сложнее ?
Книжки у меня есть, но, честно говоря некогда разбираться, поскольку вопрос одноразовый.
С каких разрядов нужно брать обратную связь для получения правильного цикла ?


--------------------
Не бойтесь тюрьмы, не бойтесь сумы, не бойтесь мора и глада, а бойтесь единственно только того, кто скажет - "Я знаю как надо". А. Галич.
Go to the top of the page
 
+Quote Post
bve
сообщение Sep 8 2006, 15:16
Сообщение #2


Местный
***

Группа: Свой
Сообщений: 316
Регистрация: 20-02-05
Из: Ленинградская обл.
Пользователь №: 2 765



Цитата(DS_ @ Sep 8 2006, 18:28) *
Нужен генератор 9 битных псевдослучайных чисел, с периодом повторения 2 в 24 или около того.
Я так понимаю, что нужен 24 битный сдвиговый регистр с обратными связями и можно просто брать 9 бит с его разрядов. Или все сложнее ?
Книжки у меня есть, но, честно говоря некогда разбираться, поскольку вопрос одноразовый.
С каких разрядов нужно брать обратную связь для получения правильного цикла ?

Долго пользуюсь 32-разрядным генератором с полиномом 0x4004000f.
Алгоритм таков: Xn+1=Xn<<1
IF ( Xn+1<0 ) Xn+1=Xn+1 XOR 0x4004000F

Особенно приятно, что в этом генераторе цепочка бит любой длины - случайна.
Я брал и 2 раза по 16, и 3 раза по 10 для экономии вычислений.
Go to the top of the page
 
+Quote Post
DS
сообщение Sep 8 2006, 15:25
Сообщение #3


Гуру
******

Группа: СуперМодераторы
Сообщений: 3 096
Регистрация: 16-01-06
Из: Москва
Пользователь №: 13 250



Цитата(bve @ Sep 8 2006, 19:16) *
IF ( Xn+1<0 )


Я вот этого не понял - XOR делается, только если старший бит ==1 ? Это зачем ?


--------------------
Не бойтесь тюрьмы, не бойтесь сумы, не бойтесь мора и глада, а бойтесь единственно только того, кто скажет - "Я знаю как надо". А. Галич.
Go to the top of the page
 
+Quote Post
vladv
сообщение Sep 8 2006, 20:59
Сообщение #4


Частый гость
**

Группа: Участник
Сообщений: 128
Регистрация: 7-06-06
Пользователь №: 17 825



Цитата(DS_ @ Sep 8 2006, 19:25) *
Цитата(bve @ Sep 8 2006, 19:16) *


IF ( Xn+1<0 )


Я вот этого не понял - XOR делается, только если старший бит ==1 ? Это зачем ?

По определению сдвигового регистра с линейными обратными связями (в форме Галуа).
Для указанного полинома (X**32+X**30+X**26+X**3+X**2+X**1+1) старший бит
регистра "XOR-ится в разряды" 0,1,2,3,26 и 30:
X[0] <= X[31]
X[1] <= X[31]^X[0]
X[2] <= X[31]^X[1]
X[3] <= X[31]^X[2]
X[4] <= X[3]
X[5] <= X[4]
...
X[25] <= X[24]
X[26] <= X[31]^X[25]
X[27] <= X[26]
...
X[29] <= X[28]
X[30] <= X[31]^X[29]
X[31] <= X[30]


Если просто брать 9 бит с разных разрядов, то будут встречаться "не совсем случайные"
подпоследовательности. Например, для 9-ти старших бит 24-х разрядного регистра в
какой-то момент будет такая последовательность:
01: 000000000
02: 000000000
...
14: 000000000
15: 000000000
16: 000000001
17: 000000010
...
23: 010000000
24: 100000000
Go to the top of the page
 
+Quote Post
DS
сообщение Sep 8 2006, 21:09
Сообщение #5


Гуру
******

Группа: СуперМодераторы
Сообщений: 3 096
Регистрация: 16-01-06
Из: Москва
Пользователь №: 13 250



Мне собственно полином был нужен под 32 разряда. Если делать в железке, то достаточно с указанных разрядов все просуммировать (XOR) и завести на 0 разряд, а код формировать 9 -ти кратным выполением сдвига , так ? Что нельзя брать кусок этого же регистра я уже понял - пример с нулями сам просится.


--------------------
Не бойтесь тюрьмы, не бойтесь сумы, не бойтесь мора и глада, а бойтесь единственно только того, кто скажет - "Я знаю как надо". А. Галич.
Go to the top of the page
 
+Quote Post
vladv
сообщение Sep 9 2006, 13:04
Сообщение #6


Частый гость
**

Группа: Участник
Сообщений: 128
Регистрация: 7-06-06
Пользователь №: 17 825



Цитата(DS_ @ Sep 9 2006, 01:09) *
Мне собственно полином был нужен под 32 разряда. Если делать в железке, то достаточно с указанных разрядов все просуммировать (XOR) и завести на 0 разряд, а код формировать 9 -ти кратным выполением сдвига , так ?


Почти достаточно. Еще надо перевернуть их порядок, иначе рискуите не получить последовательность
максимальной длины.

Вообще говоря, есть две формы построения LFSR:
- в форме Фибоначи, это когда с указанных разрядов все просуммировать (XOR) и
заводится на 0 разряд
- в форме Галуа, это когда старший разряд суммируется в указанные разряды (как в примере bve).
Для полинома 0x4004000f имеем:
- "в указанные разряды" для Галуа: (32), 30, 26,3,2,1,0
- "с указанных разрядов" для Фибоначи: 32,31,30,29,6,2, (0)
Для обоих форм длина последовательности будет одинаковой и даже это общий случай) последовательность бит со старшего (а может быть и для любого) разряда с точностью до фазы
у обоих форм будет одинаковая. Однако последовательность состояний регистров в целом
для разных форм будут разные.

Если интересно, могу предложить небольшую статью:
http://www.newwaveinstruments.com/resource...ter_lfsr.htm
Там есть примеры других коэффициентов для различных длин регистров.

Кстати, если для 32-разрядного регистра формировать 9-ти разрядный код 9-ти кратным сдвигом,
то длина последовательности будет 1431655765, что намного больше, чем 2**24 smile.gif.

Сообщение отредактировал vladv - Sep 9 2006, 13:06
Go to the top of the page
 
+Quote Post
vladv
сообщение Sep 9 2006, 13:37
Сообщение #7


Частый гость
**

Группа: Участник
Сообщений: 128
Регистрация: 7-06-06
Пользователь №: 17 825



Цитата(vladv @ Sep 9 2006, 17:04) *
Цитата(DS_ @ Sep 9 2006, 01:09) *

Мне собственно полином был нужен под 32 разряда. Если делать в железке, то достаточно с указанных разрядов все просуммировать (XOR) и завести на 0 разряд, а код формировать 9 -ти кратным выполением сдвига , так ?


Почти достаточно. Еще надо перевернуть их порядок, иначе рискуите не получить последовательность
максимальной длины.



Был неправ. Можно и не переворачивать. В этом случае последовательность также будет максимальной длины, но иметь обратный порядок (на отдельном бите).

Сообщение отредактировал vladv - Sep 9 2006, 13:40
Go to the top of the page
 
+Quote Post
DS
сообщение Sep 9 2006, 14:52
Сообщение #8


Гуру
******

Группа: СуперМодераторы
Сообщений: 3 096
Регистрация: 16-01-06
Из: Москва
Пользователь №: 13 250



Спасибо за ссылку ! Таблица полиномов - то, что нужно. Про поля Галуа я, видимо, все-таки почитаю, надо только выбрать пару дней спокойных, чтобы подумать. Заинтересовала связь неприводимых полиномов и регистров сдвига biggrin.gif

Да, что-то приведенного полинома нет в таблице - ошибка в полиноме или он из секретных ?


--------------------
Не бойтесь тюрьмы, не бойтесь сумы, не бойтесь мора и глада, а бойтесь единственно только того, кто скажет - "Я знаю как надо". А. Галич.
Go to the top of the page
 
+Quote Post
gab
сообщение Sep 10 2006, 00:34
Сообщение #9


Местный
***

Группа: Свой
Сообщений: 376
Регистрация: 30-06-04
Из: Moskow
Пользователь №: 218



Ещё можете поискать по слову "tauswothe". При достаточно маленьких требуемых ресурсах он даёт достаточно длинную последовательность...


--------------------
serpents on the way to paradise -
dying for love, fighting for ages.

Go to the top of the page
 
+Quote Post
Oldring
сообщение Sep 14 2006, 14:33
Сообщение #10


Гуру
******

Группа: Свой
Сообщений: 3 041
Регистрация: 10-01-05
Из: Москва
Пользователь №: 1 874



Цитата(DS_ @ Sep 8 2006, 18:28) *
Нужен генератор 9 битных псевдослучайных чисел, с периодом повторения 2 в 24 или около того.
Я так понимаю, что нужен 24 битный сдвиговый регистр с обратными связями и можно просто брать 9 бит с его разрядов. Или все сложнее ?


Это зависит от требования к качеству непредсказуемости последовательности. Например, для криптографических задач LFSR как генератор случайных чисел абсолютно неприменим. Кроме того, LFSR как генератор именно чисел а не битовых последовательностей считается довольно посредственным - могут вылезти неожиданные эффекты если использовать эти числа в неподходящем месте. А в остальном все тривиально - выбор полиномов и длин безграничен. Если конечно период последовательности допустипо делать _больше_ требуемого минимума и заметные корреляции на длинах меньше периода допустимы.

Проиллюстрирую почему LFSR как генератор чисел плох. Например, такая примитивная реализация. Чтобы получить очередное число мы прокручиваем LFSR на один бит и берем 9 соседних разрядов. С вероятностью 1/2 очередное число будет в ровно два раза больше/меньше предыдущего, в зависимости от направления сдвига. Для многих задач это неприемлемо. Разные ухищрения позволяют улучшить последовательность получаемых чисел - но все равно она может оказаться неожиданно плохой. Как получать "хорошие" последовательности чисел - это отдельная наука, начните с Кнута.


--------------------
Пишите в личку.
Go to the top of the page
 
+Quote Post
DS
сообщение Sep 14 2006, 17:14
Сообщение #11


Гуру
******

Группа: СуперМодераторы
Сообщений: 3 096
Регистрация: 16-01-06
Из: Москва
Пользователь №: 13 250



Кнута я как бы читал. Про линейно-конгруэнтные генераторы помню до сих пор и пользуюсь иногда.
У меня сейчас другая задача - размазать в спектре сигнала вредный артефактный пик, который потенциально может пустить вразнос систему управления.
Для железа сдвиговый регистр - самое то, а что надо делать не 1 а 9 сдвигов, уже написано было.


--------------------
Не бойтесь тюрьмы, не бойтесь сумы, не бойтесь мора и глада, а бойтесь единственно только того, кто скажет - "Я знаю как надо". А. Галич.
Go to the top of the page
 
+Quote Post
Oldring
сообщение Sep 14 2006, 17:54
Сообщение #12


Гуру
******

Группа: Свой
Сообщений: 3 041
Регистрация: 10-01-05
Из: Москва
Пользователь №: 1 874



Цитата(DS_ @ Sep 14 2006, 21:14) *
Для железа сдвиговый регистр - самое то, а что надо делать не 1 а 9 сдвигов, уже написано было.


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

Исходя из этого, возможно, что 1 сдвиг, что 9 - разницу не заметите. 9 сдвигов устраняют упомянутую мною неприятность - но все равно такая псевдослучайная последовательность может не проходить по довольно простым критериям случайности. См. например упражнение 3.2.2.18 из Кнута на русском 2000 года издания.


--------------------
Пишите в личку.
Go to the top of the page
 
+Quote Post
DS
сообщение Sep 14 2006, 18:02
Сообщение #13


Гуру
******

Группа: СуперМодераторы
Сообщений: 3 096
Регистрация: 16-01-06
Из: Москва
Пользователь №: 13 250



Энергия в пике не превышает 10-20% энергии шума в полосе пропускания, поэтому мне важно просто чтобы длина цикла была большой, чтобы не перегнать этот пик в низкие частоты, где у меня шум маленький, а усиление большое. А то, что будет слегка неравномерный спектр, мне не важно - я пик размажу на ширину, вдесятеро большую полосы пропускания, он в белом шуме утонет.


--------------------
Не бойтесь тюрьмы, не бойтесь сумы, не бойтесь мора и глада, а бойтесь единственно только того, кто скажет - "Я знаю как надо". А. Галич.
Go to the top of the page
 
+Quote Post
Макс_Мат
сообщение Mar 23 2007, 17:45
Сообщение #14


Частый гость
**

Группа: Свой
Сообщений: 76
Регистрация: 21-03-07
Пользователь №: 26 378



ты был почти прав. Только тебе нужен 24+9=33 разрядный генератор. Полиномы посмотри поиском, либо Питерсон, Уэлдон "Коды, исправляющиие ошибки"
Go to the top of the page
 
+Quote Post
bve
сообщение Mar 25 2007, 18:13
Сообщение #15


Местный
***

Группа: Свой
Сообщений: 316
Регистрация: 20-02-05
Из: Ленинградская обл.
Пользователь №: 2 765



А кто-нибудь знает БЫСТРЫй генератор с нормальным распределением?
Go to the top of the page
 
+Quote Post
Макс_Мат
сообщение Mar 26 2007, 13:37
Сообщение #16


Частый гость
**

Группа: Свой
Сообщений: 76
Регистрация: 21-03-07
Пользователь №: 26 378



Цитата(bve @ Mar 25 2007, 19:13) *
А кто-нибудь знает БЫСТРЫй генератор с нормальным распределением?


А куда быстрее ГПСП, а результат накпливающая сумма за несколько сдвигов?
Go to the top of the page
 
+Quote Post
Pathfinder
сообщение Mar 26 2007, 22:08
Сообщение #17


Местный
***

Группа: Свой
Сообщений: 275
Регистрация: 29-06-05
Пользователь №: 6 400



Один из самых быстрых способов получить нормальное распределение - метод Бокса-Мюллера (нелинейное преобразование двух псевдослучайных последовательностей с равномерным распределением на интервале 0..1). Делал такую штуку на блекфине, вычисление одной выборки (включая генераторы ПСП) занимает 73 такта на выборку(выборка двухканальная). Для вычисления нелинейных преобразований использовал кусочно-линейную аппроксимацию. Подозреваю, что на ПЛИС скорость будет просто бешеная.


--------------------
ADC / DAC LC Filter Designer — Удобный инструмент проектирования LC-фильтров для ЦАП и АЦП
Go to the top of the page
 
+Quote Post
Макс_Мат
сообщение Mar 27 2007, 11:58
Сообщение #18


Частый гость
**

Группа: Свой
Сообщений: 76
Регистрация: 21-03-07
Пользователь №: 26 378



Молодой человек, скорости скоростями, но ко всему надо подходить с головой. На ГПСП на том же блэкфине результат получается за максимум 2-4 такта. Так куда быстрее то?
Go to the top of the page
 
+Quote Post
Pathfinder
сообщение Mar 27 2007, 13:41
Сообщение #19


Местный
***

Группа: Свой
Сообщений: 275
Регистрация: 29-06-05
Пользователь №: 6 400



Макс_Мат Результат чего?!


--------------------
ADC / DAC LC Filter Designer — Удобный инструмент проектирования LC-фильтров для ЦАП и АЦП
Go to the top of the page
 
+Quote Post
Макс_Мат
сообщение Mar 28 2007, 14:19
Сообщение #20


Частый гость
**

Группа: Свой
Сообщений: 76
Регистрация: 21-03-07
Пользователь №: 26 378



Цитата(Pathfinder @ Mar 27 2007, 14:41) *
Макс_Мат Результат чего?!


нормально распределенные числа вообщето. О них же речь, насколько я понимаю
Go to the top of the page
 
+Quote Post
bve
сообщение Mar 28 2007, 18:44
Сообщение #21


Местный
***

Группа: Свой
Сообщений: 316
Регистрация: 20-02-05
Из: Ленинградская обл.
Пользователь №: 2 765



Цитата(Макс_Мат @ Mar 26 2007, 14:37) *
А куда быстрее ГПСП, а результат накпливающая сумма за несколько сдвигов?

Сумма 12-15 равномернораспределенных отсчетов для моей задачи на сигнальном процессоре - долгонько. Вот и ищу "прямой" метод тактов на 3-4 на отсчет.....
Go to the top of the page
 
+Quote Post
Pathfinder
сообщение Mar 29 2007, 14:57
Сообщение #22


Местный
***

Группа: Свой
Сообщений: 275
Регистрация: 29-06-05
Пользователь №: 6 400



Макс_Мат, а ну-ка просветите, что это вы там такое за 2-4 такта считаете??? сумму двух псп что-ли?


--------------------
ADC / DAC LC Filter Designer — Удобный инструмент проектирования LC-фильтров для ЦАП и АЦП
Go to the top of the page
 
+Quote Post
Макс_Мат
сообщение Apr 4 2007, 15:08
Сообщение #23


Частый гость
**

Группа: Свой
Сообщений: 76
Регистрация: 21-03-07
Пользователь №: 26 378



Мне интересно, кто сможет дать определение нормального распределения на конечном множестве?
Go to the top of the page
 
+Quote Post
Oldring
сообщение Apr 4 2007, 15:58
Сообщение #24


Гуру
******

Группа: Свой
Сообщений: 3 041
Регистрация: 10-01-05
Из: Москва
Пользователь №: 1 874



Цитата(Макс_Мат @ Apr 4 2007, 16:08) *
Мне интересно, кто сможет дать определение нормального распределения на конечном множестве?


Нет, нет, давайте все-таки двигаться вперед по-порядку. Раз люди в этой ветке что-то обсуждали, значит, возможно, они понимали, о чем беседуют. Вы нарисовались, такой весь из себя красивый и умный, сказали (почти) что все вокруг необразованные болваны, и что нормальное распределение можно генерировать за 4 такта некоего процессора. У меня лично возникло серьезное подозрение, что Вы под нормальным распределением понимали нечто, что другие люди совершенно нормальным распределением назвать не могут даже с очень большой натяжкой, и уж заведомо не подразумевали при обсуждении в этой ветке. Поэтому прежде, чем мы с Вами дойдем до обсуждения смысла использованных ранее в этой ветке уважаемыми собеседниками терминов, а также предельных переходов и аппроксимации непрерывных распределений дискретными, пожалуйста, разъясните все-таки подробно, что именно Вы подразумевали, когда утверждали, что некоторое "нормальное распределение" можно генерировать за 4 такта?


--------------------
Пишите в личку.
Go to the top of the page
 
+Quote Post
Макс_Мат
сообщение Apr 4 2007, 17:00
Сообщение #25


Частый гость
**

Группа: Свой
Сообщений: 76
Регистрация: 21-03-07
Пользователь №: 26 378



Такое ощущение, что я попал не в профессиональный форум, а в общеобразовательный. Идею дал - мало, "на пальцах" покажи. Надеюсь матлабная модели хватит? Для непосвященных - здесь randint-128 генерит равномер, т.е. описывает состояние регистра псп

R=[];
s=0;
delLine = zeros(32,1);
for i=1:10000,
v = randint(1,1,256)-128;
s = s + v - delLine(end);
delLine = [v; delLine(1:end-1)];
R=[R;s];
end;
Go to the top of the page
 
+Quote Post
Oldring
сообщение Apr 4 2007, 17:51
Сообщение #26


Гуру
******

Группа: Свой
Сообщений: 3 041
Регистрация: 10-01-05
Из: Москва
Пользователь №: 1 874



Цитата(Макс_Мат @ Apr 4 2007, 18:00) *
Такое ощущение, что я попал не в профессиональный форум, а в общеобразовательный. Идею дал - мало, "на пальцах" покажи. Надеюсь матлабная модели хватит? Для непосвященных - здесь randint-128 генерит равномер, т.е. описывает состояние регистра псп

R=[];
s=0;
delLine = zeros(32,1);
for i=1:10000,
v = randint(1,1,256)-128;
s = s + v - delLine(end);
delLine = [v; delLine(1:end-1)];
R=[R;s];
end;


Спасибо, теперь стало понятно, что имеется в виду именно скользящее среднее по 32 равномерно распределенным независимым отсчетам. Это, конечно, не так плохо, как я подумал с самого начала. Распределение у такого генератора, конечно, близко к нормальному - но есть одна засада, из-за которой для многих приложений, для которых нужно именно нормальное распределение, он неприменим. От генераторов случайных чисел обычно требуют еще одно свойство - генерируемая последовательность должна быть белой. У этого же генератора автокорреляционная функция представляет собой аккуратный треугольник, простирающийся на +-31 отсчет. Почему-то Вы об это важнейшее свойство упомянуть забыли. Кстати, ранее в этой ветке предлагалось суммирование нескольких равномерно распределенных отсчетов для получения приближения к нормальному распределению.


--------------------
Пишите в личку.
Go to the top of the page
 
+Quote Post
Макс_Мат
сообщение Apr 5 2007, 09:21
Сообщение #27


Частый гость
**

Группа: Свой
Сообщений: 76
Регистрация: 21-03-07
Пользователь №: 26 378



Нигде выше не сказано о корреляционных свойствах последовательности. Вот какое важное значение имеет строгость в высказываниях. Но уважаемый Олдринг, а для чего существуют литература, знания, опыт, мышление и т.д.? Что мешает нам сделать указанную последовательность "белой"? (Хотя, конечно, строго белым нельзя называть функции на конечных множествах). Что мешает нам рандомизировать знак? А, именно, либо использовать второй псп либо использовать для этого произвольно выбраный разряд генератора (кроме первого разумеется). Посмотрите что получится. И довольствуйтесь приобретенным опытом.
Go to the top of the page
 
+Quote Post
Oldring
сообщение Apr 5 2007, 11:07
Сообщение #28


Гуру
******

Группа: Свой
Сообщений: 3 041
Регистрация: 10-01-05
Из: Москва
Пользователь №: 1 874



Цитата(Макс_Мат @ Apr 5 2007, 10:21) *
Нигде выше не сказано о корреляционных свойствах последовательности. Вот какое важное значение имеет строгость в высказываниях. Но уважаемый Олдринг, а для чего существуют литература, знания, опыт, мышление и т.д.? Что мешает нам сделать указанную последовательность "белой"? (Хотя, конечно, строго белым нельзя называть функции на конечных множествах). Что мешает нам рандомизировать знак? А, именно, либо использовать второй псп либо использовать для этого произвольно выбраный разряд генератора (кроме первого разумеется). Посмотрите что получится. И довольствуйтесь приобретенным опытом.


За четыре такта?

А для чего Вы вообще что-то пишете? Какой в этом смысл?
Лично мне от Вас был интересен только способ быстрого построения генератора с нормальным распределением. Больше ничего. Я подумал, что может быть Вы знаете нечто, что другие в это ветке не знают? Оказалось, что Ваш способ с заковыкой и по сути мало отличается от описанного коллегами ранее. Нет, конечно, для некоторых узкоспециализированных задач он подойдет - но, скорее всего, в этих задачах было бы достаточно просто выходы LFSR.

P.S. Надеюсь, написав про невозможность получения белой случайной последовательности на конечных множествах, Вы имели в виду не то, что написали? Формализуйте, пожалйста, Ваше высказывание.

P.P.S. Что получится в результате экспериментов - разъясните, пожалуйста. Мне очень интересно. Кроме увеличения времени вычисления, конечно.

P.P.P.S. Здесь редко формулируют теоремы с математической точностью. Хороший тон - думать о том, что люди еще и подразумевают. Независимость отсчетов - это обычное требование для хороших генераторов.


--------------------
Пишите в личку.
Go to the top of the page
 
+Quote Post
Макс_Мат
сообщение Apr 5 2007, 11:28
Сообщение #29


Частый гость
**

Группа: Свой
Сообщений: 76
Регистрация: 21-03-07
Пользователь №: 26 378



R=[];
s=0;
delLine = zeros(32,1);
for i=1:10000,
v = randint(1,1,256)-128;
s = s + v - delLine(end);
delLine = [v; delLine(1:end-1)];
g = s;
if randint(1,1,2)==0,
g = -g;
end;
R=[R;g];
end;

Что то я перестал вас понимать...
"Лично мне от Вас был интересен только способ быстрого построения генератора с нормальным распределением".
Я показал вам генератор, в котором можно не то что разрядность чисел регулировать, а также(!) корреляционные свойства. Если вам нужны зависимые отчеты, пожалуйста, если нужны не зависимые, то тоже пожалуйста! Количество операций при этом константа и выгодно отличается от приведенных выше!

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

psps только сейчас пришло в голову, может вам еще и код для сигнальника выложить? Говорите для какого? А может тогда вообще возьмете меня к себе на подработку? Сдается мне, что пока у нас в стране такие "спецы", долго еще будем после китая и кореи находиться
Go to the top of the page
 
+Quote Post
Oldring
сообщение Apr 5 2007, 12:13
Сообщение #30


Гуру
******

Группа: Свой
Сообщений: 3 041
Регистрация: 10-01-05
Из: Москва
Пользователь №: 1 874



Цитата(Макс_Мат @ Apr 5 2007, 12:28) *
Я показал вам генератор, в котором можно не то что разрядность чисел регулировать, а также(!) корреляционные свойства. Если вам нужны зависимые отчеты, пожалуйста, если нужны не зависимые, то тоже пожалуйста! Количество операций при этом константа и выгодно отличается от приведенных выше!


Нет, спасибо, код для сигнальника не нужен. Матлабовского скрипта достаточно.
Какие могут быть обиды? У меня, например, складывается впечатление, что Вы, пытаясь советовать коллегам алгоритмы генерации случайных чисел, не читали Кнута. Потому что пытаетесь порождать на лету методы генерации откровенно плохих случайных чисел. Может быть, Вам стоит с ознакомиться с этой классической книгой? Без обид?

Знаете, был когда-то такой популярный в СССР компьютер - ZX Spectrum. Если для него написать программу, в которой последовательно генерируемые числа рисовать в виде точек на экране - попарно X и Y координаты, то точки начинали вастраиваться в сетку линий. Такой тест - один из простейших критериев качества генератора случайных чисел, описанный в Кнуте. Называется критерием серий.

Для вашего генератора получается крест.

Прикрепленное изображение


Будет ли это крест на Вашем генераторе, или этот генератор можно будет использовать в конкретном алгоритме - зависит от алгоритма. Но обнаружить побочные эффекты будет, конечно, несколько сложнее. За счет некоторого замедления времени работы первоначального генератора.


--------------------
Пишите в личку.
Go to the top of the page
 
+Quote Post
Макс_Мат
сообщение Apr 5 2007, 14:50
Сообщение #31


Частый гость
**

Группа: Свой
Сообщений: 76
Регистрация: 21-03-07
Пользователь №: 26 378



Удивительно как вы неуклонно не хотите думать. Ведь все же уже разжевано до безобразия! Поймите, что именно мышление ведет к прогрессу и нельзя этой функции, данной нам свыше, допускать атрофироваться. Решение задачи можно сравнить с написанием картины - один, два штрижка и она превращается в шедевр. Но художник, опирается на внутренее чувство окружающего мира, а мы - на мышление(!).

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

R=[];
s=0;
delLine = zeros(12,1);
mas=zeros(1,256);
for i=1:10000,
a = randint(1,1,256)+1;
v = a - 128;
s = s + v - delLine(end);
delLine = [v; delLine(1:end-1)];
g = mas(a);
mas(a) = s;
R=[R;g];
end;

ps меня удивило, что Вы, Олдрин, непонаслышке знакомы с синклером, думаю с радио-86рк тоже. Чувствуется старая закалка, не то, что нынешние студенты, которые живут с ожиданием, что все за них сделают...С Вами приятно общаться, но все же, настоятельно рекомендую вникать глубже в суть задач...есть у Вас такой небольшой порочек...
Go to the top of the page
 
+Quote Post
Oldring
сообщение Apr 5 2007, 15:10
Сообщение #32


Гуру
******

Группа: Свой
Сообщений: 3 041
Регистрация: 10-01-05
Из: Москва
Пользователь №: 1 874



Цитата(Макс_Мат @ Apr 5 2007, 15:50) *
Удивительно как вы неуклонно не хотите думать. Ведь все же уже разжевано до безобразия! Поймите, что именно мышление ведет к прогрессу и нельзя этой функции, данной нам свыше, допускать атрофироваться. Решение задачи можно сравнить с написанием картины - один, два штрижка и она превращается в шедевр. Но художник, опирается на внутренее чувство окружающего мира, а мы - на мышление(!).

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

R=[];
s=0;
delLine = zeros(12,1);
mas=zeros(1,256);
for i=1:10000,
a = randint(1,1,256)+1;
v = a - 128;
s = s + v - delLine(end);
delLine = [v; delLine(1:end-1)];
g = mas(a);
mas(a) = s;
R=[R;g];
end;

ps меня удивило, что Вы, Олдрин, непонаслышке знакомы с синклером, думаю с радио-86рк тоже. Чувствуется старая закалка, не то, что нынешние студенты, которые живут с ожиданием, что все за них сделают...С Вами приятно общаться, но все же, настоятельно рекомендую вникать глубже в суть задач...есть у Вас такой небольшой порочек...


Постепенно переходим к криптографии?

Мышление не заменяет образование. Кнута Вы ведь так и не прочитали?

Да, Вы избавились от сильной связи между соседними отсчетами. С третьей попытки. Все равно, без тщательного анализа нельзя утверждать, что Ваш доморощенный алгоритм генерирует достаточно хорошие случайные числа. Критериев их качества ведь до фига. К сожалению, незнание недостатков обычно не устраняет сами недостатки.

P.S. РКшки у меня не было. Журналы Радио читал. Но тогда оставалось только завидовать друзьям. С Синклерами, действительно, знаком не понаслышке. Хорошая была школа.


--------------------
Пишите в личку.
Go to the top of the page
 
+Quote Post
Макс_Мат
сообщение Apr 5 2007, 15:16
Сообщение #33


Частый гость
**

Группа: Свой
Сообщений: 76
Регистрация: 21-03-07
Пользователь №: 26 378



Это не доморощенный алгоритм. Он подробно исследован и запатентован. Я собственно оттуда и узнал о нем. Автора не помню. Кстати, кто-то из соотечественников, Чикин, кажется...

Сообщение отредактировал Макс_Мат - Apr 5 2007, 15:26
Go to the top of the page
 
+Quote Post
Oldring
сообщение Apr 5 2007, 15:41
Сообщение #34


Гуру
******

Группа: Свой
Сообщений: 3 041
Регистрация: 10-01-05
Из: Москва
Пользователь №: 1 874



Цитата(Макс_Мат @ Apr 5 2007, 16:16) *
Это не доморощенный алгоритм. Он подробно исследован и запатентован. Я собственно оттуда и узнал о нем. Автора не помню. Кстати, кто-то из соотечественников, Чикин, кажется...


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

Ну так ведь первые две Ваши реализации ведь были имменно доморощенными?

P.S. Помню, некоторое время назад прочитал сообщение, что в каких-то вычислениях по методу Монте-Карло было обнаружено систематическое смещение, потому что использовался недостаточно хороший генератор случайных чисел. И так бывает.


--------------------
Пишите в личку.
Go to the top of the page
 
+Quote Post
Макс_Мат
сообщение Apr 5 2007, 15:57
Сообщение #35


Частый гость
**

Группа: Свой
Сообщений: 76
Регистрация: 21-03-07
Пользователь №: 26 378



Согласен. Я сам столкнулся с необходимостью реализации быстрых алгоритмов генерации и наткнулся на этот алгоритм. По мере тестов (именно практических на сигналыче) получали различные модификации.

ps Кстати, Вы не смотрели матлабовский генератор? Уж слишком подозрительно граммотно он сделан. А алгоритмиками матлабовцы не хотят делиться, или я плохо искал... Что думаете?
Go to the top of the page
 
+Quote Post
Oldring
сообщение Apr 5 2007, 16:08
Сообщение #36


Гуру
******

Группа: Свой
Сообщений: 3 041
Регистрация: 10-01-05
Из: Москва
Пользователь №: 1 874



Цитата(Макс_Мат @ Apr 5 2007, 16:57) *
ps Кстати, Вы не смотрели матлабовский генератор? Уж слишком подозрительно граммотно он сделан. А алгоритмиками матлабовцы не хотят делиться, или я плохо искал... Что думаете?


Нет, не смотрел. Вопрос в общем-то детально меня не особо интересовал. Работает - и ладно, особо важные исследования с ним я не проводил.

Это поможет?

Цитата
% References
%
% [1] C.B. Moler (2004) Numerical Computing with MATLAB, SIAM, 336pp.
% Available on-line at http://www.mathworks.com/moler.
%
% [2] G. Marsaglia and W.W. Tsang (2000) "The Ziggurat Method for Generating
% Random Variables", Journal of Statistical Software, 5(8). Available on-line
% at http://www.jstatsoft.org/v05/i08/.
%
% [3] G. Marsaglia and W.W. Tsang (1984) "A Fast, Easily Implemented Method
% for Sampling from Decreasing or Symmetric Unimodal Density Functions",
% SIAM Journal of Scientific and Statistical Computing, 5(2):349-359.
%
% [4] Knuth,D.E. (1998) Seminumerical Algorithms, volume 2 of The Art of
% Computer Programming, 3rd ed., Addison-Wesley.


--------------------
Пишите в личку.
Go to the top of the page
 
+Quote Post
Макс_Мат
сообщение Apr 5 2007, 16:19
Сообщение #37


Частый гость
**

Группа: Свой
Сообщений: 76
Регистрация: 21-03-07
Пользователь №: 26 378



спасибо, посмотрим на досуге...
Go to the top of the page
 
+Quote Post
Pathfinder
сообщение Apr 7 2007, 23:12
Сообщение #38


Местный
***

Группа: Свой
Сообщений: 275
Регистрация: 29-06-05
Пользователь №: 6 400



Макс_Мат, вы так и не ответили, каким образом предлагаемые вами методы реализуются за 4 такта на блекфине


--------------------
ADC / DAC LC Filter Designer — Удобный инструмент проектирования LC-фильтров для ЦАП и АЦП
Go to the top of the page
 
+Quote Post
Макс_Мат
сообщение Apr 9 2007, 10:09
Сообщение #39


Частый гость
**

Группа: Свой
Сообщений: 76
Регистрация: 21-03-07
Пользователь №: 26 378



А нужно ли это лично Вам? Если Вы до сих пор не видите как и не хотите учиться, то может Вам вообще покинуть сферу деятельности, связанную с электроникой и, в частности, с сигнальными процессорами?

ps обучают программированию на специальных курсах или в соседних разделах на форуме...
Go to the top of the page
 
+Quote Post
Pathfinder
сообщение Apr 9 2007, 12:12
Сообщение #40


Местный
***

Группа: Свой
Сообщений: 275
Регистрация: 29-06-05
Пользователь №: 6 400



Хмм, ничего другого и не ожидал - нечем ответить по всей видимости...
Или осознание собственного величия не позволяет снисходить до простых смертных...


--------------------
ADC / DAC LC Filter Designer — Удобный инструмент проектирования LC-фильтров для ЦАП и АЦП
Go to the top of the page
 
+Quote Post
Макс_Мат
сообщение Apr 9 2007, 12:59
Сообщение #41


Частый гость
**

Группа: Свой
Сообщений: 76
Регистрация: 21-03-07
Пользователь №: 26 378



я одно время работал с очень талантливым человеком. И вот, частенько, он любил повторять, когда мы принимали на работу очередного студента: "если человек к 18 годам не стал профессиональным инженером, то он им не станет никогда".

Сообщение отредактировал Макс_Мат - Apr 9 2007, 12:59
Go to the top of the page
 
+Quote Post
makc
сообщение Apr 9 2007, 14:19
Сообщение #42


Гуру
******

Группа: Админы
Сообщений: 3 621
Регистрация: 18-10-04
Из: Москва
Пользователь №: 904



Уважаемые участники, для bb-offtopic.gif есть отдельный раздел. Не отходите от темы!


--------------------
BR, Makc
В недуге рождены, вскормлены тленом, подлежим распаду. (с) У.Фолкнер.
Go to the top of the page
 
+Quote Post
CD_Eater
сообщение May 1 2007, 22:50
Сообщение #43


Частый гость
**

Группа: Новичок
Сообщений: 173
Регистрация: 3-09-04
Из: Moscow
Пользователь №: 595



Для автора, думаю, через полгода запоздалый ответ вряд ли будет полезен, но "для копилки" хочу привести ещё один генератор ПСП, до безобразия простой, легко настраиваемый на любую длину чисел и на любую длину неповторяющегося куска.

X_next = 5*(1 + X_prev)
Вычисления производятся по модулю 2 в степени k (k - любое целое число от 3 до бесконечности).
Этот генератор обладает ПОЛНЫМ периодом (то есть, цикл проходит через все k-битные числа, прежде чем возникнет повтор).
А главное - простота реализации на любом МК. Это проще, чем вычислять регистр с линейной обратной связью, особенно если в МК есть умножение.

Примеры:
Чтобы получить посл-сть 9-битных чисел с периодом 512, применяем вышенаписанную формулу при k=9
Чтобы получить посл-сть 9-битных чисел с периодом 2^24, то применяем вышенаписанную формулу при k=24 и берём СТАРШИЕ 9 бит от получающихся чисел.

Если кто-то усмотрит в этом генераторе некую автокорреляцию, ухудшающую свойства случайности, то есть такой выход (при наличии в МК быстрого умножения)
X_next = A * X_prev + B
где коэффициенты A и B - любые целые числа, такие что A даёт остаток 1 при делении на 4, а B - любое нечётное. Эти требования на A и B гарантируют полноту периода, то есть, все k-битные числа будут собраны в один цикл (при любом k).
Автокорреляция, имхо, может быть улучшена, если взять большие числа A и B (вариант A=B=5 в этом плане хуже, но зато он предпочтительнее для тех, кому придётся умножать сдвигами и сложениями)

Конечно, для криптографических целей этот генератор не подходит.
Go to the top of the page
 
+Quote Post

3 страниц V   1 2 3 >
Reply to this topicStart new topic
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 


RSS Текстовая версия Сейчас: 25th July 2025 - 05:49
Рейтинг@Mail.ru


Страница сгенерированна за 0.01847 секунд с 7
ELECTRONIX ©2004-2016