Memorizzazione di grandi numeri primi in un database

Question

Questo problema mi ha colpito come un po 'strano. Sono curioso come si potrebbe rappresentare un elenco di numeri primi in una banca dati. Non so di un solo tipo di dati che sarebbe in grado di acuratly e costantemente memorizzare una grande quantità di numeri primi. La mia preoccupazione è che quando i numeri primi stanno iniziando a contenere 1000s di cifre, che potrebbe essere un po 'difficile fare riferimento formare il database. C'è un modo per rappresentare un grande insieme di numeri primi in un DB? Sono abbastanza sicuro che questo argomento ha è stato affrontato prima.

Una delle questioni su questo che rende difficile è che i numeri primi non possono essere suddivisi in fattori. Se potessero questo problema sarebbe molto più facile.

Answer 1

Se davvero si vuole memorizzare numeri primi come i numeri e una delle domande, fermandosi voi è "numeri primi non possono essere suddivisi in fattori", ci sono un'altra cosa: memorizzano nella lista di modulo di qualsiasi numero in ordine di sequenza.

Piccolo esempio:

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

List è:

81, 17, 83, 2

In un'applicazione reale è utile raggruppati per modulo 2 ^ 32 (interi a 32-bit), specialmente se i numeri primi in un'applicazione di elaborazione memorizzate come matrici di byte.

bagagli in 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;

inserire ad esempio sopra (1647 si solo per esempio):

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

valore prime_id può essere assegnato dalla sequenza oracle ...

create sequence seq_primes start with 1 increment by 1;

Ottenere ID del prossimo numero primo da inserire:

select seq_primes.nextval from dual;

selezionare il contenuto numero primo con id specificato:

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

Answer 2

Si poteva memorizzare come dati binari. Non saranno direttamente leggibile dal database, ma questo non dovrebbe essere un problema.

Answer 3

Database (a seconda di quale) può routine memorizzare numeri fino a 38-39 cifre precisione. Che si ottiene abbastanza lontano.

Al di là che non farà operazioni aritmetiche su di essi (accuratamente) in database (salvo moduli precisione arbitraria che possono esistere per il database particolare). Ma i numeri possono essere memorizzati come testo fino a diverse migliaia di cifre. Oltre a ciò è possibile utilizzare campi di tipo CLOB di immagazzinare milioni di cifre.

Inoltre, è da notare che se si sta memorizzare sequenze di numeri primi e il vostro interesse è nello spazio di compressione di tale sequenza si potrebbe iniziare memorizzando la differenza tra un numero e l'altro, piuttosto che l'intero numero.

Answer 4

Questo è un po 'inefficiente, ma li si può memorizzare come stringhe.

Answer 5

Se non si ha intenzione di utilizzare i calcoli di database-side con questi numeri, semplicemente memorizzarli come sequenze di bit della loro rappresentazione binaria (BLOB, VARBINARY ecc.)

Answer 6

Ecco i miei 2 centesimi vale la pena. Se si desidera memorizzare loro come i numeri in un database, allora sarete vincolati dalla dimensione massima del numero intero che il database in grado di gestire. si sarebbe probabilmente desidera una tabella 2 colonne, con il numero primo in una colonna e il suo numero di sequenza nell'altra. Allora che ci si vuole alcuni indici per rendere la ricerca dei valori memorizzati rapida.

Ma in realtà non vuole fare questo si, si desidera memorizzare humongous (sp?) Numeri primi ben oltre qualsiasi tipo di dati integer hai anche se ancora. E dici che siete contrari a corde in modo che sia i dati binari per voi. (Sarebbe anche per me.) Sì, li è possibile memorizzare in un BLOB in un database, ma che tipo di strutture si DBMS offrire per trovare il primo n-esimo o di controllo della primeness di un intero candidato?

Come progettare una struttura di file adatto? Questo è il meglio che ho potuto venire con dopo circa 5 minuti di pensiero:

1. Imposta un contatore a 2.
2. Scrivi i due bit che rappresentano il primo numero primo.
3. Scrivi di nuovo, per segnare la fine della sezione che contiene i numeri primi 2 bit.
4. Imposta il contatore per contrastare + 1
5. Scrivi i numeri primi 3 bit in ordine. (Penso che ci siano due: 5 e 7)
6. Scrivi l'ultimo dei 3-bit numeri primi di nuovo per contrassegnare la fine della sezione che contiene i numeri primi 3 bit.
7. Torna a 4 e proseguire per analogia.

Il punto di scrivere l'ultima n-bit prime due volte è quello di fornire un mezzo per identificare la fine della parte del file con numeri primi n bit in esso quando si arriva a leggere il file.

Come si scrive il file, probabilmente anche voler prendere nota degli spostamenti nei file in vari punti, forse l'inizio di ogni sezione contenente numeri primi n bit.

Credo che questo dovrebbe funzionare, e sarebbe gestire i numeri primi fino a 2 ^ (il più grande numero intero senza segno si può rappresentare). Credo che sarebbe stato abbastanza facile da trovare il codice per la traduzione di un valore di 325.467 bit (ad esempio) in un grande numero intero.

Certo, si potrebbe salvare questo file come un BLOB, ma non sono sicuro perché ci si preoccupa.

Answer 7

Tutto dipende da che tipo di operazioni che si vuole fare con i numeri. Se solo memorizzare e di ricerca, poi basta usare le stringhe e utilizzare un vincolo CHECK / dominio tipo di dati per far rispettare che sono i numeri. Se si desidera un maggiore controllo, allora PostgreSQL vi permetterà di definire tipi di dato personalizzati e funzioni. È possibile per l'interfaccia esempio con la biblioteca GMP avere ordinamento corretto e l'aritmetica per interi precisione arbitraria. Utilizzando tale libreria sarà anche permetterà di implementare un vincolo di controllo che utilizza il test di primalità probabilistico per verificare se i numeri sono davvero privilegiata.

La vera questione è in realtà se un database relazionale è lo strumento adatto per il lavoro.

Answer 8

Credo che si sta meglio fuori usando un BLOB. Come i dati vengono memorizzati nel BLOB dipende dalla vostra destinazione d'uso dei numeri. Se si desidera utilizzarli nei calcoli Credo che sarà necessario creare una classe o digitare per memorizzare i valori come una certa varietà di valore binario ordinata e permettere loro di essere trattati come numeri, ecc Se avete solo bisogno di visualizzarli poi la loro memorizzazione come una sequenza di caratteri sarebbe sufficiente, e eliminerebbe la necessità di convertire i vostri valori calcolabile a qualcosa visualizzabile, che può richiedere molto tempo per i valori di grandi dimensioni.

Condividere e godere.

Answer 9

Probabilmente non brillante, ma cosa succede se li è memorizzato in qualche struttura dati ricorsiva. Si potrebbe archiviare come un int, è esponente, e un riferimento ai numeri di bit inferiori.

Come l'idea di stringa, probabilmente non sarebbe molto buono per considerazioni di memoria. E tempo di risposta sarebbe aumentato a causa della natura ricorsiva della query.