Немного о себе

[Dig386]

Английский ловил просто интуитивно, когда надо было часто читать хелпы.

Занимался подобным в начальной школе, т.к. тогда многие программы были ещё не русифицированы, особенно среды разработки. А класса с 5 уже систематически начал язык учить, и шёл довольно тяжело, в первую очередь - восприятие речи на слух. В итоге научился писать документацию, статьи, письма, и перешёл к документированию своих же исходников на английском. Могу говорить и даже пробовал последовательным переводом заниматься. Но фильмы и беглую речь на слух воспринимаю всё ещё далеко не всегда.

Просто перебирал значения для параметров (не все, а так чтобы хорошо оптимизировались), и замерял получившийся период. Там особо большой период и не нужен, 2^24-1 достаточно.

Для шума период наверняка достаточен, хотя кто знает, может, и есть уникумы, которое такое отличат от AES на слух. "Хорошо оптимизировались" - это чтобы значения сдвигов и поворотов были поменьше, насколько я знаю, у некоторых процессоров эти команды двигают только на 1 бит? Подход "в лоб" я точно использовал для xorshift16, xorshift32, функции Климова-Шамира, но уже для xorshift64 методика оказалась неприменима. И пришлось городить огород с матрицами перехода.

Серьёзных тестов на случайность не делал.

Серьёзные тесты генератор с периодом 2^24 - 1 и не пройдёт, т.к. период крошечный для "тяжелых" вычислений. Впрочем, я склоняюсь к мысли, что реально серьёзные тесты - это уже скорее криптоанализ.

[SergM]

Я не уверен, что тоже самое имею ввиду. У меня конкретно с хором такого не было, но было с инструментом музыкальным. Я очень плохо на слух различаю ноты. Если на сольфеджио все сидели как то писали их, я вообще ничего не понимал. Видимо это так проявляется то же отсутствие интуитивного восприятия. То есть научится было можно, но для этого нужно было бы составлять свою азбуку поверх нот. Думаю у вас с хором была та же проблема

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

[SergM]

"Хорошо оптимизировались" - это чтобы значения сдвигов и поворотов были поменьше, насколько я знаю, у некоторых процессоров эти команды двигают только на 1 бит?

Да, сдвиги только на 1 бит. Сдвиги на 8 или 16 бит можно заменить пересылками. Да и вообще, чтобы поменьше операций. Время ограничено.

Один аутичный автор попытался это сделать, и получилось весьма интересно, прямо научно-популярное описание модели психического: https://www.aspergers.ru/node/139

Занятно. Когда мне на работе что-то объясняли, очень часто хотелось сказать (и говорил): да скажите же прямо, чего вы на самом деле хотите? А то всё вокруг да около. А те не понимают. Даже такой алгоритм сложился по решению задач от начальства: выслушать их, и постараться понять, чего они на самом деле хотят. Не нарисовать такую-то форму, а какую информацию они вообще хотят увидеть? А потом просто делать по своему разумению, может быть и совсем не так, как они это рисовали. Как оказалось - самый результативный. А если тупо делать как говорят - потом по нескольку раз приходилось переделывать.

[Владимир]

У мамы истерика, а мне — хоть бы что. Только всё стихло — спокойно пошёл проверять: целы ли окна. Как будто ничего не произошло. Не знаю как это называется.

Я называю такое нарушенным чувством самосохранения. Меня часто воспринимали храбрым, потому что не выказывал страха в опасных обстоятельствах. Со временем понял, что не то чтобы не боюсь. Именно, не чувствую опасности.

[SergM]

Я называю такое нарушенным чувством самосохранения. Меня часто воспринимали храбрым, потому что не выказывал страха в опасных обстоятельствах. Со временем понял, что не то чтобы не боюсь. Именно, не чувствую опасности.

Да нет, проблема шире. Других сигналов тоже нет, и я могу даже не догадываться, что они должны быть.
В последнее время мне кажется, что не чувствую усталости (возможно, и раньше так было, просто сил было больше). Нет никакого сигнала, что "хватит, пора отдыхать". Перегрузок не замечаю. В итоге: день хорошо поработал - на следующий день лежу пластом с больной головой.
Часто могу не чувствовать голода, замечаю только головокружение и нарастающую слабость (это ещё в детстве было) - это хотя бы режимом можно исправить.
Или ещё пример: когда надо впервые выступить перед людьми - естественно волноваться. Чувствую себя спокойным как столб, а голос дрожит. Пытаюсь с этим справиться - всё равно что-то не то выходит. Говорят "будь увереннее", а я вроде бы уже уверен дальше некуда.

[Dig386]

Когда мне на работе что-то объясняли, очень часто хотелось сказать (и говорил): да скажите же прямо, чего вы на самом деле хотите? А то всё вокруг да около. А те не понимают.

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

А потом просто делать по своему разумению, может быть и совсем не так, как они это рисовали.

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

Или ещё пример: когда надо впервые выступить перед людьми - естественно волноваться. Чувствую себя спокойным как столб, а голос дрожит.

Лет 20-25 назад я мог сильно волноваться перед публичными выступлениями, сейчас волнение почти ушло из-за регулярного преподавания. Отчасти помогал подход "голос дрожит или запинки пошли? Ничего, подрожит и перестанет, разгонишься потихоньку".

Да, сдвиги только на 1 бит. Сдвиги на 8 или 16 бит можно заменить пересылками.

Попробовал забавы ради поэкспериментировать, получилась конструкция, похожая на xorshift96, со сдвигами только на 1 бит с максимальным периодом 2^24 - 1. Не знаю, насколько она на самом деле быстрая для 8-битных процессоров. Сложение в конце пришлось добавить, т.к. без него генератор даже одномерный 32-битный birthday spacings проваливал. Если рисовать точки на плоскости генератором, то ложатся они хаотично. На x86-64 этот алгоритм использовать бессмысленно, т.к. он медленнее AES и ChaCha.

спойлер

Код: Выделить всё

#include <stdint.h>
#include <stdio.h>

static inline uint8_t rotl8(uint8_t x, int r)
{
    return (uint8_t) ( (x << r) | (x >> ((-r) & 7)) );
}

typedef struct {
    uint8_t x;
    uint8_t y;
    uint8_t z;
} Gen24State;

static inline uint8_t get_byte(Gen24State *obj)
{
    const uint8_t x0 = obj->x, z0 = obj->z;
    obj->x = x0 ^ obj->y;
    obj->y = x0 ^ z0;
    obj->z = (x0 << 1) ^ obj->y ^ rotl8(z0, 1) ^ rotl8(z0, 7);
    return x0 + z0;
}

static inline double get_double(Gen24State *obj)
{
    uint32_t out = get_byte(obj);
    out |= (uint32_t)get_byte(obj) << 8;
    out |= (uint32_t)get_byte(obj) << 16;
    out |= (uint32_t)get_byte(obj) << 24;
    return out / 4294967296.0;
}

int main()
{
    Gen24State obj = {1, 2, 3};
    for (long i = 0; i < (1L << 24) - 1; i++) {
        (void) get_byte(&obj);
    }    
    printf("%d %d %d\n", (int) obj.x, (int) obj.y, (int) obj.z);
    for (long i = 0; i < (1L << 16) - 1; i++) {
        const double x = get_double(&obj), y = get_double(&obj);
        printf("%.8f,%.8f\n", x, y);
    }
    return 0;
}

[SergM]

Попробовал забавы ради поэкспериментировать, получилась конструкция, похожая на xorshift96, со сдвигами только на 1 бит с максимальным периодом 2^24 - 1. Не знаю, насколько она на самом деле быстрая для 8-битных процессоров.

Попробовал. На слух разница с моим почти незаметна, вслепую, наверное, не отличил бы. Спектр вроде бы чуть получше. Аппаратный rdrand32, впрочем даёт спектр ещё немного лучше, но на слух тоже незаметно.

Сходу прикинул для 8-битного: 16 тактов и 6 регистров, но может быть, можно ещё оптимизировать.
Мой вариант требует 16 тактов и 5 регистров:

спойлер

Код: Выделить всё

static unsigned seed = 0xFFFFFF;
static unsigned rand1(unsigned *seed)
{
    unsigned s = *seed;
    unsigned b1 = (s >> 16) & 0xFF;
    s = (s << 8) ^ b1;
    s ^= b1 << 1;
    s ^= b1 << 8;
    s ^= b1 << 11;
    *seed = s;
    return s;
}

Вот только я с результата сразу снимаю 16 бит за одну итерацию, а сдвигаю только на 8. Наверное, это не очень хорошо. Вместо чисел 1, 8, 11 пробовал также 1, 3, 16 - разницы особой не заметил.

[Dig386]

Вот только я с результата сразу снимаю 16 бит за одну итерацию, а сдвигаю только на 8. Наверное, это не очень хорошо.

Какие 16 бит, нижние? И unsigned - это на Вашей платформе 32-разрядное беззнаковое целое? Если да, то период у него действительно 2^24 - 1, а вот birthday spacings и побайтовый частотный тест он хуже проходит. Особенно второй набор сдвигов. По идее если ставить цель получить побольше бит за одну итерацию, то имеет смысл посмотреть в сторону xorshift24 или xorshift32 с удачными сдвигами (и задействовать флаг переноса при организации сдвигов всего состояния). Есть ещё Multiply With Carry, если удачно подобрать множитель и скремблер, то он тоже может быть быстрым, хотя и период у него меньше при том же размере состояния.

Аппаратный rdrand32

Имеется в виду на микроконтроллере или на x86-64? Насколько я знаю, он действительно хороший, но медленный, и на некоторых старых процессорах он мог сбоить. Если мне нужны хорошие сиды, то я поступаю проще - обращаюсь к системному криптогенератору вроде /dev/urandom, а если быстрый и очень качественный ГПСЧ - то беру поточный шифр.

[SergM]

Какие 16 бит, нижние?

Да, нижние.

И unsigned - это на Вашей платформе 32-разрядное беззнаковое целое?

Этот код использовался для теста алгоритма на x86. Да, unsigned - 32-разрядное беззнаковое целое, старшие 8 бит не используются. На реальном микроконтроллере он кодировался на ассемблере, там seed был в трех 8-битных регистрах.

По идее если ставить цель получить побольше бит за одну итерацию, то имеет смысл посмотреть в сторону xorshift24 или xorshift32

Пробовал какой-то xorshift (уже не помню), спектр совсем не понравился, и на слух заметно, что шум не белый.

Это уже микрооптимизации. Всего на итерацию - 256 тактов, из них львиную долю занимает цифровой фильтр. 16 тактов на ГПСЧ - это неплохо. Да и вообще, делать такое на 8-разрядном AVR без умножений - это в некоторой степени экстрим. Почти за те же деньги можно взять 32-разрядный STM или ESP32. А ещё проще - китайский MP3-проигрыватель. Но это неинтересно.

Имеется в виду на микроконтроллере или на x86-64?

На x86-64. Да, медленный, у меня на ноутбуке выдаёт около 1,1M чисел (32-битных) в секунду. Просто брал для сравнения, чтобы никаких сомнений не было.

[Dig386]

Пробовал какой-то xorshift (уже не помню), спектр совсем не понравился, и на слух заметно, что шум не белый.

Разные наборы сдвигов для xorshift могут сильно различаться по качеству генерации даже при максимальном периоде, обычно у xorshift64 и особенно xorshift32 хватает грубых артефактов (впрочем, у мини-генераторов из этой темы их тоже полно). И ещё в xorshift32 из исходников KISS99 была опечатка в константах, приводящая для части сидов к коротким циклам.

Кстати, а не возникает ли из-за короткого периода 2^24-1 ощущения, что генератор белого шума повторяет словно зацикленный фрагмент записи?

. Почти за те же деньги можно взять 32-разрядный STM или ESP32.

Насколько я помню, на части из них уже могут быть специализированные инструкции для реализации AES? Просто если эти инструкции там есть и они достаточно быстрые, то это полностью решает вопрос с качеством ГПСЧ.

Да, медленный, у меня на ноутбуке выдаёт около 1,1M чисел (32-битных) в секунду.

Скорость выполнения этих инструкций очень сильно варьируется от процессору к процессору. И на одном ядре x86-64 аппаратно ускоренные AES128 или ChaCha8 выдают гигабайты в секунду. Пользуюсь ими в том случае, кода мне нужно методом Монте-Карло вывести эмпирическую функцию распределения для статистических тестов.