Два слова из трёх букв (обсуждение)

[ysv_]

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]

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

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

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

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

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

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

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

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

Запускаем программу - и совершаем мышедвижения.

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

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

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

P.S. Программист обращается к коллеге:
- Вася, у тебя нет случаем генератора случайных чисел?
Вася, не отрываясь от листинга:
- 17!

[Alf]

Смысл вычисления 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]

Автор привёл пример контрольной суммы, но не показал необходимость вычисления суммы.  Как показано в статье, из которой взят метод вычисления контрольной суммы, если контрольную сумму приписать в конец сообщения (массива байт), то для такого удлиннённого сообщения контрольная сумма будет равна 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

[Алексей++]

Раздолбали в хлам!!!      

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

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

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

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

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


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

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

 убито другим

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

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

это же и тут:

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

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


 :arrow:

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

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