Algoritma berdasarkan sistem basis bilangan? [Tutup]

Saya baru-baru ini memperhatikan bahwa ada banyak algoritma di luar sana yang sebagian atau seluruhnya didasarkan pada penggunaan angka yang cerdik dalam basis kreatif. Sebagai contoh:

• Heap binomial didasarkan pada bilangan biner, dan heap binomial skew yang lebih kompleks didasarkan pada bilangan biner skew.
• Beberapa algoritme untuk menghasilkan permutasi yang diurutkan secara leksikografis didasarkan pada sistem bilangan faktorad.
• Percobaan dapat dianggap sebagai pohon yang melihat satu digit string pada satu waktu, untuk basis yang sesuai.
• Pohon pengkodean Huffman dirancang agar setiap tepi di pohon menyandikan nol atau satu dalam beberapa representasi biner.
• Pengkodean Fibonacci digunakan dalam pencarian Fibonacci dan untuk membalikkan jenis logaritma tertentu.

Pertanyaan saya adalah: algoritma lain apa yang ada di luar sana yang menggunakan sistem bilangan pintar sebagai langkah kunci dari intuisi atau pembuktian mereka? . Saya berpikir untuk membuat pembicaraan tentang subjek, jadi semakin banyak contoh yang harus saya ambil, semakin baik.

Chris Okasaki memiliki bab yang sangat bagus dalam bukunya Purely Functional Data Structures yang membahas "Representasi Numerik": pada dasarnya, mengambil beberapa representasi angka dan mengubahnya menjadi struktur data. Untuk memberi rasa, berikut adalah bagian dari bab itu:

1. Sistem Bilangan Posisi
2. Bilangan Biner (Daftar Akses Acak Biner, Representasi Zeroless, Representasi Malas, Representasi Segmented)
3. Bilangan Biner Skew (Daftar Akses Acak Biner Skew, Heap Binomial Skew)
4. Bilangan Triner dan Kuarter

Beberapa trik terbaik, saring:

• Bedakan antara representasi bilangan padat dan renggang (biasanya Anda melihat ini dalam matriks atau grafik, tetapi ini juga berlaku untuk bilangan!)
• Sistem bilangan redundan (sistem yang memiliki lebih dari satu representasi bilangan) berguna.
• Jika Anda menyusun digit pertama menjadi bukan nol atau menggunakan representasi nol, mengambil kepala struktur data dapat menjadi efisien.
• Borrows Hindari Cascading (dari mengambil ekor daftar) dan membawa (dari consing ke daftar) oleh segmentasi struktur data

Berikut juga daftar referensi untuk bab tersebut:

• Guibas, McCreight, Plass dan Roberts: Representasi baru untuk daftar linier.
• Myers: Tumpukan akses acak aplikatif
• Carlsson, Munro, Poblete: Antrian binomial implisit dengan waktu penyisipan konstan.
• Kaplan, Tarjan: Daftar fungsional murni dengan catenation melalui perlambatan rekursif.

"Bilangan terner dapat digunakan untuk menyampaikan struktur yang mirip dengan dirinya sendiri seperti Segitiga Sierpinski atau rangkaian Cantor dengan mudah." sumber

"Bilangan kuarter digunakan dalam representasi kurva Hilbert 2D." sumber

"Sistem angka imajiner-kuater pertama kali diusulkan oleh Donald Knuth pada tahun 1955, dalam pengajuan ke pencarian bakat sains sekolah menengah. Ini adalah sistem angka posisi non-standar yang menggunakan angka imajiner 2i sebagai dasarnya. Sistem ini mampu. untuk merepresentasikan setiap bilangan kompleks hanya dengan menggunakan angka 0, 1, 2, dan 3. " sumber

"Angka Romawi adalah sistem biquinary." sumber

"Senari dapat dianggap berguna dalam mempelajari bilangan prima karena semua bilangan prima, jika dinyatakan dalam basis enam, selain 2 dan 3 memiliki 1 atau 5 sebagai digit terakhir." sumber

"Sexagesimal (basis 60) adalah sistem angka dengan enam puluh sebagai basisnya. Ini berasal dari bangsa Sumeria kuno pada milenium ke-3 SM, diturunkan ke Babilonia kuno, dan masih digunakan - dalam bentuk yang dimodifikasi - untuk mengukur waktu, sudut, dan koordinat geografis yang merupakan sudut. " sumber

dll ...

Daftar ini adalah titik awal yang baik.

Saya membaca pertanyaan Anda beberapa hari yang lalu, dan hari ini dihadapkan pada masalah: Bagaimana cara membuat semua partisi dari satu set? Solusi yang terpikir oleh saya, dan yang saya gunakan (mungkin karena membaca pertanyaan Anda) adalah ini:

Untuk himpunan dengan elemen (n), di mana saya membutuhkan (p) partisi, hitung semua (n) digit angka dalam basis (p).

Setiap nomor sesuai dengan partisi. Setiap digit sesuai dengan elemen dalam himpunan, dan nilai digit memberi tahu Anda di partisi mana elemen tersebut akan ditempatkan.

Ini tidak luar biasa, tapi rapi. Itu lengkap, tidak menyebabkan redundansi, dan menggunakan basis sewenang-wenang. Basis yang Anda gunakan tergantung pada masalah partisi tertentu.

Baru-baru ini saya menemukan algoritme keren untuk menghasilkan subset dalam urutan leksikografis berdasarkan representasi biner dari angka antara 0 dan 2 ⁿ - 1. Ini menggunakan bit angka untuk menentukan elemen apa yang harus dipilih untuk himpunan dan untuk menyusun ulang secara lokal set yang dihasilkan untuk membuatnya menjadi urutan leksikografis. Jika Anda penasaran, saya memiliki artikel yang diposting di sini .

Selain itu, banyak algoritme didasarkan pada penskalaan (seperti versi polinomial lemah dari algoritme aliran maks Ford-Fulkerson), yang menggunakan representasi biner dari angka-angka dalam masalah masukan untuk secara progresif menyempurnakan perkiraan kasar menjadi solusi lengkap.

Bukan sistem dasar yang cerdas tetapi penggunaan sistem dasar yang cerdas: Urutan Van der Corput adalah urutan ketidaksesuaian rendah yang dibentuk dengan membalik representasi bilangan berbasis n. Mereka digunakan untuk membuat urutan Halton 2-d yang terlihat seperti ini .

Saya samar-samar mengingat sesuatu tentang sistem basis ganda untuk mempercepat beberapa perkalian matriks.

Sistem basis ganda adalah sistem redundan yang menggunakan dua basis untuk satu angka.

 n = Sum(i=1 --> l){ c_i * 2^{a_i} * 3 ^ {b_i}, where c in {-1,1}

Redundan berarti satu angka dapat ditentukan dengan banyak cara.

Anda dapat mencari artikel "Algoritme Hibrid untuk Perhitungan Polinomial Matriks" oleh Vassil Dimitrov, Todor Cooklev.

Mencoba memberikan gambaran singkat terbaik yang saya bisa.

Mereka mencoba menghitung matriks polinomial G(N,A) = I + A + ... + A^{N-1} .

Misalkan N adalah komposit G(N,A) = G(J,A) * G(K, A^J), jika kita menerapkan J = 2, kita dapatkan:

         / (I + A) * G(K, A^2)        , if N = 2K
G(N,A) = |
         \ I + (A + A^2) * G(K, A^2)  , if N = 2K + 1

juga,

         / (I + A + A^2) * G(K, A^3)           , if N = 3K
G(N,A) = | I + (A + A^2 + A^3) * G(K, A^3)     , if N = 3K + 1
         \ I + A * (A + A^2 + A^3) * G(K, A^3) , if N = 3K + 2

Karena "jelas" (bercanda) bahwa beberapa persamaan ini cepat di sistem pertama dan beberapa lebih baik di sistem kedua - jadi sebaiknya pilih yang terbaik dari yang bergantung N. Tetapi ini akan membutuhkan operasi modulo yang cepat untuk 2 dan 3. Inilah mengapa basis ganda masuk - pada dasarnya Anda dapat melakukan operasi modulo dengan cepat karena keduanya memberi Anda sistem gabungan:

         / (I + A + A^2) * G(K, A^3)       , if N = 0 or 3 mod 6
G(N,A) = | I + (A + A^2 + A^3) * G(K, A^3) , if N = 1 or 4 mod 6
         | (I + A) * G(3K + 1, A^2)        , if N = 2 mod 6
         \ I + (A + A^2) * G(3K + 2, A^2)  , if N = 5 mod 6

Lihat artikel untuk penjelasan yang lebih baik karena saya bukan ahli di bidang ini.

RadixSort dapat menggunakan berbagai basis angka. http://en.wikipedia.org/wiki/Radix_sort Implementasi bucketSort yang cukup menarik.

berikut adalah posting yang bagus tentang menggunakan nomor terner untuk memecahkan masalah "koin palsu" (di mana Anda harus mendeteksi satu koin palsu dalam kantong yang biasa, menggunakan saldo sesedikit mungkin)

String hashing (misalnya dalam algoritma Rabin-Karp ) sering mengevaluasi string sebagai bilangan basis-b yang terdiri dari n digit (di mana n adalah panjang string, dan b adalah beberapa basis terpilih yang cukup besar). Misalnya string "ABCD" dapat di-hash sebagai:

'A'*b^3+'B'*b^2+'C'*b^1+'D'*b^0

Mengganti nilai ASCII untuk karakter dan menganggap b 256 ini menjadi,

65*256^3+66*256^2+67*256^1+68*256^0

Padahal, dalam sebagian besar aplikasi praktis, nilai yang dihasilkan diambil modulo beberapa angka berukuran wajar untuk menjaga hasilnya cukup kecil.

Eksponensial dengan kuadrat didasarkan pada representasi biner dari eksponen.

Di Hackers Delight (buku yang harus diketahui setiap programmer di mata saya) ada bab lengkap tentang basis yang tidak biasa, seperti -2 sebagai basis (ya, basis negatif kanan) atau -1 + i (i sebagai unit imajiner sqrt (-1)) sebagai mendasarkan. Saya juga menghitung dengan baik apa basis terbaik (dalam hal desain perangkat keras, untuk semua yang tidak ingin membacanya: Solusi persamaannya adalah e, ​​jadi Anda dapat menggunakan 2 atau 3, 3 akan sedikit lebih baik (faktor 1,056 kali lebih baik dari 2) - tetapi secara teknis lebih praktis).

Hal lain yang muncul di benak saya adalah penghitung abu-abu (Anda ketika Anda menghitung dalam sistem ini hanya perubahan 1 bit, Anda sering menggunakan properti ini dalam desain perangkat keras untuk mengurangi masalah metastabilitas) atau generalisasi pengkodean Huffmann yang telah disebutkan - pengkodean aritmatika.

Kriptografi menggunakan banyak cincin bilangan bulat (aritmatika modular) dan juga bidang terbatas, yang operasinya secara intuitif didasarkan pada cara polinomial dengan koefisien bilangan bulat berperilaku.

Saya sangat suka yang satu ini untuk mengubah bilangan biner menjadi kode Gray: http://www.matrixlab-examples.com/gray-code.html

Pertanyaan bagus. Daftarnya memang panjang. Menceritakan waktu adalah contoh sederhana dari basis campuran (hari | jam | menit | detik | am / pm)

Saya telah membuat kerangka kerja n-tuple enumerasi meta-base jika Anda tertarik untuk mendengarnya. Ini adalah gula sintaksis yang sangat manis untuk sistem penomoran dasar. Ini belum dirilis. Email nama pengguna saya (di gmail).

Salah satu favorit saya menggunakan basis 2 adalah Enkode Aritmatika . Ini tidak biasa karena hart dari algoritme menggunakan representasi angka antara 0 dan 1 dalam biner.

Mungkin AKS memang demikian.