Lưu trữ số nguyên tố lớn trong cơ sở dữ liệu

Question

Sự cố này khiến tôi hơi kỳ quặc. Tôi tò mò làm thế nào bạn có thể đại diện cho một danh sách các số nguyên tố trong một cơ sở dữ liệu. Tôi không biết một kiểu dữ liệu đơn lẻ nào có thể lưu trữ một số lượng lớn các số nguyên tố. Mối quan tâm của tôi là khi các số nguyên tố bắt đầu chứa 1000 chữ số, có thể hơi khó để tham khảo biểu mẫu cơ sở dữ liệu. Có cách nào để đại diện cho một tập hợp lớn các số nguyên tố trong một DB? Tôi khá chắc chắn rằng chủ đề này đã được tiếp cận trước đây.

Một trong những vấn đề về điều này gây khó khăn là các số nguyên tố không thể được chia thành các yếu tố. Nếu họ có thể vấn đề này sẽ dễ dàng hơn nhiều.

Answer 1

Nếu bạn thực sự muốn lưu số nguyên tố và một trong các câu hỏi, hãy dừng bạn là "số nguyên tố không thể chia thành các yếu tố", có một điều khác: lưu trữ nó trong danh sách mô đun của bất kỳ số nào theo thứ tự .

ví dụ nhỏ:

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

Danh sách là:

81, 17, 83, 2 

Trong ứng dụng thực tế rất hữu ích để chia bởi mô đun của 2^32 (32-bit số nguyên), đặc biệt nếu số nguyên tố trong chế biến ứng dụng được lưu trữ dưới dạng mảng byte.

lưu trữ trong 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; 

chèn ví dụ trên (1647 là ví dụ duy nhất):

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

giá trị prime_id có thể được gán từ chuỗi oracle ...

create sequence seq_primes start with 1 increment by 1; 

Nhận ID số nguyên tố tiếp theo để chèn:

select seq_primes.nextval from dual; 

chọn nội dung số nguyên tố với id đã chỉ định:

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

Answer 2

Đây là một chút không hiệu quả, nhưng bạn có thể lưu trữ chúng dưới dạng chuỗi.

Answer 3

Nếu bạn đang không sử dụng các phép tính cơ sở dữ liệu-side với những con số này, chỉ cần lưu trữ chúng như chuỗi bit biểu diễn nhị phân của họ (BLOB, VARBINARY vv)

Answer 4

Bạn có thể lưu trữ chúng dưới dạng dữ liệu nhị phân. Chúng sẽ không thể đọc được trực tiếp từ cơ sở dữ liệu, nhưng đó không phải là vấn đề.

Answer 5

Cơ sở dữ liệu (tùy theo đó) có thể lưu trữ chính xác số lên tới 38-39 chữ số chính xác. Điều đó giúp bạn đạt được một cách hợp lý.

Ngoài ra bạn sẽ không thực hiện các phép toán số học trên chúng (chính xác) trong cơ sở dữ liệu (chặn các mô-đun chính xác tùy ý có thể tồn tại cho cơ sở dữ liệu cụ thể của bạn). Nhưng con số có thể được lưu trữ dưới dạng văn bản lên đến vài nghìn chữ số. Ngoài ra, bạn có thể sử dụng các trường loại CLOB để lưu trữ hàng triệu chữ số. Ngoài ra, nó không có giá trị gì nếu bạn đang lưu trữ chuỗi số nguyên tố và sở thích của bạn là nén không gian của chuỗi đó, bạn có thể bắt đầu bằng cách lưu trữ sự khác biệt giữa một số và số tiếp theo chứ không phải là số nguyên.

Answer 6

Tôi nghĩ bạn nên sử dụng BLOB. Cách dữ liệu được lưu trữ trong BLOB của bạn tùy thuộc vào mục đích sử dụng của bạn đối với các con số. Nếu bạn muốn sử dụng chúng trong tính toán, tôi nghĩ bạn sẽ cần phải tạo một lớp hoặc loại để lưu trữ các giá trị dưới dạng một số giá trị nhị phân đã đặt hàng và cho phép chúng được coi là số, v.v. Nếu bạn chỉ cần hiển thị chúng lưu trữ chúng như là một chuỗi các ký tự sẽ là đủ, và sẽ loại bỏ sự cần thiết phải chuyển đổi các giá trị tính toán của bạn thành một cái gì đó có thể hiển thị, có thể tốn rất nhiều thời gian cho các giá trị lớn.

Chia sẻ và thưởng thức.

Answer 7

Có lẽ không rực rỡ, nhưng nếu bạn lưu trữ chúng trong một số cấu trúc dữ liệu đệ quy. Bạn có thể lưu trữ nó như là một int, đó là số mũ, và một tham chiếu đến các số bit thấp hơn.

Giống như ý tưởng chuỗi, nó có thể sẽ không tốt cho những cân nhắc về bộ nhớ. Và thời gian truy vấn sẽ được tăng lên do tính chất đệ quy của truy vấn.

Answer 8

Tất cả phụ thuộc vào loại hoạt động bạn muốn thực hiện với các con số. Nếu chỉ lưu trữ và tra cứu, sau đó chỉ cần sử dụng chuỗi và sử dụng một ràng buộc kiểm tra/tên miền datatype để thực thi rằng chúng là số. Nếu bạn muốn kiểm soát nhiều hơn, sau đó PostgreSQL sẽ cho phép bạn xác định custom datatypes và chức năng. Bạn có thể giao diện ví dụ với thư viện GMP để có thứ tự chính xác và số học cho các số nguyên chính xác tùy ý. Sử dụng một thư viện như vậy thậm chí sẽ cho phép bạn thực hiện một ràng buộc kiểm tra sử dụng kiểm tra tính xác thực nguyên thủy để kiểm tra xem các số thực sự là số nguyên tố.

Câu hỏi thực sự là liệu cơ sở dữ liệu quan hệ có phải là công cụ chính xác cho công việc hay không.

Answer 9

Đây là giá trị 2 xu của tôi. Nếu bạn muốn lưu chúng dưới dạng các số trong cơ sở dữ liệu thì bạn sẽ bị hạn chế bởi kích thước tối đa của số nguyên mà cơ sở dữ liệu của bạn có thể xử lý. Bạn có thể muốn có một bảng 2 cột, với số nguyên tố trong một cột và số thứ tự của nó trong cột kia. Sau đó, bạn muốn một số chỉ mục để làm cho việc tìm kiếm các giá trị được lưu trữ nhanh chóng.

Nhưng bạn không thực sự muốn làm điều đó làm bạn, bạn muốn lưu trữ các số nguyên tố khổng lồ (sp?) Cách vượt quá bất kỳ kiểu dữ liệu nguyên nào mà bạn đã biết. Và bạn nói rằng bạn không thích hợp với chuỗi nên đó là dữ liệu nhị phân cho bạn. (Nó cũng dành cho tôi nữa.) Có, bạn có thể lưu trữ chúng trong một BLOB trong một cơ sở dữ liệu nhưng DBMS sẽ cung cấp cho bạn những gì để tìm kiếm nguyên tố thứ n hoặc kiểm tra độ nguyên của một số nguyên ứng cử viên?

Cách thiết kế cấu trúc tệp phù hợp? Đây là tốt nhất mà tôi có thể đưa ra sau khoảng 5 phút để nghĩ:

1. Đặt một bộ đếm đến 2.
2. Viết hai-bit đại diện cho số nguyên tố đầu tiên.
3. Viết lại, để đánh dấu phần cuối của phần chứa các số nguyên tố 2 bit.
4. Đặt bộ đếm để truy cập + 1
5. Viết số nguyên tố 3 bit theo thứ tự. (Tôi nghĩ có hai: 5 và 7)
6. Viết lại số nguyên tố 3 bit cuối cùng để đánh dấu phần cuối của phần chứa các số nguyên tố 3 bit.
7. Quay lại 4 và thực hiện các biện pháp thay thế miễn phí.

Điểm viết phần tử n bit cuối cùng hai lần là cung cấp cho bạn phương tiện để xác định phần cuối của tệp với số nguyên tố n bit trong đó khi bạn đọc tệp.

Khi bạn ghi tệp, bạn có thể cũng muốn ghi chú số dư vào các tệp tại các điểm khác nhau, có lẽ là bắt đầu của mỗi phần có chứa số nguyên tố n bit.

Tôi nghĩ rằng điều này sẽ làm việc và nó sẽ xử lý số nguyên tố lên đến 2^(số nguyên không dấu lớn nhất mà bạn có thể đại diện). Tôi đoán nó sẽ được dễ dàng, đủ để tìm mã cho dịch một giá trị 325467-bit (nói) thành một số nguyên lớn.

Chắc chắn, bạn có thể lưu trữ tệp này dưới dạng BLOB nhưng tôi không chắc chắn lý do bạn bận tâm.