基于数字基础系统的algorithm？
我最近注意到，有很多algorithm在部分或全部基于数字在创意基础上的巧妙使用。 例如：
- 二项堆是基于二进制数的，而更复杂的二项二项堆是基于二进制数的偏斜。
- 一些用于产生字典顺序排列的algorithm基于事实数字系统。
- 尝试可以被认为是树木，每次看一个string的数字，为适当的基础。
- 霍夫曼编码树被devise为使得树中的每个边在一些二进制表示中编码零或一。
- 斐波那契编码被用于斐波纳契search并且反转某些types的对数。
我的问题是： 还有哪些其他algorithm使用一个聪明的数字系统作为直觉或certificate的关键步骤？ 。 我正在考虑围绕这个问题进行一个讨论，所以我必须得到的例子越多越好。
Chris Okasaki在他的着作“ Purely Functional Data Structures”中讨论了“数值表示”一书中的一个非常好的章节：本质上，对数字进行一些表示并将其转换为数据结构。 给一个风味，这个章节的部分：
- 位置号码系统
- 二进制数（二进制随机访问列表，无零表示，延迟表示，分段表示）
- 偏斜二进制数（偏斜二进制随机访问列表，偏斜二项堆）
- 三位和第四数字
一些最好的技巧，蒸馏：
- 区分数字的稠密和稀疏表示（通常您可以在matrix或graphics中看到这一点，但它也适用于数字！）
- 冗余号码系统（具有多个号码表示的系统）是有用的。
- 如果您将第一个数字设置为非零或使用无零表示，则检索数据结构的头部可能会很有效。
- 避免级联借入（从列表的尾部开始），并通过分割数据结构来携带（从列入列表）
这也是该章的参考清单：
- Guibas，McCreight，Plass和Roberts：线性列表的新表示。
- 迈尔斯：一个应用随机访问栈
- Carlsson，Munro，Poblete：具有恒定插入时间的隐式二项式队列。
- Kaplan，Tarjan：纯粹function性的列表，通过recursion减速来链接。
“三元数字可以用来传达像Sierpinski Triangle或Cantor这样的自相似结构。” 资源
“二维希尔伯特曲线的表示中使用了四元数。” 资源
“四位数的虚拟数字系统最早是由Donald Knuth于1955年提出的，在高中科学人才搜寻的提交中，是以虚数2i为基数的非标准位置数字系统，以仅使用数字0,1,2和3来表示每个复数。“ 资源
“罗马数字是一个biquinary系统。” 资源
“在研究素数时，Senary可能被认为是有用的，因为所有的素数都以6为底，2和3除1或5为最后一位。 资源
“六十一行”（60世纪）是一个以六十为基数的数字系统，起源于公元前三千年代的古代苏美尔人，它被传给了古代巴比伦人，并且仍然用于修改forms时间，angular度和angular度的地理坐标。 资源
等等…
这份清单是一个很好的起点。
那天我读了你的问题，今天遇到了一个问题：我怎样才能生成一个集合的所有分区？ 我遇到的解决scheme，我使用（也许是因为读你的问题）是这样的：
对于具有（n）个元素的集合，我需要（p）个分区，通过基数（p）中的所有（n）个数字计数。
每个数字对应一个分区。 每个数字对应于该集合中的一个元素，并且该数字的值告诉您将该元素放入哪个分区。
这不是很了不起，但很整齐。 这是完整的，不会造成冗余，并使用任意的基础。 您使用的基础取决于具体的分区问题。
我最近遇到了一个很酷的algorithm，用于根据0到2 n – 1之间数字的二进制表示forms生成子集。它使用数字的位来确定应该为集合select哪些元素，并在本地重新sorting生成的集合将它们按照字典顺序排列。 如果你好奇，我在这里张贴一个文章。
此外，许多algorithm都是基于比例缩放（例如Ford-Fulkerson最大streamalgorithm的弱多项式版本），该algorithm使用input问题中数字的二进制表示forms逐步完善粗略近似为完整的解决scheme。
不完全是一个聪明的基本系统，而是巧妙地使用基本系统： Van der Corput序列是通过反转数字的基-n表示形成的低差异序列 。 它们被用来构造2-d Halton序列 ，看起来就像这样 。
我隐约记得一些关于加速某些matrix乘法的双基系统。
双基座系统是一个冗余系统，使用一个数字的两个基地。
n = Sum(i=1 --> l){ c_i * 2^{a_i} * 3 ^ {b_i}, where c in {-1,1}
冗余意味着可以用多种方式指定一个数字。
您可以查看Vodil Dimitrov，Todor Cooklev撰写的文章“matrix多项式计算的混合algorithm”（Hybrid Algorithm for the Computation of the Matrix Polynomial）。
试着给我最好的简短的概述，我可以。
他们试图计算matrix多项式G(N,A) = I + A + ... + A^{N-1} 。
假设N G(N,A) = G(J,A) * G(K, A^J) ，如果我们申请J = 2，得到：
/ (I + A) * G(K, A^2) , if N = 2K G(N,A) = | \ I + (A + A^2) * G(K, A^2) , if N = 2K + 1
也，
/ (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
由于“明显”（开玩笑），这些方程中的一些在第一个系统中是快速的，而在第二个系统中则好一些 – 因此根据Nselect最好的scheme是个好主意。 但是这需要2和3的快速模运算。这就是为什么双基的原因 – 你基本上可以快速地对它们进行模运算，为它们提供一个组合系统：
/ (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
因为我不是这个领域的专家，所以请看这篇文章以获得更好的解释。
RadixSort可以使用不同的编号。 http://en.wikipedia.org/wiki/Radix_sort相当有趣的实现一个bucketSort。;
这里有一个利用三元数字来解决“假币”问题的好post （你必须在一袋普通的硬币中检测一个假币，尽可能less地使用天平）
散列string（例如在Rabin-Karpalgorithm中）经常将string评估为由n个数字组成的基本b数字（其中n是string的长度，b是一些足够大的选定基数）。 例如，string“ABCD”可以被散列为：
'A'*b^3+'B'*b^2+'C'*b^1+'D'*b^0
将ASCII值replace为字符并将b取为256，
65*256^3+66*256^2+67*256^1+68*256^0
尽pipe在大多数实际应用中，所产生的值是以某种合理大小的数字为模数来保持足够小的结果。
平方的幂运算是基于指数的二进制表示。
在Hackers Delight （每个程序员都应该知道的书）中，有一个关于非常规基础的完整章节，比如-2作为base（yea，right negative bases）或者-1 + i（我作为sqrt（-1） ）为基地。 此外，我很好的计算什么是最好的基础（在硬件devise方面，所有谁不想读它：方程的解决scheme是e，所以你可以去2或3，3会好一点（因素比2好1.056倍），但技术更实用）。
其他我想到的东西是灰色计数器（当你在这个系统中只有1位变化时，你经常在硬件devise中使用这个属性来减less亚稳态问题）或者已经提到的Huffmann编码的一般化 – 算术编码。
密码学广泛使用整数环（模块化算术）和有限域，其操作直观地基于具有整数系数的多项式performance。
我真的很喜欢这个转换二进制数字格雷码： http : //www.matrixlab-examples.com/gray-code.html
伟大的问题。 名单确实很长。 告诉时间是混合基数的一个简单实例（天/小时/分钟/秒|上午/下午）
我已经创build了一个元基枚举n元组框架，如果你有兴趣听到它。 对于基数编号系统来说，这是一些非常甜蜜的语法糖。 它还没有发布。 通过电子邮件发送我的用户名（在Gmail）。
我最喜欢使用基数2的算术编码 。 它不寻常，因为该algorithm的哈特使用二进制0到1之间的数字表示。
可能是AKS是这样的。
