Storing large prime numbers in a database

Question

This problem struck me as a bit odd. I'm curious how you could represent a list of prime numbers in a database. I do not know of a single datatype that would be able to acuratly and consistently store a large amount of prime numbers. My concern is that when the prime numbers are starting to contain 1000s of digits, that it might be a bit difficult to reference form the database. Is there a way to represent a large set of primes in a DB? I'm quite sure that this has topic has been approached before.

One of the issues about this that makes it difficult is that prime numbers can not be broken down into factors. If they could this problem would be much easier.

Answer 1

This is a bit inefficient, but you could store them as strings.

Answer 2

If you are not going to use database-side calculations with these numbers, just store them as bit sequences of their binary representation (BLOB, VARBINARY etc.)

Answer 3

You could store them as binary data. They won't be human readable straight from the database, but that shouldn't be a problem.

Answer 4

Databases (depending on which) can routinely store numbers up to 38-39 digits accurately. That gets you reasonably far.

Beyond that you won't be doing arithmetic operations on them (accurately) in databases (barring arbitrary-precision modules that may exist for your particular database). But numbers can be stored as text up to several thousand digits. Beyond that you can use CLOB type fields to store millions of digits.

Also, it's worth nothing that if you're storing sequences of prime numbers and your interest is in space-compression of that sequence you could start by storing the difference between one number and the next rather than the whole number.

Answer 5

I think you're best off using a BLOB. How the data is stored in your BLOB depends on your intended use of the numbers. If you want to use them in calculations I think you'll need to create a class or type to store the values as some variety of ordered binary value and allow them to be treated as numbers, etc. If you just need to display them then storing them as a sequence of characters would be sufficient, and would eliminate the need to convert your calculatable values to something displayable, which can be very time consuming for large values.

Share and enjoy.

Answer 6

Probably not brilliant, but what if you stored them in some recursive data structure. You could store it as an int, it's exponent, and a reference to the lower bit numbers.

Like the string idea, it probably wouldn't be very good for memory considerations. And query time would be increased due to the recursive nature of the query.

Answer 7

It all depends on what kinds of operations you want to do with the numbers. If just store and lookup, then just use strings and use a check constraint / domain datatype to enforce that they are numbers. If you want more control, then PostgreSQL will let you define custom datatypes and functions. You can for instance interface with the GMP library to have correct ordering and arithmetic for arbitrary precision integers. Using such a library will even let you implement a check constraint that uses the probabilistic primality test to check if the numbers really are prime.

The real question is actually whether a relational database is the correct tool for the job.

Answer 8

Hi

Here's my 2 cents worth. If you want to store them as numbers in a database then you'll be constrained by the maximum size of integer that your database can handle. You'd probably want a 2 column table, with the prime number in one column and it's sequence number in the other. Then you'd want some indexes to make finding the stored values quick.

But you don't really want to do that do you, you want to store humongous (sp?) primes way beyond any integer datatype you've even though of yet. And you say that you are averse to strings so it's binary data for you. (It would be for me too.) Yes, you could store them in a BLOB in a database but what sort of facilities will the DBMS offer you for finding the n-th prime or checking the primeness of a candidate integer ?

How to design a suitable file structure ? This is the best I could come up with after about 5 minutes thinking:

1 Set a counter to 2.
2 Write the two-bits which represent the first prime number.
3 Write them again, to mark the end of the section containing the 2-bit primes.
4 Set the counter to counter+1
5 Write the 3-bit primes in order. ( I think there are two: 5 and 7)
6 Write the last of the 3-bit primes again to mark the end of the section containing the 3-bit primes.
7 Go back to 4 and carry on mutatis mutandis.

The point about writing the last n-bit prime twice is to provide you with a means to identify the end of the part of the file with n-bit primes in it when you come to read the file.

As you write the file, you'll probably also want to make note of the offsets into the files at various points, perhaps the start of each section containing n-bit primes.

I think this would work, and it would handle primes up to 2^(the largest unsigned integer you can represent). I guess it would be easy enough to find code for translating a 325467-bit (say) value into a big integer.

Sure, you could store this file as a BLOB but I'm not sure why you'd bother.

Regards

Mark

Answer 9

If you really want to store primes as numbers and one of questions, stopping you is "prime numbers can not be broken down into factors", there are another thing: store it in list of modulus of any number ordered by sequence.

Small example:

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

List is:

81, 17, 83, 2

In real application is useful to split by modulus of 2^32 (32-bits integers), specially if prime numbers in processing application stored as byte arrays.

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

insert for example above (1647 is for example only):

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 value can be assigned from oracle sequence ...

create sequence seq_primes start with 1 increment by 1;

Get ID of next prime number to insert:

select seq_primes.nextval from dual;

select prime number content with specified id:

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