Almacenamiento de números primos grandes en una base de datos

Question

Este problema me pareció un poco extraño. Tengo curiosidad de cómo podrías representar una lista de números primos en una base de datos. No conozco un solo tipo de datos que pueda almacenar de manera precisa y consistente una gran cantidad de números primos. Mi preocupación es que cuando los números primos comienzan a contener miles de dígitos, puede ser un poco difícil hacer referencia a la base de datos. ¿Hay alguna forma de representar un gran conjunto de números primos en un DB? Estoy bastante seguro de que este tema se ha abordado antes.

Uno de los problemas que dificulta esto es que los números primos no se pueden descomponer en factores. Si pudieran, este problema sería mucho más fácil.

Answer 1

Si realmente desea almacenar números primos como números y una de las preguntas, detenerlo es "los números primos no se pueden descomponer en factores", hay otra cosa: almacenarlo en la lista de módulos de cualquier número 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 que es útil para dividir por módulo de 2^32 (32-bits enteros), especialmente si los números primos en el procesamiento aplicación almacenada 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; 

inserto 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 partir de la secuencia de Oracle ...

create sequence seq_primes start with 1 increment by 1; 

Obtenga el ID del primer número primo a insertar:

select seq_primes.nextval from dual; 

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

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

Answer 2

Esto es un poco ineficiente, pero puede almacenarlos como cadenas.

Answer 3

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

Answer 4

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

Answer 5

Las bases de datos (dependiendo de cuál) pueden almacenar de manera rutinaria números de hasta 38-39 dígitos con precisión. Eso te lleva bastante lejos.

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

Además, no vale la pena que si está almacenando secuencias de números primos y su interés está en la compresión del espacio de esa secuencia, puede comenzar almacenando la diferencia entre un número y el siguiente en lugar del número entero.

Answer 6

Creo que es mejor que utilices un BLOB. Cómo se almacenan los datos en su BLOB depende de su uso previsto de los números. Si quieres usarlos en los cálculos, creo que necesitarás crear una clase o un tipo para almacenar los valores como una variedad de valores binarios ordenados y permitir que sean tratados como números, etc. Si solo necesitas mostrarlos, entonces almacenarlos como una secuencia de caracteres sería suficiente, y eliminaría la necesidad de convertir los valores calculables en algo visualizable, lo que puede consumir mucho tiempo para valores grandes.

Comparte y disfruta.

Answer 7

Probablemente no sea brillante, pero ¿qué ocurre si los almacenó en una estructura de datos recursiva? Puede almacenarlo como un int, es exponente y una referencia a los números de bit más bajos.

Al igual que la idea de cadena, probablemente no sería muy bueno para las consideraciones de memoria. Y el tiempo de consulta aumentaría debido a la naturaleza recursiva de la consulta.

Answer 8

Todo depende del tipo de operaciones que desee hacer con los números. Si solo almacena y busca, simplemente use cadenas y use una restricción de verificación/tipo de datos de dominio para hacer cumplir que son números. Si desea más control, PostgreSQL le permitirá definir custom datatypes y funciones. Por ejemplo, puede interactuar con la biblioteca GMP para tener pedidos correctos y aritmética para enteros de precisión arbitrarios. El uso de una biblioteca de este tipo incluso le permitirá implementar una restricción de verificación que usa la prueba de primalidad probabilística para verificar si los números son realmente primos.

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

Answer 9

Aquí está mi valor de 2 centavos. Si desea almacenarlos como números en una base de datos, se verá limitado por el tamaño máximo del número entero que su base de datos puede manejar. Probablemente quieras una tabla de 2 columnas, con el número primo en una columna y su número de secuencia en la otra. Entonces querrá algunos índices para hacer que los valores almacenados sean rápidos.

Pero realmente no quieres hacer eso, quieres almacenar primers humongous (sp?) Mucho más allá de cualquier tipo de datos entero que tengas aunque sea. Y dices que eres reacio a las cadenas así que son datos binarios para ti. (Sería para mí también.) Sí, podría almacenarlos en un BLOB en una base de datos, pero ¿qué tipo de instalaciones le ofrecerá el DBMS para encontrar el n-ésimo primo o verificar la excelencia de un entero candidato?

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

1. Establecer un contador a 2.
2. Escribir los dos bits que representan el primer número primo.
3. Escríbelos nuevamente para marcar el final de la sección que contiene los números primos de 2 bits.
4. Establezca el contador en el contador + 1
5. Escriba los primos de 3 bits en orden. (Creo que hay dos: 5 y 7)
6. Escriba el último de los primos de 3 bits nuevamente para marcar el final de la sección que contiene los números primos de 3 bits.
7. Regrese a 4 y continúe mutatis mutandis.

El objetivo de escribir el último n-bit prime dos veces es proporcionarle un medio para identificar el final de la parte del archivo con n-bit primes cuando llegue a leer el archivo.

Al escribir el archivo, probablemente también desee anotar los desplazamientos en los archivos en varios puntos, tal vez el comienzo de cada sección que contenga números primos de n bits.

Creo que esto funcionaría, y manejaría números primos hasta 2^(el número entero sin signo más grande que puede representar). Supongo que sería bastante fácil encontrar un código para traducir un valor de 325467 bits (digamos) en un entero grande.

Claro, podría guardar este archivo como BLOB, pero no estoy seguro de por qué se molestaría.