Le stockage de grands nombres premiers dans une base de données

Question

Ce problème m'a frappé comme un peu bizarre. Je suis curieux de savoir comment vous pouvez représenter une liste des nombres premiers dans une base de données. Je ne sais pas d'un seul type de données qui serait en mesure de stocker acuratly et toujours une grande quantité de nombres premiers. Ma préoccupation est que lorsque les nombres premiers commencent à contenir 1000s de chiffres, qu'il pourrait être un peu difficile à référencer former la base de données. Y at-il une façon de représenter un grand ensemble de nombres premiers dans un DB? Je suis tout à fait sûr que ce sujet a été abordé a avant.

L'une des questions sur ce qui rend difficile est que les nombres premiers ne peuvent pas être divisés en facteurs. Si ce problème, ils pourraient seraient beaucoup plus facile.

Answer 1

Si vous voulez vraiment stocker les nombres premiers comme les nombres et l'une des questions, vous arrêtez est « nombres premiers ne peuvent pas être divisés en facteurs », il y a une autre chose: stocker dans la liste du module d'un nombre quelconque ordonné par séquence.

Petit exemple:

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

Liste est:

81, 17, 83, 2

Dans l'application réelle est utile de regrouper par module 2 ^ 32 (nombres entiers de 32 bits), spécialement si les nombres premiers dans l'application de traitement stockées en tant que tableaux d'octets.

Stockage dans 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;

insérer par exemple ci-dessus (1647 est par exemple seulement):

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 valeur peut être affectée de la séquence d'oracle ...

create sequence seq_primes start with 1 increment by 1;

Obtenir ID du numéro NextPrime d'insérer:

select seq_primes.nextval from dual;

sélectionner le contenu du premier avec identifiant spécifié:

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

Answer 2

Vous pouvez les stocker sous forme de données binaires. Ils ne seront pas directement lisible par l'homme à partir de la base de données, mais cela ne devrait pas être un problème.

Answer 3

Base de données (selon lequel) peut stocker systématiquement des nombres jusqu'à 38-39 chiffres avec précision. Que vous obtient raisonnablement bien.

Au-delà, vous ne serez pas faire des opérations arithmétiques sur les (avec précision) dans les bases de données (sauf modules de précision arbitraire qui peuvent exister pour votre base de données particulière). Mais les chiffres peuvent être stockés sous forme de texte jusqu'à plusieurs milliers de chiffres. Au-delà, vous pouvez utiliser des champs de type CLOB pour stocker des millions de chiffres.

Aussi, il est ne vaut rien que si vous stockez des séquences de nombres premiers et votre intérêt est dans l'espace de compression de cette séquence, vous pouvez commencer en stockant la différence entre un numéro et le suivant plutôt que le nombre entier.

Answer 4

est un peu inefficace, mais vous pouvez les stocker sous forme de chaînes.

Answer 5

Si vous ne comptez pas utiliser des calculs côté base de données avec ces chiffres, il suffit de les stocker sous forme de séquences de bits de leur représentation binaire (BLOB, VARBINARY etc.)

Answer 6

Voici mes 2 cents vaut. Si vous voulez les stocker sous forme de chiffres dans une base de données, vous serez limité par la taille maximale de votre base de données entier peut gérer. Vous auriez probablement besoin d'une table de la colonne 2, le nombre premier dans une colonne et il est le numéro de séquence dans l'autre. Ensuite, vous voudriez quelques indices pour faire trouver les valeurs stockées rapidement.

Mais vous ne voulez pas vraiment faire que vous le faites, vous voulez stocker Humongous (sp?) Nombres premiers au-delà tout type de données entier que vous avez même si pour le moment. Et vous dites que vous êtes opposé à des chaînes il est donc des données binaires pour vous. (Ce serait pour moi aussi.) Oui, vous pouvez les stocker dans une base de données BLOB dans une mais quel genre d'installations sera le SGBD vous permettent de trouver le premier n-ième ou le contrôle du primeness d'un entier candidat?

Comment concevoir une structure de fichier approprié? C'est le meilleur que je pouvais trouver après environ 5 minutes en pensant:

1. Définir un compteur à 2.
2. Ecrire les deux bits qui représentent le premier nombre premier.
3. Écrivez-les à nouveau, pour marquer la fin de la section contenant les nombres premiers 2 bits.
4. le compteur à contre + 1
5. Ecrire les nombres premiers 3 bits dans l'ordre. (Je pense qu'il ya deux: 5 et 7)
6. Ecrire le dernier des trois nombres premiers bits à nouveau pour marquer la fin de la section contenant les nombres premiers 3 bits.
7. Retour à 4 et continuez mutatis mutandis.

Le point sur l'écriture du dernier premier est deux fois n bits pour vous fournir un moyen d'identifier la fin de la partie du fichier avec les nombres premiers n bits dans quand vous venez de lire le fichier.

Comme vous écrivez le fichier, vous voudrez probablement aussi prendre note des décalages dans les fichiers en divers points, peut-être le début de chaque section contenant des nombres premiers n bits.

Je pense que cela fonctionnerait, et il gérerait les nombres premiers jusqu'à 2 ^ (le plus grand entier non signé, vous pouvez représenter). Je suppose que ce serait assez facile de trouver le code pour traduire une valeur 325467 bits (par exemple) dans un grand entier.

Bien sûr, vous pouvez stocker ce fichier comme un blob, mais je ne sais pas pourquoi vous dérange pas.

Answer 7

Tout dépend de quels types d'opérations que vous voulez faire avec les chiffres. Si juste stocker et recherche, puis il suffit d'utiliser des chaînes et utiliser une contrainte de vérification / domaine DataType veiller à leur nombre. Si vous voulez plus de contrôle, alors PostgreSQL vous permettra de définir types de données personnalisés et les fonctions. Vous pouvez par exemple l'interface avec la bibliothèque de l' GMP pour avoir correct commande et arithmétique des nombres entiers de précision arbitraire. En utilisant une telle bibliothèque vous permet même de mettre en œuvre une contrainte de vérification qui utilise le test de primalité probabiliste pour vérifier si les chiffres sont vraiment prime.

La vraie question est en fait de savoir si une base de données relationnelle est l'outil approprié pour le travail.

Answer 8

Je pense que vous êtes mieux à l'aide d'un blob. Comment les données sont stockées dans votre blob dépend de votre utilisation prévue des numéros. Si vous voulez les utiliser dans les calculs, je pense que vous aurez besoin de créer une classe ou de type pour stocker les valeurs de la variété de l'ordre valeur binaire et leur permettre d'être traités comme des numéros, etc. Si vous avez juste besoin de les afficher ensuite les stocker sous forme d'une séquence de caractères serait suffisante, et éliminerait la nécessité de convertir vos valeurs calculable à quelque chose affichable, ce qui peut prendre beaucoup de temps pour les grandes valeurs.

Partager et profiter.

Answer 9

Probablement pas génial, mais si vous les avez stockées dans une structure de données récursive. Vous pouvez stocker comme un entier, il est exposant, et une référence aux numéros de bits inférieurs.

Comme l'idée de chaîne, il ne serait probablement pas très bon pour des raisons de mémoire. Et le temps de requête serait augmentée en raison de la nature récursive de la requête.