?

Log in

No account? Create an account

Задачка по теорверу - Общество дровосеков Бердичева по изучению Мишны

Aug. 2nd, 2017

12:38 pm - Задачка по теорверу

Previous Entry Share Next Entry

Пункт 1, предварительный:
Что напечатает эта программа:

#include <stdio.h>
#include <stdlib.h>
void foo(int i) {
    int j;
    srand48(i);
    while ((j = drand48() * 22)) {
        putchar(j+64);
    }
    putchar('\n');
}

int main() {
    foo(17594951);
    foo(56010574);
    foo(84979338); /* try 16447603 instead */
    return 0;
}


Пункт 2: Насколько сильно нам повезло? (Придумайте способ выразить везение численно.)

This entry was originally posted at http://spamsink.dreamwidth.org/1056952.html. Please comment there using OpenID.

Comments:

[User Picture]
From:fatoff
Date:August 2nd, 2017 08:45 pm (UTC)
(Link)
Посолили srand48, известно чем.

The initializer function srand48() sets the high order 32-bits of Xi to the argument seedval. The low order 16-bits are set to the arbitrary value 0x330E.

Пытаюсь довычислить.
(Reply) (Thread)
From:pigdeon
Date:August 2nd, 2017 08:58 pm (UTC)
(Link)
Куда более интересно движение мысли, приведшее к самой идее искать словарные текстовые строки в выходных последовательностях рандомизатора.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:August 2nd, 2017 09:30 pm (UTC)

Музыкой навеяло

(Link)
http://www.tpug.ca/tpug-media/nl/91-Fall2015.pdf стр. 7

Они там в Канаде совсем необученные математике сидят?
(Reply) (Parent) (Thread)
[User Picture]
From:yigal_c
Date:August 2nd, 2017 09:16 pm (UTC)
(Link)
Забавно.

Но вот если б оно главу Торы выдало...

Казалось бы, среди 4G сидов найдутся такие, что дадут последовательность из 5-6 нужных букв практически со стопроцентной вероятностью.

Или же я чего-то не понимаю?...
(Reply) (Thread)
[User Picture]
From:spamsink
Date:August 2nd, 2017 09:31 pm (UTC)
(Link)
Найдутся, конечно. Вопрос, насколько быстро по сравнению с ожидаемым.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:August 2nd, 2017 10:00 pm (UTC)
(Link)
Там важную роль играет округление до целых чисел. И не случайно умножается на 22, а не на 26, чтобы подогнать диапазоны округления.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:August 2nd, 2017 11:45 pm (UTC)
(Link)
Округление до целых чисел играет роль, но довольно неважную. С тем же успехом можно было бы рассматривать мантиссу как длинное целое, и брать остаток от деления на 22.
Получились бы другие значения сидов, но всё равно рано или поздно нашлись бы.

Умножается на 22, а не на 26, потому что самая дальняя в алфавите буква, которая нам нужна - U. Это улучшает шансы нахождения желаемого сида.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:August 3rd, 2017 08:57 pm (UTC)
(Link)
> Округление до целых чисел играет роль, но довольно неважную.

Я так понимаю, что фокус в том, что конкретное число сгенерированное генератором неважно, важно чтоб оно попало в диапазон, который округляется до того же числа.
(Reply) (Parent) (Thread)
From:ext_1745607
Date:August 2nd, 2017 09:26 pm (UTC)
(Link)
В воздухе отчетливо запахло пуассоном...
(Reply) (Thread)
[User Picture]
From:spamsink
Date:August 2nd, 2017 09:31 pm (UTC)
(Link)
:) Isn't that fishy? (Sorry, coudln't resist.)
(Reply) (Parent) (Thread)
From:ext_1745607
Date:August 2nd, 2017 09:55 pm (UTC)
(Link)
;) дык. Как только подобные задачи всплывают, так сразу..

Навскидку нам вроде не повезло ни разу, то есть таких сидов можно найти еще больше десятка -- для каждого слова.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:August 2nd, 2017 11:52 pm (UTC)
(Link)
Под "повезло" я имею в виду, "повезло найти перебором относительно быстро по сравнению с ожидаемой длительностью перебора".

Если бы найденные сиды были все в пределах первой сотни или тысячи, это значило бы, что или нам очень сильно повезло, или что в алгоритм действительно заложено пасхальное яйцо, как наивно предполагал автор статьи по ссылке http://www.tpug.ca/tpug-media/nl/91-Fall2015.pdf
(Reply) (Parent) (Thread)
From:ext_1745607
Date:August 3rd, 2017 12:17 pm (UTC)
(Link)
а, теперь понял. Ну я думаю даже в те времена перебрать 100М сидов не было большой проблемой. Ну не пол-секунды как сейчас, а несколько минут. no big deal.
Интересно становится все это для шестибуквенных слов.
(Reply) (Parent) (Thread)
From:ext_1745607
Date:August 3rd, 2017 04:31 pm (UTC)
(Link)
Не совсем ответ на вопрос насколько вероятно найти нужные слова и ТАКИЕ СИДЫ для них без нечестных трюков, но хватит для оценки:
вероятность того, что сиды для искомых 5-буквенных слов будут лежать в диапазоне
< 60000000 (как для GATES) около 40%, то есть ничего необычного.
Значит не easter egg с достаточно хорошей уверенностью, хотя точно p-value оценить не берусь.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:August 3rd, 2017 06:14 pm (UTC)
(Link)
Что в случае GNU LIBC это не easter egg, можно быть достаточно уверенным, а по ссылке числа гораздо меньше: 125708, 33435700 и 17059266. :)
(Reply) (Parent) (Thread)
From:ext_1745607
Date:August 3rd, 2017 07:45 pm (UTC)
(Link)
Тут надо задуматься над тем что такое фэйк в терминах статистики,
то есть что есть наша H1-гипотеза.
Такие 32-битные сиды с большой вероятностью существуют -- тут фэйк не нужен.
Может фэйк в том, что наши числа восьмизначные? Ну тогда тоже нет разницы между libc и коммодором. Или фэйк в том, что максимальное число всего 33435700?
Тут я чисто по-человечески не вижу смысла такой фэйк делать ;)
(Reply) (Parent) (Thread)
[User Picture]
From:janatem
Date:August 3rd, 2017 11:45 am (UTC)
(Link)
Конечно, дело не в везении. Если реализация псевдослучайности достаточно хорошая, то можно ожидать НЕ найти нужное 5-буквенное слово среди первых 10^8 сидов с вероятностью всего 3E-9 (точнее, 1-(1.-22**(-5))**1E8).
(Reply) (Thread)
From:ext_1745607
Date:August 3rd, 2017 12:19 pm (UTC)
(Link)
а точно? Ведь для пятибуквенного слова нужна последовательность из шести чисел.
(Reply) (Parent) (Thread)
[User Picture]
From:janatem
Date:August 3rd, 2017 12:51 pm (UTC)
(Link)
Да, точно, был неправ. Тогда придется перебрать 10^9 сидов, чтобы получить хорошую вероятность успеха:

1-(1.-22**(-6))**1e9 = 0.99985

Поскольку в примере сиды значительно меньше 10^9, то изрядно повело. Хотя если там нужно не априори заданное слово, а любое из словаря, то шансы опять хороши.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:August 3rd, 2017 06:20 pm (UTC)
(Link)
Для оценки "везения" логично смотреть, когда вероятность станет равна 50%. Мы же не говорим, что нам изрядно повезло, если при бросании монеты удалось выбросить желаемую сторону менее чем за log(1-0.99985)/log(0.5) = ~13 раз.

(Reply) (Parent) (Thread)
[User Picture]
From:janatem
Date:August 3rd, 2017 12:16 pm (UTC)
(Link)
Предлагаю такой пример:
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <math.h>

#define ACCURACY (1E-12)
void foo(double *);

int main(int argc, const char **argv) {
  srandom(argc > 1 ? atoi(argv[1]) : 12345);
  
  double x = 10;
  uint64_t cnt = 0;
  while(fabs(x) > ACCURACY) {
    foo(&x);
    ++cnt;
  }
  printf("cnt: %lu\n", cnt);
}

Как подсказывает интуиция в отношении того, какое примерно число будет напечатано? Конечно, всё зависит от того, что именно делает foo(). В реальном случае из-за ошибки программиста foo() портила память в окрестности указателя, и там оказывался мусор. Но мы для чистоты эксперимента портить будем равномерно:
void foo(double *x) {
  uint32_t *y = (uint32_t *)x;
  /* assume RAND_MAX >= 2^32) */
  y[0] = random();
  y[1] = random();
}

(Reply) (Thread)
[User Picture]
From:spamsink
Date:August 3rd, 2017 07:31 pm (UTC)
(Link)
Очень маленькое. Грубо, для достижения 1Е-12 (~ 2^-40) нужно, чтобы старшие 12 бит 32-битного целого были не более 2048-40. Но старший бит и так всегда 0, потому что RAND_MAX = 2^31-1, так что ответ будет 1, от силы 2.
(Reply) (Parent) (Thread)
[User Picture]
From:janatem
Date:August 3rd, 2017 08:29 pm (UTC)
(Link)
Хм, я ошибся. Я думал, что RAND_MAX больше, так что перемешиваются все биты (еще удивлялся, почему ответ такой маленький). Нужно переписать foo(), так чтобы рандомизировались все 64 бита. И ACCURACY поставить поменьше, например 1E-6.

Изначально цель демонстрации была в том, что в IEEE-754 доля близких к нулю чисел контринтуитивно велика.
(Reply) (Parent) (Thread)