Pull to refresh

Comments 95

The Top Ten Algorithms of the Century
5. the Fortran compiler, developed by a team lead by John Backus;
Вот, да, кстати.
Буду признателен, если кто-нибудь расскажет, что в этом компиляторе такого особенного.
Может это потому, что это был первый компилятор, в котором использовался анализатор на основе BNF, насколько я понимаю?
Спасибо. Заодно узнал, что такое BNF.
Вполне заслуженно в топе находится.
Для своего времени компилятор был революционным. Как с точки зрения внутреннего устройства, так и с точки зрения пользователя. Насколько я помню, это был первый компилятор с «нормальными» сообщениям об ошибках в виде сообщения, а не номера, который нужно искать в мануале.
Это первый компилятор языка высокого уровня. До этого были только ассемблеры.
А этот алгоритм на другие иррациональные числа перекладывается?
К примеру, в статье, ссылку на которую я приводил в конце топика, Бэйли начинает с вычисления n-го знака натурального логарифма двойки.
Других упоминаний о подобном пока не встречал.
Да, если для них существует столь же удобная формула
Отличное практическое применение вышеупомянутого алгоритма: πfs! Давно перенес на нее всю свою коллекцию фильмов.
Чёрт, мы пару дней назад взялись за реализацию подобного.
А оказывается, всё уже придумали до нас!
Практического применения этому, конечно, никакого, но весело!

Если мы всё же доделаем свой вариант, имеет смысл статью об этом писать? Интересно будет? Или не очень?
Пишите, конечно. Интересно будет почитать.
В связи с ухудшающейся общемировой ситуацией, связанной с копирайтами и последствиями его нарушения, предлагаю simple yet brilliant идею — Offline Torrents Downloader!

Суть очень проста — для скачивания каждого блока достаточно просто найти последовательность в π с требуемым хэшем! Доступ к интернету? Зачем, ведь есть Offline Torrents Downloader — и пусть копираст докажет, что ты что-то откуда-то скачал!
Собственно, это мы и реализовываем.
Coming soon, в общем :)
Когда я последний раз изучал вопрос, скорость этой ФС еще не позволяла записывать туда фильмы. Это тонкий сарказм, или неожиданный прорыв в скорости поиска чанков?
UFO just landed and posted this here
Это почему же на порядки больше? В среднем, того же объёма. Иногда больше, иногда меньше.
UFO just landed and posted this here
Согласен с вами до фразы «Почему-то я уверен». Это заблуждение сродни тому, что вероятность выигрыша лотерейного билета номер 123456 ниже, чем 593742.
Для иллюстрации попробуйте поискать в числе Пи, например, ABC и 7F3. Да и любые данные, которые выглядят более-менее осмысленными и сравните со «случайными».
Действительно, редкой красоты формула. Вспомнилась, кстати сразу античная (!) 22/7
Да, красивая дробь, Архимедова. Только точность низкая.
Во времена Архимеда ещё не придумали арифметику с плавающей точкой. Так и жили, аппроксимированным делением интеджеров на интеджеры.
… а равно как и в былые славные времена Z80, да и сейчас, во времена нынешних AVR со товарищи. Fixed-point рулит! Со времен античности.
Почему то вспомнился Integer Basic на ранних Apple I/II, который благодаря античным «интеджерам» накручивал популярность.
А мне всегда намого больше нравилась 355/113. Чуть сложнее, а точность зато на 4 порядка больше.
Напомнило про визуализацию разрядов числа пи.
image
Взято отсюда.
> Учитывая, что Пи — это иррациональное число, то есть, в его записи каждая следующая цифра непредсказуема,…

Довольно сомнительный вывод. Что вы понимаете под непредсказуемостью, и как это следует из иррациональности?
Наверное, неправильно сформулировал.
Я имею в виду то, что любой случайно взятый знак дробной части числа Пи может с равной вероятностью оказаться любой цифрой от 0 до 9 (или, в случае с HEX-ом, от 0 до F).
Да, неверно. Это — не непредсказуемость. И более того, совершенно не следует из иррациональности. Например, число 1.10100100010000100001 и т.д. иррациональное, хотя распределение цифр далеко от равномерного.
Если бы распределение в таких числах было хорошим, генераторы случайных чисел для криптографии были бы в разы проще.
Не факт. Допустим они абсолютно случайные.
Берём 76352843-ю цифру числа Пи. С одной стороны она абсолютно случайная. С другой стороны, не более случайная чем 76352843.
Ну и как такую случайность использовать в генераторе случайных чисел в криптографии?
Вам достаточно было бы получить одно случайное число-ключ с медленного физического генератора, а не забирать с него всю последовательность, например. Естественно, это очень упрощенный пример.
С другой стороны такое может не подойти из-за вот этого требования

Пусть генератор основывается на выводе бит какого-то представления числа Пи, начиная с какой то неизвестной точки. Такой генератор, возможно и пройдет «тест на следующий бит», так как ПИ, видимо, является случайной последовательностью (это было бы гарантированно, если доказать что Пи является нормальным числом). Однако этот подход не является критографически надежным — если криптоаналитик определит, какой бит числа Пи используется в данный момент, он сможет вычислить и все предшествующие биты.

ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8_%D1%81%D1%82%D0%BE%D0%B9%D0%BA%D0%B8%D0%B9_%D0%B3%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D1%82%D0%BE%D1%80_%D0%BF%D1%81%D0%B5%D0%B2%D0%B4%D0%BE%D1%81%D0%BB%D1%83%D1%87%D0%B0%D0%B9%D0%BD%D1%8B%D1%85_%D1%87%D0%B8%D1%81%D0%B5%D0%BB

Т.е. если часть полученной последовательности скомпрометирована, (т.е. стал известен порядковый номер цифры числа), то и вся последовательность становится известной.
Если вы перехватили часть последовательности гаммы(потока бит числа Пи в данном случае), то это не дает вам возможность найти следующие биты. Данное условие направлено было исходя из того, что алгоритм генерации — конечный автомат и по N отсчетам (n1,n2...nN) можно найти текущее состояние генератора. В случае же числа Пи сколько угодно отсчетов можете взять и это не поможет: существует бесконечно много отсчетов вида (n1,n2...nN,l1,l2....lL), т.е. включающих в себя выбранный.
Другими словами скомпрометированный кусок может продолжаться бесконечным числом способов.
Здесь речь про другое:
если криптоаналитик определит, какой бит числа Пи используется в данный момент, он сможет вычислить и все предшествующие биты.

если часть полученной последовательности скомпрометирована, (т.е. стал известен порядковый номер цифры числа)
Я как раз и отмечаю, что второе утверждение неверно: часть полученной последовательности не дает знания порядкового номера.
Здесь нигде не идёт речь про узнавание порядкового номера, с помощью полученной последовательности.

Речь просто про узнавание порядкового номера. Не важно каким путём.
next-bit тест будет тем не менее пройден.
pS. вот бы для всех шифров так анализ происходил: для начала найдем секретный ключ. не важно каким путем.
Во первых это требование написано в википедии, не я его выдумал.

Ну вот в моём примере выше.
Берём 76352843-ю цифру числа Пи. С одной стороны она абсолютно случайная. С другой стороны, не более случайная чем 76352843.


на что Milfgard отвечает
Вам достаточно было бы получить одно случайное число-ключ с медленного физического генератора, а не забирать с него всю последовательность, например.


Итак, у нас есть последовательность в миллион «случайных» бит числа ПИ, полученная начиная с позиции 76352843

И вот — 76352843 можно просто угадать. Это легче чем угадать миллион случайных бит.
Когда вы получили эту последовательность у вас нет гарантии, что данная последовательность не повторяется «чуть» раньше или «чуть» позже: до данной позиции у вас еще примерно столько же, сколько и порядковый номер, последовательностей длины миллион. Об этом я и говорю выше: вы не сможете просто так угадать этот номер, ведь данная последовательность будет встречаться бесконечное множество раз в Пи.
Возможно, я непонятно объясняю… =(
Я понимаю что она бесконечно много раз встречается.
Но это не влияет на то что 76352843 можно просто угадать, и легче чем угадать миллион случайных бит.

76352843 влезает в 56 бит. Если мы решили из 76352843 сделать миллион случайных бит, «сэкономив» генератор настоящих случайных чисел («медленных физический генератор»).

То, злоумышленник, зная этот алгоритм, не будет угадывать миллон бит, он знает что исходное число влезало в 56 бит, и ему нужно брутфорсить 56 бит, а не миллион.
У 76352843 уместится и в 32-битный int, что по сути ничего не меняет. Вы вслепую ссылаетесь на теорему Шеннона про идеальные шифры. Просто тогда и гамму надо как-то передавать по еще одному секретному каналу.
В том же RC4 когда ваш браузер безопасно соединяется вас же не смущает, что генерируется очень большая гамма из маленького начального ключа? Допустим, всего 128 бит?
Да, пардон, не 56 бит, а 56/2=28 бит.
В том же RC4 когда ваш браузер безопасно соединяется вас же не смущает, что генерируется очень большая гамма из маленького начального ключа? Допустим, всего 128 бит?

Как раз таки по этому стойкость там считается как 128 бит, а не миллион бит.

А если и этот начальный 128-битовый ключ генерировали бы из 28-битового индекса числа ПИ, то стойкость была бы 28 бит.
Тут довольно тонкий момент есть: 76352843 можно уместить и в 32-битное число, и в 128-битное и в 512-битное. Так вот в случае Пи это число бесконечно битное, просто старшие разряды нули. Или числа после некоего предела в последовательности Пи отбрасываются?
Тут довольно тонкий момент есть: 76352843 можно уместить и в 32-битное число, и в 128-битное и в 512-битное.

Я называю 76352843 28-ми битным, потому что по легенде мы получили его из медленного физического генератора настоящих случайных чисел, и этот факт известен злоумышленнику. Ясно что медленный генератор генерирует маленькие числа, и какая именно разрядность — известно злоумышленнику, т.к. алгоритм не является секретом.
В начальной фазе инициализации сколько захотите, столько и будет стойкость: никто не запрещает использовать AES и для ключей длины 32 биты. В этом случае нам уже не интересно есть ли дальше уязвимости. Интерес в том не вносит ли алгоритм генерации гаммы других уязвимостей, о чем собственно и говорит тест next-bit.
оно не иррациональное, оно трансцендентное
Трасцендентное — да, но почему же не иррациональное?
ну просто потому что это более строгое определение ))
Более строгое определение? Иррациональное число — это не определение числа, это его принадлежность множеству иррациональных чисел. Так, что пи — рациональное число, пи — действительное число, это верные утверждения. А то, что пи — не иррациональное число, т.е. не принадлежит множеству иррациональных чисел — утверждение неверное.
Хотели сказать, что трансцендентные числа — более узкое множество? Но, увы, число может быть:
1) Не иррациональное, не трансцендентное. Например, 1.
2) Иррациональное, не трансцендентное. Например, sqrt(2).
3) Не иррациональное, трансцендентное. Например, pi * i.
4) Иррациональное, трансцендентное, Например, pi.
вы в 4 пункте сами себе выше противоречите )))
вероятно описание 3 и 4 перепутали?
и я думаю мнимые единицы в данном контексте не сильно влияют на узость определения )))
даже Вики в этом соглашается
В 3 и 4 — нет, выше действительно есть опечатка, следует читать:
«Так, что пи — иррациональное число, пи — действительное число, это верные утверждения.»
Пи — иррациональное, трансцендентное, действительное число
Так не честно — вы комментарий уже исправили! )))
UFO just landed and posted this here
UFO just landed and posted this here
UFO just landed and posted this here
Да вы — просто кладезь интересных ссылок!
Между тем, я нашёл заметку Саймона Плаффа, где он рассказывает о том, как открыл эту формулу.
Интересна следующая цитата:
Величайшей ошибкой в моей жизни было то, что я позволил Боруэйну и Бэйли называться соавторами формулы, когда они не открыли ничего вообще.
(ориг. This is where I made the biggest mistake in my life: To accept the collaboration of Peter Borwein and David H. Bailey as co-founders of that algorithm and formula when they have found nothing at all)

UFO just landed and posted this here
UFO just landed and posted this here
UFO just landed and posted this here
Про точку Фейнмана не знал, очень интересно, спасибо.
Наверное, на днях займусь написанием статьи о формуле BBP для русской Википедии, учтя при этом замечания Хабра.
UFO just landed and posted this here
Напрямую — честно говоря, не знаю подходящих формул, из которых можно было бы что-нибудь подобное вывести.
А с промежуточным этапом в виде шестнадцатеричных знаков — с этим отлично справляется С-шный код, приведённый в статье.
А, значит, полагаю, и из формулы Белларда можно вывести, с промежуточным этапом в виде двоичных чисел.
И, похоже, вы только что прочитали первую русскоязычную статью об этом алгоритме в рунете — других я найти не смог.

а вот cih.ru/a1/e79.html
Ну, там этот алгоритм только упоминается вскользь, даже краткого описания нет. Но всё равно спасибо — вспомнил, что такое Web 1.0
По мне так почти вся статья про этот алгоритм, но нет формулы и примера реализации.
UFO just landed and posted this here
Саймон Плафф, как выяснилось, готов с вами поспорить.
Цитирую первые строчки:
We outline a method for computing the n'th decimal (or any other base) digit of Pi in
C*n^3*log(n)^3 time and with very little memory.
UFO just landed and posted this here
А чему соответствует C?
Имеется в виду следующее:
«Существует такая константа C, для которой при любом сколь угодно большом N время выполнения алгоритма будет ниже, чем C*n^3*log(n)^3».
По-другому то же самое можно записать как T = О(n^3*log(n)^3)
Тогда правильно ли я понимаю, что время выполнения не зависит от основания системы счисления, даже если оно будет порядка (2**64)?

Если так, то можно значительно ускорить вычисления за счет VLIW/SIMD.
Когда основание системы счисления — степень двойки, время будет О(n), в других случаях — O(n^3*log(n)^3).
Согласно эмпирическим данным, дробная часть числа Пи представляет собой нормальную числовую последовательность (хотя доказать это достоверно ещё не удалось), а значит, последовательности цифр из него можно использовать в генерации паролей и просто случайных чисел, или в криптографических алгоритмах (например, в хэшировании). Способов применения можно найти великое множество — надо только включить фантазию.

Для генерации паролей, случайных чисел и другого есть более оптимальные и менее ресурсозатратные методы.
Был проект распределенных вычислений пи до миллиардного знака, как раз эту формулу использовал. Там был клинт, нужно было его скачать, чтобы сервер выдал ему диапазон для вычисления
Это все было или в конце 90х или в начале 2000х, проект шел параллельно с SETI@Home и кембриджским проектом поиска лекарств. То есть эта формула реально работала в параллельных вычислениях
Сомневаюсь в ценности формулы для распределенных вычислений большого количества цифр. Время вычисления n-го знака O(n), то есть на вычисление n цифр потратим O(n^2) времени, думаю есть более эффективные методы. Или нет?
Для вычисления всех цифр до n есть алгоритм со сложностью O(M(n)*log(n)), где M(n) — сложность перемножения двух чисел длиной n бит.
полагаю для n порядка 10^13 это значительно лучше квадрата.
Зависит от того, что такое M(n). Если «тупо» в столбик умножать, то M(n)=O(n^2), если с быстрым преобразованием Фурье — то M(n) = O(n log(n)).
Спасибо кэп. Речь шла о константе n (log n) ^ 2 лучше O(n^2) или нет. Замечу еще что умножение с быстрым преобразованием Фурье помимо прочего хорошо распараллеливается.
А каков геометрический смысл этой формулы? Встречались статьи на русском? Что она говорит про суть числа пи и прочих, считаемых подобными формулами? Как доказано, что ими вычисляется именно пи, а не лабуда какая-нибудь?
То, что это пи, доказывается без особого труда (доказательство где-то на полстранички). В сущности, формула говорит, что пи — это какой-то логарифм (или их линейная комбинация).
Что то не пойму и как из этого получить 10-ичную цифру, кто то может объяснить?
position = 6
fraction = 0.533289136557027
hex digits = 8885A308D3
Меня одного смущает вот этот цикл в коде: for (k = 0; k < id; k++)?
Получается, чтобы вычислить цифру числа PI начиная с позиции id, нам придется выполнить id итераций этого цикла. Получается, алгоритм имеет сложность O(n) для вычисления n-й цифры числа.

Честно говоря, по заголовку подумал, что, найдена формула, которая имеет сложность O(1) для конкретной цифры числа. Формула, безусловно, красивая. Но думаю, что генератор случайных чисел создать на её базе, увы, не получится: накладно.
Sign up to leave a comment.

Articles