Хранение больших простых чисел в базе данных
Эта проблема, которой показались мне немного нечетный. Мне любопытно, как Вы могли представить список простых чисел в базе данных. Я не знаю о единственном типе данных, который смог бы к acuratly и последовательно хранил бы большое количество простых чисел. Мое беспокойство - то, что, когда простые числа начинают содержать 1000-е цифр, что это могло бы быть немного трудно к ссылке, формируют базу данных. Существует ли способ представить большой набор начал в DB? Я совершенно уверен, что это имеет тему, был приближен прежде.
Одна из проблем об этом, которое мешает, - то, что простые числа не могут быть разломаны на факторы. Если бы они могли эта проблема быть намного легче.
9 ответов
Если вы действительно хотите хранить простые числа в виде чисел, и вас останавливает один из вопросов: «простые числа не могут быть разбиты на множители», есть еще одна вещь: сохраните его в списке модулей любого числа, упорядоченного по порядку.
Небольшой пример:
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 может быть присвоено из последовательности оракула ...
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
Все зависит от того, какие операции вы хотите выполнять с числами. Если просто хранить и искать, просто используйте строки и используйте ограничение проверки / тип данных домена, чтобы убедиться, что они являются числами. Если вам нужен больший контроль, PostgreSQL позволит вам определять пользовательские типы данных и функции. Например, вы можете взаимодействовать с библиотекой GMP , чтобы иметь правильный порядок и арифметику для целых чисел произвольной точности. Использование такой библиотеки даже позволит вам реализовать ограничение проверки, которое использует вероятностный тест на простоту, чтобы проверить, действительно ли числа являются простыми.
Реальный вопрос в том, действительно ли реляционная база данных является правильным инструментом для работы.
Возможно, не блестяще, но что, если бы вы сохранили их в некоторой рекурсивной структуре данных. Вы можете сохранить его как int, его показатель степени и ссылку на младшие битовые числа.
Как и идея со строкой, это, вероятно, не очень хорошо с точки зрения памяти. И время запроса будет увеличено из-за рекурсивного характера запроса.
Я думаю, вам лучше использовать BLOB. Как данные хранятся в вашем большом двоичном объекте, зависит от предполагаемого использования чисел. Если вы хотите использовать их в вычислениях, я думаю, вам нужно создать класс или тип для хранения значений в виде некоторого разнообразия упорядоченных двоичных значений и разрешить их обрабатывать как числа и т.д. Если вам просто нужно отобразить их, тогда достаточно было бы хранить их в виде последовательности символов, и это избавило бы от необходимости преобразовывать ваши вычисляемые значения во что-то отображаемое, что может занять очень много времени для больших значений.
Поделитесь и наслаждайтесь.
Вы можете хранить их как двоичные данные. Они не будут читаться человеком прямо из базы данных, но это не должно быть проблемой.
Базы данных (в зависимости от того, какие) могут регулярно хранить числа до 38-39 цифр с точностью. Это уведет вас достаточно далеко.
Кроме того, вы не будете выполнять арифметические операции с ними (точно) в базах данных (за исключением модулей произвольной точности, которые могут существовать для вашей конкретной базы данных). Но числа могут храниться в виде текста до нескольких тысяч цифр. Кроме того, вы можете использовать поля типа CLOB для хранения миллионов цифр.
Кроме того, ничего не стоит, если вы храните последовательности простых чисел и вас интересует пространственное сжатие этой последовательности, вы могли бы начать с сохранения разницы между одним числом и другим, а не целым числом.
Это немного неэффективно, но вы можете сохранить их в виде строк.
Если вы не собираетесь использовать вычисления на стороне базы данных с этими числами, просто сохраните их как битовые последовательности их двоичного представления ( BLOB , VARBINARY ] и т. д.)
Вот мои 2 цента. Если вы хотите сохранить их как числа в базе данных, вы будете ограничены максимальным размером целого числа, которое может обрабатывать ваша база данных. Вам, вероятно, понадобится таблица из 2 столбцов, с простым числом в одном столбце и порядковым номером в другом. Тогда вам понадобятся индексы, чтобы быстро находить сохраненные значения.
Но вы действительно не хотите этого делать, ведь вы хотите хранить огромные (sp?) Простые числа, выходящие за рамки любого целого типа данных, который вы даже хотя еще. И вы говорите, что не любите строки, поэтому это двоичные данные для вас. (Это было бы и для меня.) Да, вы могли бы хранить их в большом двоичном объекте базы данных, но какие средства СУБД предложит вам для поиска n-го простого числа или проверки простоты целого числа-кандидата?
Как разработать подходящую файловую структуру? Это лучшее, что я смог придумать примерно после 5 минут размышлений:
- Установите счетчик на 2.
- Запишите два бита, которые представляют первое простое число.
- Запишите их снова, чтобы отметить конец секции, содержащей 2-битные простые числа.
- Установить счетчик на counter + 1
- Записать 3-битные простые числа по порядку. (Думаю, их два: 5 и 7)
- Запишите последнее из 3-битных простых чисел еще раз, чтобы отметить конец раздела, содержащего 3-битные простые числа.
- Вернитесь к 4 и продолжайте mutatis mutandis .
Смысл записи последнего n-битного простого числа дважды состоит в том, чтобы предоставить вам возможность идентифицировать конец части файла с n-битными простыми числами в нем, когда вы приходите читать файл.
Как вы пишете файл, вы, вероятно, также захотите записать смещения в файлах в различных точках, возможно, в начале каждого раздела, содержащего n-битные простые числа.
Я думаю, что это сработает, и он будет обрабатывать простые числа до 2 ^ (наибольшее целое число без знака, которое вы можете представить). Думаю, было бы достаточно легко найти код для преобразования (скажем, 325467-битного) значения в большое целое число.
Конечно, вы можете сохранить этот файл как BLOB, но я не уверен, зачем вам это нужно.
Я, вероятно, также захочу отметить смещения в файлах в различных точках, возможно, в начале каждого раздела, содержащего n-битные простые числа.Я думаю, что это сработает, и он будет обрабатывать простые числа до 2 ^ (самый большой целое число без знака, которое вы можете представить). Думаю, было бы достаточно легко найти код для преобразования (скажем, 325467-битного) значения в большое целое число.
Конечно, вы можете сохранить этот файл как BLOB, но я не уверен, зачем вам это нужно.
Я, вероятно, также захочу отметить смещения в файлах в различных точках, возможно, в начале каждого раздела, содержащего n-битные простые числа.Я думаю, что это сработает, и он будет обрабатывать простые числа до 2 ^ (самый большой целое число без знака, которое вы можете представить). Думаю, было бы достаточно легко найти код для преобразования (скажем, 325467-битного) значения в большое целое число.
Конечно, вы можете сохранить этот файл как BLOB, но я не уверен, зачем вам это нужно.