Armazenar grandes números primos em um banco de dados

https://stackoverflow.com/questions/1907409

19-09-2019
|

Pergunta

Este problema me pareceu um pouco estranho. Estou curioso para saber como você pode representar uma lista de números primos em um banco de dados. Eu não sei de um único tipo de dados que seria capaz de acuratly e consistentemente armazenar uma grande quantidade de números primos. A minha preocupação é que quando os números primos estão começando a conter 1000s de dígitos, que pode ser um pouco difícil de formulário de referência do banco de dados. Existe uma maneira de representar um grande conjunto de números primos em um banco de dados? Tenho certeza de que isso tenha tópico foi abordado antes.

Uma das questões sobre este que torna difícil é que os números primos não pode ser dividido em fatores. Se eles pudessem este problema seria muito mais fácil.

Solução

Se você realmente deseja armazenar números primos como números e uma das perguntas, que você parar é "números primos não pode ser dividido em fatores", há outra coisa: armazená-lo em lista de módulo de qualquer número ordenados por sequência.

Um pequeno exemplo:

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

Lista é:

81, 17, 83, 2

Na aplicação real é útil para dividir pelo módulo de 2 ^ 32 (32 bits inteiros), especialmente se os números primos em aplicação de processamento armazenados como matrizes de bytes.

O armazenamento em DB:

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;

inserção por exemplo acima (1,647 é apenas para exemplo):

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);

valor prime_id pode ser atribuído a partir de seqüência de Oracle ...

create sequence seq_primes start with 1 increment by 1;

Get ID do próximo número primo para inserir:

select seq_primes.nextval from dual;

selecionar o conteúdo número primo com id especificado:

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

Outras dicas

Você pode armazená-los como dados binários. Eles não vão ser reta legível do banco de dados, mas isso não deve ser um problema.

Bases de Dados (dependendo de qual) podem rotineiramente armazenar números até 38-39 dígitos com precisão. Que você fica razoavelmente longe.

Além de que você não vai estar fazendo operações aritméticas sobre eles (precisão) em bancos de dados (com exceção de módulos de precisão arbitrária que possam existir para o seu banco de dados específico). Mas os números podem ser armazenados como texto até vários milhares de dígitos. Além de que você pode usar campos de tipo CLOB para armazenar milhões de dígitos.

Além disso, vale a pena nada que se você está armazenando seqüências de números primos e seu interesse está no espaço-compressão dessa sequência, você poderia começar por armazenar a diferença entre um número e no próximo em vez do número inteiro.

Este é um pouco ineficiente, mas você pode armazená-los como strings.

Se você não vai usar cálculos do lado do banco de dados com esses números, apenas armazená-los como seqüências de sua representação binária bit (BLOB, VARBINARY etc.)

Aqui está o meu valor de 2 centavos. Se você quiser guardá-los como números em um banco de dados, então você vai ser limitado pelo tamanho máximo de número inteiro que seu banco de dados pode manipular. Você provavelmente iria querer uma tabela 2 coluna, com o número primo em uma coluna e do número de série no outro. Então você quer alguns índices para fazer encontrar os valores armazenados rápida.

Mas você realmente não quer fazer isso você, você deseja armazenar humongous (sp?) Primos muito além de qualquer tipo de dados inteiro você tem mesmo que ainda. E você diz que você é avesso a cordas por isso é dados binários para você. (Seria para mim também.) Sim, você pode armazená-los em um BLOB em um banco de dados, mas que tipo de instalações vão os DBMS oferecer-lhe para encontrar o n-th principal ou verificar o primeness de um inteiro candidato?

Como conceber uma estrutura de arquivo adequado? Este é o melhor que eu poderia vir acima com após cerca de 5 minutos pensando:

Definir um contador para 2.
Escrever os dois bits que representam o primeiro número primo.
Escreva-los novamente, para marcar o fim da seção que contém os números primos 2 bits.
Definir o contador para contador + 1
Escreva os números primos 3 bits em ordem. (Eu acho que existem dois: 5 e 7)
Escrever o último dos primos 3 bits novamente para marcar o fim da seção que contém os números primos 3 bits.
Volte para 4 e continue com as necessárias adaptações.

O ponto de escrever o último primeiro-n-bit duas vezes é para lhe fornecer um meio para identificar o fim da parte do arquivo com números primos de n bits em que quando você vem para ler o arquivo.

Como você gravar o arquivo, você provavelmente também quer ter a nota das compensações para os arquivos em vários pontos, talvez no início de cada seção que contém números primos n bits.

Eu acho que isso iria funcionar, e ele iria lidar com números primos até 2 ^ (o maior inteiro sem sinal pode representar). Eu acho que seria fácil o suficiente para encontrar o código para traduzir um valor 325467-bit (por exemplo) em um grande número inteiro.

Claro, você poderia armazenar esse arquivo como um BLOB, mas eu não sei por que você iria se preocupar.

Tudo depende de que tipos de operações que você quer fazer com os números. Se apenas loja e pesquisa, então é só usar cordas e usar um tipo de dados restrição de verificação / domínio para impor que eles são números. Se você quiser mais controle, então o PostgreSQL vai deixar você definir tipos de dados personalizados e funções. Você pode, por exemplo de interface com o GMP biblioteca ter ordenação correta e aritmética para inteiros de precisão arbitrária. Usando uma biblioteca ainda permitirá que você implementar uma restrição de verificação que usa o teste de primalidade probabilística para verificar se os números realmente são primos.

A verdadeira questão é, na verdade, se um banco de dados relacional é a ferramenta correta para o trabalho.

Eu acho que você é melhor fora de usar um BLOB. Como os dados são armazenados em sua BLOB depende da sua utilização prevista para os números. Se você quiser usá-los nos cálculos eu acho que você vai precisar para criar uma classe ou espécie para armazenar os valores como alguns variedade de valor binário ordenada e permitir que eles sejam tratados como números, etc. Se você só precisa exibi-los em seguida, armazená-los como uma sequência de caracteres seria suficiente, e eliminaria a necessidade de converter seus valores calculatable a algo displayable, o que pode ser muito demorado para grandes valores.

Compartilhar e apreciar.

Provavelmente não é brilhante, mas o que se armazenados-los de alguma estrutura de dados recursiva. Você pode armazená-lo como um int, é expoente, e uma referência aos números de bits menor.

Como a idéia string, ela provavelmente não seria muito bom para considerações de memória. E consulta tempo seria aumentado devido à natureza recursiva da consulta.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow