Chức năng ghép nối cantor C++
|
Theo một cách thực dụng hơn, có thể cần phải mã hóa hai giá trị thành một cho mục đích nén dữ liệu hoặc khai thác một giao thức không cho phép gửi nhiều giá trị riêng biệt. Ví dụ, cách đơn giản nhất để ghép hai số nguyên là xen kẽ các bit của chúng với một số thứ như uint64_t pair(uint32_t x, uint32_t y)
{
int64_t p=0;
int i=0;
while (x||y)
{
p|= ((uint64_t)(x&1)<với nghịch đảo của nó void depair(uint64_t p, uint32_t & x, uint32_t & y)
{
x=0;
y=0;
int i=0;
while (p)
{
x|=((uint32_t)(p&1)<Tất nhiên, việc triển khai này chỉ hoạt động với các số nguyên cỡ máy. Ý tưởng xen kẽ các bit (hoặc chữ số) cho chức năng ghép nối không phải là mới—tôi nhớ đã đọc về phát minh của nó vào thế kỷ 19, nhưng tôi không thể nhớ tên của nhà toán học. Các loại chức năng ghép nối khác đã được đề xuất, và một chức năng đặc biệt thanh lịch—và không thực tế—được đề xuất bởi Gödel như một cách mã hóa các chương trình. Được gọi là Đánh số Gödel, sơ đồ sử dụng định lý cơ bản của số học để mã hóa các chuỗi thành một số duy nhất. Nghĩa là, đối với một chuỗi , số Gödel được cho bởi. Trong đó là số nguyên tố thứ . Vì nó có thể phân tích thành thừa số duy nhất—thật dễ dàng để chia một số cho hai cho đến khi chúng ta có số dư lẻ để tìm —mã có thể đảo ngược. Gödel đã giải quyết trường hợp tổng quát của mã hóa -bộ dữ liệu, nhưng chúng ta hãy quay lại các hàm ghép nối, đối với bộ dữ liệu 2 bộ, tức là bộ dữ liệu đơn giản. Chúng tôi sẽ có Lúc đầu, có vẻ như việc có một chức năng ghép nối dựa trên phân tích thừa số nguyên không phải là một ý tưởng hay bởi vì , nhưng trường hợp đặc biệt này mang lại một thuật toán đặc biệt hiệu quả. Trên thực tế, về cơ bản, chúng ta có thể phân tích số lượng theo các bước . Hãy suy nghĩ về nó trước khi bạn tiếp tục đọc * Vì số được mã hóa rất đơn giản, nó chỉ có hai thừa số riêng biệt là 2 và 3 nên độ phức tạp của việc tìm kiếm và được giảm đi rất nhiều. Một cách tiếp cận ngây thơ sẽ chia liên tiếp cho ba, cho phép bạn tìm , sau đó chia liên tiếp cho 2, cho phép bạn tìm , tạo ra một thuật toán về cơ bản trong steps (note that I am leaving the complexity of division out, to keep things simple, but you would have to include it were you to perform a complete analysis of the algorithm.) Nhưng, vì chúng ta đã biết các thừa số nguyên tố, chứ không phải bội số của chúng, nên chúng ta có thể quan sát thấy rằng nếu , đối với một số nguyên , thì < . Được rồi, điều đó có nghĩa là nếu phần dư của . OK, that means that if the remainder of bằng 0, thì chia hết và do đó , with possibly zero. This will allow us to find trong các bước. Bởi vì, nếu thì , chúng ta có thể bắt đầu bằng , rồi nhân đôi until , that is, is too large for it to be a solution. This mean that nằm đâu đó giữa và , cung cấp cho chúng tôi phạm vi chia đôi. Cả “giai đoạn phi nước đại” của việc nhân đôi liên tiếp và giai đoạn chia đôi đều được thực hiện trong . Sau khi có được , việc có được thật dễ dàng. bạn có thể làm điều tương tự. Hoặc sử dụng quy trình nhanh cho các số nguyên lớn. Cũng được thực hiện trong . Vì nó khá cồng kềnh để xử lý các số nguyên lớn trong C hoặc C++ (và đó là một cách nói nhẹ nhàng), chúng ta hãy đề xuất một triển khai Python def godel(x,y):
return (2**x)*(3**y)
def degodel_log(z):
x,y=0,0
## "galloping" phrase
lo_y=0
hi_y=1
while (z % 3**hi_y==0): lo_y=hi_y; hi_y*=2
# ok, we know it's somewhere lo_y<=y |
