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

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

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

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

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

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

Благодарность

bb23850


postgresql sql bigint
person BB23850    schedule 05.10.2019    source источник
comment
Что касается GIMPS, похоже, что их исходный код находится в Assembly. Я не очень много знаю о ассемблере (на самом деле очень мало), но, насколько я знаю, ассемблеру не нужны типы данных, он просто перемещает области памяти. Таким образом, хранение миллионов или даже миллиардов цифр — это всего лишь вопрос распределения памяти. Бит есть бит, и не имеет значения, является ли этот бит частью числа, слова, даты или чего-то еще. Ассемблер знает только битовые операции (опять же, насколько мне известно).   -  person HoneyBadger    schedule 05.10.2019
comment
Спасибо за Ваш ответ. Что не выходит, так это то, как они хранят эти числа для повторного использования. Числа Мерсенна не являются простыми. Нужно проверить его по простому числу. Следовательно, Prime Number должен храниться в базе данных или файле. Это мое понимание.   -  person BB23850    schedule 05.10.2019

Ответы (1)


arrow_upward
1
arrow_downward

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

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

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 должно быть простым, чтобы число, соответствующее числу Мерсенна, было простым.

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

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

person Gordon Linoff    schedule 05.10.2019
comment
Спасибо за Ваш ответ. Не все числа Мерсенна являются простыми. 2^4-1=15, 2^6-1=63 не являются простыми числами. Мне потребовалось почти 24 часа, чтобы обработать 1 миллиард чисел и определить простые числа. Теперь я понимаю, насколько это колоссальная работа. Вы имеете в виду, что существуют альтернативные алгоритмы для проверки того, что это простое число или нет. Это интересный предмет для изучения. Но я бы не стал так просто отказываться от баз данных. - person BB23850; 05.10.2019
comment
@BB23850 . . . Я многое понимаю в базах данных, немного в теории чисел и достаточно в высшей математике, чтобы знать, что базы данных вряд ли помогут в этом начинании, кроме как в качестве хранилища данных для информации как части более сложного алгоритма. Но я призываю вас в вашем стремлении лучше понять простые числа Мерсенна, простые числа в целом и теорию чисел. - person Gordon Linoff; 05.10.2019