Comments 52
А вот у меня вопрос возник: в этом есть какое-то практическое значение? Может в каких-то очень специфических расчетах надо. Или просто флаговтык?
Ещё спросите, зачем мы ищем самые большие простые числа в мире :)
А вот это как раз где-то в криптографии применяют. Вроде.
Точно как на картинках))
Нет, эти очень большие простые числа нигде не применяют. Ибо они уж очень большие. Если вам для хранения ключа нужен отдельный жесткий диск, а операция шифрования занимает часы или дни, это не очень практично.
Одно из самых распространенных применений простых чисел — система шифрования RSA.
Допустим, Алиса и Боб хотят секретно пообщаться в Интернете. Им нужна система шифрования. Если они сначала встретятся лично, они могут оговорить метод шифрования и дешифрования, который будет известен только им, но если же первый разговор состоится в онлайне, им придется сперва открыто обсудить систему шифрования — а это риск.
Однако если Алиса выберет два больших числа, рассчитает их произведение и сообщит об этом открыто, определить первоначальные простые числа будет очень сложно, потому что только она знает множители.
Поэтому Алиса сообщает свое произведение Бобу, сохраняя в тайне множители. Боб использует произведение для шифрования своего послания Алисе, которое можно расшифровать только при помощи известных ей множителей. Если Ева захочет подслушать, она никогда не сможет расшифровать сообщение Боба, если не заполучит множители Алисы. Если Ева попытается разложить произведение, у нее это не получится, потому что не существует такого алгоритма, который справился бы с этой задачей за время жизни Вселенной.
(с)
Я знаю, как работает RSA. Но там не нужны офигенно большие числа, потому что с ними сложно работать. Ну, 2048-бит используют. Взломать такое даже на самом большом кластере получится лишь за миллиарды лет. И числа такого размера вы можете запросто сгенерировать за несколько секунд на своем компьютере.
А математики уже давно ищут гораздо более большие числа. Вроде этого, где 80 миллионов бит. Нормально вам будет каждый раз при установлении соединения по https ждать, пока 80мб только ключа скачается?
А вот у меня вопрос возник: в этом есть какое-то практическое значение? Может в каких-то очень специфических расчетах надо. Или просто флаговтык?
А у вашего вопроса какое практическое значение?)
Пустить солнечного зайчика на обратной стороне Луны - цель сама по себе особого практического смысла не имеет. Зато сколько важных задач нужно решить, что её достичь!
В основном флаговтык. Именно поэтому считать только сейчас начали, а до этого индийско-китайская рациональная апроксимация 355/113 многие годы (или даже века) была достаточной для практики
С физической точки зрения - нет. Всего лишь 80 знаков досаточно, чтобы рассчитать длину окружности радиусом со всю наблюдаемую вселенную с точностью до планковской длины.
в этом есть какое-то практическое значение?
Конечно. В процессе решения этой задачки были найдены баги в процессоре и реализации библиотечного алгоритма. Это очень важные и очень практические результаты.
Может в каких-то очень специфических расчетах надо.
В расчётах вряд ли, а вот какие-нибудь гипотезы по распределению или наличию закономерностей циферок в иррациональных числах определённо существуют и такие расчёты могли бы опровергнуть какие-то из них. Или породить новые. Правда, не знаю, являются ли для вас научные результаты "практическими".
Так-то с "практическим" значением у науки всегда "проблемы" :). Шарообразность Земли была известна древним грекам, а Эратосфен еще в ~240году до н.э. расчитал и длину меридиана. Но на практике это попытался применить только Колумб, но и то, если бы знал результат Эратосфена, то не поплыл бы :).
Да и те же простые числа - тот же Эратосфен простой метод для их поиска изобрёл, а практическое применение им нашлось только аж в ХХ веке. Вот, может через пару тысячелений и триллионы цифр числа пи куда приспособят...
в этом есть какое-то практическое значение?
Это хороший способ "сверить часы". Т.е. сравнить значения, полученные разными формулами, разными алгоритмами, разными реализациями, разными библиотеками и т.п. Попутно найти ошибки во всем этом, за исключением, может быть, формул.
Ну и реклама, конечно. Вот статью на Хабре написали :)
Если говорить про физические измерения и реально наблюдаемые величины, то размер атома отличается от размера видимой вселенной менее чем на 40 порядков.
В криптографии тоже вроде всерьёз давно не используется.
А где скачать?
Decimal Digits 105,000,000,000,000
Hexadecimal Digits 87,200,612,490,794
Если я правильно посчитал это около 40 Тбайт
Интересно было бы посмотреть, как хорошо это дело сжимается архиватором.
Это не должно сжиматься архиватором просто по определению.
Погуглил немного. Выяснилось, что борьба идёт не за сжатие, а за "оптимальность хранения":
Storing each single (0–9) digit per byte (0–255) would be incredibly
wasteful (only 41.52% efficiency). So y-cruncher employs its own
compression method to pack 19 decimal digits in a 64-bit (8-byte) chunk
which is 98.62% efficient. (I would have chosen to pack 12 decimal
digits in each 40-bit (5-byte) chunk to achieve 99.66% efficiency but
maybe there was another reason it was more optimal to have 8-byte
aligned chunks).
http://www.eveandersson.com/pi/precalculated-frequencies распределение цифр в Пи. Как подметили, только ноль чуть-чуть отстает.
В том и суть, что повторений особо нет, число несжимаемо, как вода
Мне вот интересно, как проверяют правильность расчётов, если это первый раз в истории, когда эти цифры вообще были посчитаны? С чем сравнивать? Скажем, в статье упоминается, что нашли ошибку в умножении. Как именно её поймали? Как ни кручу в голове, выходит, что для этого нужно иметь другой алгоритм, который тоже вычислит те же самые цифры, но "надёжнее". Причём он должен работать ещё и на другой физической машине, с отличающимся железом, чтобы не повторялись ошибки оборудования…
Можно сравнить с предыдущим и если первые 100 триллионов сошлись 1 в 1 - значит последние 5 триллионов, вероятнее всего, можно считать правильными. А ошибки выловили, вероятно, когда данные не сошлись.
Могу рассказать, как это происходит для простых чисел Мерсенна.
Когда обнаруживается новый кандидат, ту же самую экспоненту проверяют:
Тем же алгоритмом на другом оборудовании (видеокарте, CPU другого производителя).
Другим алгоритмом.
Только после завершения этих двух видов проверок, если они подтверждают положительный результат, анонсируется новое ПЧМ.
Тем же алгоритмом на другом оборудовании (видеокарте, CPU другого производителя).
А как часто не сходится?
С 1996 года ни разу не было :) Но там ПО довольно качественно написано - коррекция ошибок и всякое такое. Ошибка по большей части ожидается аппаратная - сбой ячейки оперативной памяти или нечто подобное.
жаль :)
Вдруг бы оказалось, алгоритмические расчёты на таких задачах не дают 100% воспроизводимый результат.
Там ещё может быть тонкость в особенностях платформы. Математически формула может быть совершенно точна, но при вычислении можем упереться в какую-нибудь невозможность точного представления иррациональных чисел в памяти компьютера.
В вычматах такое сплошь и рядом, что вычисляют сходящийся ряд или интеграл, а результат улетает в какие-то дебри, так как, например, использование чисел фиксированной длины приводит к неустранимому накоплению ошибок. И это всё приходится отдельно исследовать и доказывать применимость формулы уже для реальных вычислений на физическом оборудовании.
Где-то на хабре недавно было обсуждение того, что нейросеть это чёрный ящик с непредсказуемым результатом, и был поднят вопрос о том, насколько гарантированно воспроизводимы старые добрые алгоритмы.
В теории проблема понятна, а вот как оно на практике.
А при чём тут нейросеть? И вычисление числа пи, и вычматы, о которых я говорил, выполняются традиционными детерминированными алгоритмами.
В обсуждении нейросетей зашла речь о том, дают ли не_нейросети гарантированный повторяемый результат.
В данном обсуждении появился комментарий, из которого можно было сделать вывод о том, что могут и не давать, и мне стали интересны примеры.
Всё упирается в исходные условия задачи. Так-то и нейросеть может быть строго детерминированной, если у неё отключён режим обучения, а все входы контролируются до единого бита. Внутри сети эти биты просто перетасовываются по строго определённым фиксированным правилам и на выходе будет стабильный результат. Часто "неопределённость" связана с отклонениями во входных данных, которые для нас незначительны, но в конкретной нейросети с определёнными коэффициентами могут неожиданно увести в совершенно иную область. Впрочем, и в традиционных алгоритмах такое случается, а зачастую даже является желаемым результатом, как в хэш-функциях. Просто в хэш-функциях мы об этом знаем и этого хотим, а в нейросетях, обычно, наоборот.
Но если начать копать особенно глубоко, то вылезают всякие интересности, связанные с невозможностью гарантировать воспроизводимость работы самого железа. Всегда могут быть сбои, вызванные как несовершенством техпроцессов и устареванием, так и внешними событиями типа космических лучей. Конечно, можно бороться с подобными проблемами, уменьшая вероятность сбоев до сколь угодно низких значений путём дублирования и перепроверки, но строгой стопроцентной гарантии идеальности добиться будет невозможно. Хотя бы из-за того, что в самой глубине мы упираемся в квантовую механику с принципиально вероятностным поведением объектов.
Вопрос сбоев из-за того, что пролетавшая альфа-частица переключила 5нм транзистор, это тоже интересно, но мне больше интересны другие моменты.
Самый очевидный вариант получения другого результата состоит в том, что изменился сам язык программирования или задействованные внешних решения. Ну типа, теперь синус считается по другой формуле.
Но может быть что-нибудь и похитрее.
Вот например, если мы берём мудрёную математику и распараллеливаем вычисления с плавающей запятой, то всегда ли мы будем получать один и тот же конечный результат?
Assertion с другими алгоритмами вычисления дробей, наверное, на каждый член ряда
Давайте уже добавим причину минуса «отвратительный перевод».
Объём локальной памяти в коробке. Доставить эту установку до финиша...
Ну, теперь заживём... ))
Команда инженеров из StorageReview рассчитала число «Пи» до 105 трлн знаков после запятой за 75 суток