Хранение больших простых чисел в базе данных

StackOverflow https://stackoverflow.com/questions/1907409

Вопрос

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

Одна из проблем, связанных с этим, которая затрудняет задачу, заключается в том, что простые числа нельзя разбить на множители.Если бы они могли, эта проблема была бы намного проще.

Это было полезно?

Решение

Если вы действительно хотите хранить простые числа в виде чисел и один из вопросов, останавливающих вас, - "простые числа не могут быть разбиты на множители", есть еще одна вещь:сохраните его в списке модулей любого числа, упорядоченного по последовательности.

Небольшой пример:

2831781 == 2*100^3 + 83*100^2 + 17*100^1 + 81*100^0

Список таков:

81, 17, 83, 2

В реальном приложении полезно разбивать по модулю 2 ^ 32 (32-битные целые числа), особенно если простые числа в обрабатывающем приложении хранятся в виде массивов байтов.

Хранение в базе данных:

create table PRIMES
(
  PRIME_ID         NUMBER not null,
  PART_ORDER       NUMBER(20) not null,
  PRIME_PART_VALUE NUMBER not null
);

alter table PRIMES 
add constraint PRIMES_PK primary key (PRIME_ID, PART_ORDER) using index;

вставьте, например, выше (1647 приведен только для примера):

insert into primes(PRIME_ID, PART_ORDER, PRIME_PART_VALUE) values (1647, 0, 81);
insert into primes(PRIME_ID, PART_ORDER, PRIME_PART_VALUE) values (1647, 1, 17);
insert into primes(PRIME_ID, PART_ORDER, PRIME_PART_VALUE) values (1647, 2, 83);
insert into primes(PRIME_ID, PART_ORDER, PRIME_PART_VALUE) values (1647, 3, 82);

значение prime_id может быть присвоено из последовательности oracle ...

create sequence seq_primes start with 1 increment by 1;

Получаем ИДЕНТИФИКАТОР следующего простого числа для вставки:

select seq_primes.nextval from dual;

выберите содержимое простого числа с указанным идентификатором:

select PART_ORDER, PRIME_PART_VALUE 
from primes where prime_id = 1647 
order by part_order

Другие советы

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

Базы данных (в зависимости от того, какие именно) могут регулярно хранить номера с точностью до 38-39 цифр.Это заведет вас достаточно далеко.

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

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

Это немного неэффективно, но вы могли бы сохранить их в виде строк.

Если вы не собираетесь использовать вычисления на стороне базы данных с этими числами, просто сохраните их как битовые последовательности их двоичного представления (BLOB, VARBINARY и т.д.)

Вот мои 2 цента.Если вы хотите сохранить их как числа в базе данных, то вы будете ограничены максимальным размером целого числа, которое может обрабатывать ваша база данных.Вероятно, вам нужна таблица с двумя столбцами, с простым числом в одном столбце и его порядковым номером в другом.Тогда вам понадобятся некоторые индексы, чтобы ускорить поиск сохраненных значений.

Но вы же на самом деле не хотите этого делать, не так ли, вы хотите хранить огромные (sp?) простые числа намного выше любого целочисленного типа данных, о котором вы пока знаете.И вы говорите, что не любите строки, поэтому для вас это двоичные данные.(Для меня это было бы тоже самое.) Да, вы могли бы сохранить их в виде большого двоичного объекта в базе данных, но какие возможности предложит вам СУБД для нахождения n-го простого числа или проверки простоты возможного целого числа?

Как создать подходящую файловую структуру?Это лучшее, что я смог придумать примерно после 5 минут размышлений:

  1. Установите счетчик на 2.
  2. Запишите два бита, которые представляют первое простое число.
  3. Запишите их еще раз, чтобы отметить конец раздела, содержащего 2-разрядные простые числа.
  4. Установите счетчик в положение счетчик+1
  5. Запишите 3-разрядные простые числа по порядку.( Я думаю, что есть два варианта:5 и 7)
  6. Запишите последнее из 3-разрядных простых чисел еще раз, чтобы отметить конец раздела, содержащего 3-разрядные простые числа.
  7. Возвращайтесь к 4 и продолжайте с соответствующими изменениями.

Смысл записи последнего n-разрядного простого числа дважды состоит в том, чтобы предоставить вам средство для идентификации конца части файла с n-разрядными простыми числами в нем, когда вы приступаете к чтению файла.

При написании файла вы, вероятно, также захотите отметить смещения в файлах в разных точках, возможно, в начале каждого раздела, содержащего n-разрядные простые числа.

Я думаю, это сработало бы, и оно обрабатывало бы простые числа до 2 ^ (самое большое целое число без знака, которое вы можете представить).Я думаю, было бы достаточно легко найти код для преобразования, скажем, 325467-битного значения в большое целое число.

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

Все зависит от того, какие операции вы хотите выполнять с числами.Если просто хранить и выполнять поиск, то просто используйте строки и используйте контрольное ограничение / доменный тип данных, чтобы убедиться, что они являются числами.Если вы хотите больше контроля, то PostgreSQL позволит вам определить пользовательские типы данных и функции.Вы можете, например, взаимодействовать с GMP библиотека для правильного упорядочения и арифметики целых чисел произвольной точности.Использование такой библиотеки даже позволит вам реализовать контрольное ограничение, которое использует вероятностный тест на простоту, чтобы проверить, действительно ли числа простые.

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

Я думаю, вам лучше всего использовать BLOB.То, как данные хранятся в вашем большом двоичном объекте, зависит от предполагаемого использования вами чисел.Если вы хотите использовать их в вычислениях, я думаю, вам нужно будет создать класс или тип для хранения значений в виде некоторой разновидности упорядоченного двоичного значения и разрешить обрабатывать их как числа и т.д.Если вам просто нужно отобразить их, то было бы достаточно сохранить их в виде последовательности символов и устранить необходимость преобразования ваших вычисляемых значений во что-то отображаемое, что может занять очень много времени для больших значений.

Делитесь и наслаждайтесь.

Возможно, это не блестяще, но что, если бы вы сохранили их в какой-нибудь рекурсивной структуре данных?Вы могли бы сохранить его как int, это показатель степени и ссылка на младшие разрядные числа.

Как и идея со строками, это, вероятно, было бы не очень хорошо с точки зрения памяти.И время выполнения запроса было бы увеличено из-за рекурсивного характера запроса.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top