Обработка простых чисел Мерсенна - PullRequest
Новая
       17

Обработка простых чисел Мерсенна

0 голосов
/ 05 октября 2019

Меня интересовали простые числа Мерсенна https://www.mersenne.org/. Большой Интернет Mersenne Prime Search (GIMPS) проводит исследования в этой области. Это простые числа, но они очень большие и их мало. 49-й Mersenne Prime имеет длину 22 миллиона цифр. Невероятно, что одно число может состоять из 22 миллионов цифр.

Я пытался и смог поймать до 8-го Мерсенна Прайма, длиной 10 цифр и в пределах 2 миллиардов. Я использую Postgres BIGINT, который поддерживает целые числа длиной до 19 цифр, что составляет 9 миллионов миллиардов. Итак, если я обрабатываю 1 миллиард строк одновременно, мне потребуется 9 миллионов итераций. Я также могу использовать тип данных NUMERIC, который поддерживает 131072 цифры слева от десятичной точки и точность 16383 цифры. Конечно, мне нужно работать только с целыми числами. Мне не нужна точность. Другой альтернативой является CHAR VARYING компании Postgres, который хранит до миллиарда. Но его нельзя использовать для расчетов.

То, что предоставляет Postgres, достаточно для любых практических нужд. Мой вопрос в том, как ребята из GIMPS рассчитывают такие большие цифры. Они хранят эти числа в любой базе данных. Какая база данных поддерживает такие большие числа. Я не синхронизирован с прогрессами, сделанными в мире баз данных.

Я знаю, что они обладают огромной вычислительной мощностью. Кертис Купер упомянул, что 700 серверов используются для обнаружения и проверки чисел. Точно, сколько памяти нужно. Какой язык используется.

Просто любопытство. Похоже ли это, что я без работы.

спасибо

bb23850

1 Ответ

0 голосов
/ 05 октября 2019

Это слишком долго для комментария.

Мерсенна числа очень легко вычислить. Они всегда на единицу меньше, чем степень 2: 

select n, cast(power(cast(2 as numeric), n) - 1 as numeric(1000,0))
from generate_series(1, 100, 1) gs(n)
order by n;

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

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

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

...