El almacenamiento de grandes números primos en una base de datos

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

Pregunta

Este problema me pareció un poco extraño. Tengo curiosidad por cómo se podría representar una lista de números primos en una base de datos. No sé de un solo tipo de datos que sería capaz de almacenar acuratly y consistentemente una gran cantidad de números primos. Mi preocupación es que cuando los números primos están empezando a contener 1000 de dígitos, que podría ser un poco difícil de hacer referencia a formar la base de datos. ¿Hay una manera de representar un gran conjunto de números primos en una base de datos? Estoy seguro de que esto tiene tema ha sido abordado antes.

Una de las cuestiones sobre este que hace que sea difícil es que los números primos no pueden ser divididos en factores. Si pudieran este problema sería mucho más fácil.

¿Fue útil?

Solución

Si realmente desea almacenar los números primos como números y una de las preguntas, que te detiene es "números primos no pueden ser divididos en factores", no son otra cosa: lo almacenan en la lista de módulo de un número cualquiera ordenado por secuencia.

Pequeño ejemplo: 

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

lista es: 

81, 17, 83, 2

En aplicación real es útil para dividir por módulo de 2 ^ 32 (números enteros de 32 bits), especialmente si los números primos en aplicación de procesamiento almacenan como matrices de bytes.

Almacenamiento en 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;

insertar por ejemplo por encima (1647 es, por ejemplo solamente): 

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 se puede asignar a la secuencia de Oracle ... 

create sequence seq_primes start with 1 increment by 1;

Obtener ID del siguiente número primo para insertar: 

select seq_primes.nextval from dual;

seleccionar el contenido de los números primos con el id especificado: 

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

Otros consejos

Se puede almacenar como datos binarios. No serán directamente legible por humanos de la base de datos, pero eso no debería ser un problema.

Bases de datos (dependiendo de que) puede almacenar rutinariamente números hasta 38-39 dígitos con precisión. Eso te lleva bastante lejos.

Más allá de que no estará haciendo operaciones aritméticas sobre ellos (con precisión) en bases de datos (salvo módulos de precisión arbitraria que puedan existir para su base de datos particular). Pero los números pueden ser almacenados como texto hasta varios miles de dígitos. Más allá de que se puede utilizar campos de tipo CLOB para almacenar millones de dígitos.

Además, es destacable que si estás secuencias de números primos almacenamiento y su interés se centra en el espacio-compresión de esa secuencia se puede empezar almacenando la diferencia entre un número y el siguiente en lugar de toda la serie.

Esto es un poco ineficiente, pero se puede almacenar como cadenas.

Si no va a utilizar cálculos del lado de la base de datos con estos números, simplemente almacenarlos como secuencias de bits de su representación binaria (BLOB, VARBINARY etc.)

Esta es mi valor de 2 centavos. Si desea almacenar como números en una base de datos, entonces estará limitado por el tamaño máximo de la base de datos entero que puede manejar. Usted probablemente querrá una tabla de 2 columnas, con el número primo en una columna y es el número de secuencia en el otro. Entonces te gustaría algunos índices que facilitan la búsqueda de los valores almacenados rápida.

Pero usted realmente no quiere hacer eso es lo que, desea almacenar gigantescos (sp?) Primos mucho más allá de cualquier tipo de datos entero que has a pesar de todavía. Y se dice que son contrarios a las cadenas por lo que es datos binarios para usted. (Sería para mí también.) Sí, se puede almacenar en un BLOB en una base de datos, pero ¿qué tipo de instalaciones tendrá el DBMS que ofrecer para encontrar el primer enésima o control del primalidad de un número entero candidato?

¿Cómo diseñar una estructura de archivo adecuado? Esto es lo mejor que podía llegar a después de unos 5 minutos pensando:

  1. Establecer un contador de 2.
  2. Escribir los dos bits que representan el primer número primo.
  3. escribirlos de nuevo, para marcar el final de la sección que contiene los números primos 2 bits.
  4. poner el contador a contrarrestar + 1
  5. Escribe los números primos de 3 bits en orden. (Creo que hay dos: 5 y 7)
  6. Escribir el último de los 3 bits primos de nuevo para marcar el final de la sección que contiene los números primos 3 bits.
  7. Volver a 4 y continuar mutatis mutandis.

El punto de escribir los últimos n bits primer doble es para ofrecerle un medio para identificar el final de la parte del archivo con los números primos de n bits en que cuando se llega a leer el archivo.

A medida que escribe el archivo, es probable que también desee tomar nota de las compensaciones en los archivos en varios puntos, tal vez el comienzo de cada sección que contiene los números primos de n bits.

Creo que esto funcionaría, y que se ocuparía de los números primos hasta 2 ^ (el mayor entero sin signo puede representar). Supongo que sería bastante fácil de encontrar el código para la traducción de un valor de 325 467 bits (por ejemplo) en un gran número entero.

Claro, usted podría guardar este archivo como un BLOB, pero no estoy seguro de por qué te molestas.

Todo depende de qué tipo de operaciones que desea hacer con los números. Si acaba de almacenar y de búsqueda, a continuación, sólo tiene que utilizar cuerdas y utilizar una restricción de comprobación / Dominio tipo de datos para hacer cumplir que son números. Si desea más control, a continuación, PostgreSQL le permitirá definir tipos de datos personalizados y funciones. Se puede, por ejemplo, con la interfaz de biblioteca de la GMP tener orden correcto y la aritmética de enteros de precisión arbitraria. El uso de tal biblioteca, incluso le permitirá implementar una restricción de comprobación que utiliza el test de primalidad probabilísticos para comprobar si los números son realmente privilegiada.

La pregunta real es si una base de datos relacional es la herramienta correcta para el trabajo.

Creo que es el mejor de usar un BLOB. ¿Cómo se almacenan los datos en su BLOB depende de su uso previsto de los números. Si desea utilizarlos en los cálculos Creo que necesita para crear una clase o tipo para almacenar los valores como algunos variedad de valor binario ordenado y permitir que sean tratados como números, etc. Si sólo necesita para mostrarlos a continuación, almacenarlos como una secuencia de caracteres sería suficiente, y eliminaría la necesidad de convertir sus valores calculable a algo visualizable, que puede ser muy lento para valores grandes.

Compartir y disfrutar.

Probablemente no brillante, pero lo que si estuvieran almacenadas en alguna estructura de datos recursiva. Se podría almacenar como un int, es exponente, y una referencia a los números de bits más bajas.

Al igual que la idea de la cadena, es probable que no sea muy bueno para consideraciones de memoria. Y el tiempo de consulta se incrementaría debido a la naturaleza recursiva de la consulta.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top