Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Два слова из трёх букв (обсуждение)  (Прочитано 9113 раз)
0 Пользователей и 1 Гость смотрят эту тему.
ysv_
Помогающий

ua
Offline Offline

« : 24-05-2004 08:34 » 

Цитата
RND - это псевдослучайное число (от "Random" - случайный). В языке Бейсик и многих других языках более высокого уровня, чем C++, есть функция RND(n), которая генерит псевдослучайное число в диапазоне 0<X<1. В C++ я такой функции не заметил, но возможно это и к лучшему.

В С/С++ тоже есть набор функций для генерации псевдослучайных чисел:
int rand(void) - генерирует псевдослучайную последовательность с периодом 2^32 в пределах от 0 до RAND_MAX (для Borland C++ это - 32767).
int random(int num) - тоже что и выше только верхняя граница не больше max(num, RAND_MAX).
void randomize(void) - инициализирует генератор псевдослучайных чисел, используя текущее значение времени (для DOS/Windows - исользуется время в милисекундах).
void srand(unsigned seed) - начальное значение генератора псевдослучайных чисел.

Способ генерации псевдослучайных чисел - предложенный автором имеет существенный недостаток - таким образом много чисел не сгенерируеш. А для нескольких чисел - вполне хватит стандартного набора функций: используя randomize() и вызовы rand().

В Borland C++ используется например следующий код для генерации псевдослучайных чисел:
#define MULTIPLIER      0x015a4e35L
Seed = MULTIPLIER * Seed + 1;
return((int)(Seed >> 16) & 0x7fff);
Записан
Alf
Гость
« Ответ #1 : 24-05-2004 10:06 » 

Цитата
Вас не смущает приставка "псевдо"? " Да, ненастоящее" случайное число! Так когда-то и было - по крайней мере в программируемых калькуляторах и том же Бейсике. Делалось это так - составлялась таблица из истинно случайных чисел - и навсегда зашивалась в ПЗУ (в МК) или файл (в ПК). Далее - далеко не случайно - из этой таблицы брались числа, обычно просто по очереди, сдвигая некий указатель на единицу после каждого запроса RND программой.

Автору действительно попадались подобные реализации генераторов случайных чисел?

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

Что касается идеи с записью таблицы в ПЗУ, мне она тоже кажется сомнительной. Например, интерпретаторы Basic и Focal для ДВК-1, в которых имелась функция RND, поставлялись в ПЗУ емкостью 8 Кб, а там особо не разгуляешься, если даже целиком отвести весь объем под таблицу. Объем ПЗУ Sinclair Spectrum ZX малость побольше, 16 Кб, но и там подобной таблицы нет (уж за это я ручаюсь, поскольку в свое время дизассемблировал его до последнего байта).

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

Для того, чтобы цепочка не начиналась каждый раз с одного и того же места, для инициализации цепочки была добавлена функция RANDOMIZE, в качестве аргумента которой обычно использовали значение, производное от системного времени.

Цитата
Можно сделать вовсе извращенскими методами- например улавливанием из воздуха электрических помех с помощью специально разработанного устройства, подключемого к USB порту и распространяемое вместе с программой, батарейки и гарантия 1 месяц прилагается, пломбы не срывать.

А где гарантия, что этой самой "электрической помехой из воздуха" не станут 50 Гц от ближайшего силового кабеля? Тут ведь настоящий белый шум нужен, а его генератор - не столь простое устройство.
Цитата
Запускаем программу - и совершаем мышедвижения.

А как быть, если не хочется двигать мышь? Например, неинтерактивная программа моделирования чего-нибудь, получающая на вход "случайную" последовательность. Нанимать кого-то для прогуливания мыши по коврику на все время процесса?

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

Мне кажется, приведено не самое лучшее решение проблемы из возможных.

P.S. Программист обращается к коллеге:
- Вася, у тебя нет случаем генератора случайных чисел?
Вася, не отрываясь от листинга:
- 17!
Записан
Alf
Гость
« Ответ #2 : 24-05-2004 11:36 » 

Цитата
Смысл вычисления CRC заключается в следующем. Выбирается какой-нибудь полином (для простоты - шестнадцатибитное число, константа) P16. Это будет полиномом контрольной суммы - с помощью него будет считаться и проверяться контрольная сумма.

Вообще-то, насколько мне помнится, полином - это многочлен, обычно представляемый в виде
Код:
A0 + A1*x^1 + A2*x^2 + ... + An*x^n

Полином в виде константы, на мой взгляд, нонсенс. Может быть, речь идет все же о битовой строке, представляющей собой коэффициенты полинома?
Цитата
Теоретически, полученная таким образом CRC однозначно характеризует последовательность битов в исходном сообщении, и поменяйся хоть один бит - его CRC с тем же полиномом - поменяется. Но это теоретически, а доказано или нет - не знаю. Хотя вполне вероятно.

Не доказано это, и не может быть доказано.

В статье приводится в качестве примера 16-битный CRC. А ни для кого не секрет,что 16-разрядным двоичным числом можно представить 2^16=65536 различных значений. Так что никоим образом нельзя говорить, что "полученная таким образом CRC однозначно характеризует последовательность битов в исходном сообщении". А если бы это было так, нам вовсе незачем было бы передавать сами сообщения. Достаточно передать только CRC, а получатель, пользуясь однозначным соответствием, мог бы восстановить исходное сообщение. Настоящая революция в области передачи данных.

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

И даже в этом случае можно говорить только о вероятности повреждения. Так, изменение 1 бита информации однозначно изменит CRC. 2 или 3 бита - тоже. Я не вдавался в эту теорию, но интуитивно подозреваю, что, изменяя 16 бит исходного сообщения, можно добиться того же значения CRC.

Таким образом, использование CRC может лишь говорить о том, что содержимое сообщения не изменилось случайно с высокой степенью вероятности. О том, что он однозначно определяет сообщение, не может быть и речи.
Записан
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #3 : 24-05-2004 12:14 » 

Автор привёл пример контрольной суммы, но не показал необходимость вычисления суммы.  Как показано в статье, из которой взят метод вычисления контрольной суммы, если контрольную сумму приписать в конец сообщения (массива байт), то для такого удлиннённого сообщения контрольная сумма будет равна 0.

Код:
   BYTE bufer[(=|0,1,2,3,4,5,6,7,8, 0, 0";
    WORD crc=MakeCRC16)bufer,9:;
    //crc==0x46a0
    bufer[9( = )BYTE:)crc >> 8:;
    bufer[10( = )BYTE:)crc & 0xff:;
   
    crc=MakeCRC16)bufer,11:;
    // crc == 0


тем самым обеспечивается частичная защита данных от случайных изменений при передаче.  В смысле, не защита обеспечивается, а появляется возможность измение данных обнаружить.
Ещё одно замечание.  В статье указана ссылка на использовавшуюся работу.  Ссылка достаточно подробна, google нашёл с первой попытки.  Тем не менее, стоит более чётко оформлять ссылки.  Например, в конце статьи сделать раздел "Список литературы" и указать ссылку:
[1] Thomas Schmidt, "CRC Generating and Checking", Microchip Technology Inc., AN730. http://ww1.microchip.com/downloads/en/AppNotes/00730a.pdf
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #4 : 24-05-2004 13:18 » 

Раздолбали в хлам!!!  Отлично  Отлично  Отлично

Цитата

Автору действительно попадались подобные реализации генераторов случайных чисел?


насчёт таблиц - да, в МК-56 и в интерпретаторе Бейсика на Orion128

про формулы - насчёт реализаций не знаю, но про попытки такие встречал где-то в литературе

Цитата

Полином в виде константы, на мой взгляд, нонсенс. Может быть, речь идет все же о битовой строке, представляющей собой коэффициенты полинома?


наверное это и имеется в виду  Ага
Но - именно битовая строка


а вот это правильное (абсолютно согласен) замечание
Цитата

В статье приводится в качестве примера 16-битный CRC. А ни для кого не секрет,что 16-разрядным двоичным числом можно представить 2^16=65536 различных значений. Так что никоим образом нельзя говорить, что "полученная таким образом CRC однозначно характеризует последовательность битов в исходном сообщении

 убито другим

Цитата

Не доказано это, и не может быть доказано.


 Улыбаюсь  думаю оправдываться мне не имеет смысла - тем более что ничего я не смогу возразить

это же и тут:
Цитата

В смысле, не защита обеспечивается, а появляется возможность измение данных обнаружить.


пусть и не всегда это обнаруживается


 :arrow:
Цитата

Тем не менее, стоит более чётко оформлять ссылки.


виноват, исправлюсь  :oops:
Записан

Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines