首页 文章

基于数字基础系统的算法？ [关闭]

提问于
浏览 次
88

我最近注意到，基于创意基础中数字的巧妙使用，部分或全部有很多算法 . 例如：

  • 二项式堆基于二进制数，而更复杂的偏斜二项式堆基于偏差二进制数 .

  • 用于生成按字典顺序排列的排列的一些算法基于事实数字系统 .

  • 尝试可以被认为是一次查看字符串的一位数的树，用于适当的基础 .

  • 霍夫曼编码树被设计为使树中的每个边在一些二进制表示中编码为零或一 .
    999 Fibonacci编码用于Fibonacci搜索并反转某些类型的对数 .

我的问题是： what other algorithms are out there that use a clever number system as a key step of their intuition or proof? . 我正在考虑就这个问题进行一次谈话，所以我必须从中得到更多的例子 .

algorithm math data-structures numbers number-systems

16 回答

  • 3

    使用base 2的我最喜欢的一个是Arithmetic Encoding . 它不寻常，因为算法的哈特使用二进制中0到1之间的数字表示 .

    回复于
  • 7

    我最近遇到了一个很酷的算法，用于根据0到2n-1之间的数字的二进制表示来按字典顺序生成子集 . 它使用数字' bits both to determine what elements should be chosen for the set and to locally reorder the generated sets to get them into lexicographical order. If you'好奇，我有一个写的here .

    此外，许多算法都基于缩放（例如 . 的弱多项式版本）Ford-Fulkerson最大流算法），它使用输入问题中数字的二进制表示，逐步将粗略近似精简为完整解 .

    回复于
  • 5

    不完全是一个聪明的基础系统，但巧妙地使用了基本系统：Van der Corput序列是通过反转数字的base-n表示形成的 . 他们习惯于构建2-d Halton sequences，看起来有点像this .

    回复于
  • 6

    RadixSort可以使用各种数量的基础 . http://en.wikipedia.org/wiki/Radix_sort一个非常有趣的bucketSort实现 .

    回复于
  • 4

    我真的很喜欢这个将二进制数转换为格雷码：http://www.matrixlab-examples.com/gray-code.html

    回复于
  • 1

    我前几天读了你的问题，今天遇到了一个问题：如何生成一组的所有分区？我发现的解决方案，以及我使用的解决方案（可能是因为阅读了您的问题）是：

    对于具有（n）个元素的集合，我需要（p）分区，计算base（p）中的所有（n）个数字 .

    每个数字对应一个分区 . 每个数字对应于集合中的一个元素，数字的值告诉您将元素放入哪个分区 .

    这并不奇怪，但它很整洁 . 它完整，没有冗余，并使用任意基础 . 您使用的基础取决于特定的分区问题 .

    回复于
  • 39

    Exponentiation by squaring基于指数的二进制表示 .

    回复于
  • 4

    Chris Okasaki在他的“Purely Functional Data Structures”一书中有一篇非常好的章节，讨论了"Numerical Representations"：基本上，对数字进行一些表示并将其转换为数据结构 . 为了给出一种味道，以下是该章的部分内容：

    • 位置编号系统

    • 二进制数字（二进制随机访问列表，无零表示，惰性表示，分段表示）

    • 偏斜二进制数（偏斜二进制随机访问列表，偏斜二项积分）

    • 三元数和四元数

    一些最好的技巧，蒸馏：

    • 区分数字的密集和稀疏表示（通常你会在矩阵或图表中看到它，但它也适用于数字！）

    • 冗余数字系统（具有多个数字表示的系统）非常有用 .

    • 如果将第一个数字排列为非零或使用无零表示，则检索数据结构的头部可能很有效 .

    • 通过分割数据结构，避免级联借用（从列表尾部开始）并进行（从列表中获取）

    这是该章的参考列表：

    • Guibas，McCreight，Plass和Roberts：线性列表的新表示 .

    • Myers：一个应用随机访问堆栈

    • Carlsson，Munro，Poblete：具有恒定插入时间的隐式二项式队列 .

    • Kaplan，Tarjan：纯粹的功能列表，通过递归减速来进行连接 .

    回复于
  • 3

    密码学广泛使用整数环（模块化算术）和有限域，其操作直观地基于具有整数系数的多项式的行为 .

    回复于
  • 0

    在 Hackers Delight （每个程序员应该知道的一本书）中有一个完整的章节关于不可靠的基础，如-2作为基础（是，右基础）或-1 i（我作为假想单位sqrt（-1））as基础 . 另外，我很好地计算出最好的基础是什么（就硬件设计而言，对于所有不想阅读它的人来说：等式的解决方案是e，所以你可以选择2或3，3会更好一点（因素）比2）好1.056倍 - 但技术更实用） .

    我想到的其他事情是灰色计数器（当你在这个系统中只计算1位变化时，你经常在硬件设计中使用这个属性来减少亚稳态问题）或者已经提到的霍夫曼编码的泛化 - 算术编码 .

    回复于
  • 20

    可能是AKS就是这样 .

    回复于
  • 6

    “三元数可以用来传达自我相似的结构，如Sierpinski Triangle或Cantor set . ”来源“第四纪数字用于表示二维希尔伯特曲线 . ”源于“Drange Knuth于1955年首次提出了一个四分之一 - 虚数系统，提交给一个高中科学人才搜索 . 它是一个非标准的位置数字系统，以虚数2i为基础 . 它是能够仅使用数字0,1,2和3来表示每个复数 . “来源“罗马数字是一个两性系统 . ”来源“Senary可能被认为对质数的研究很有用，因为所有素数，当用基数6表示时，除了2和3之外，有1或5作为最终数字 . ”来源“Sexagesimal（base 60）是一个以六十为基础的数字系统 . 它起源于公元前三千年的古代苏美尔人，它被传递给古代的巴比伦人，并且仍然以一种修改的形式使用 - 测量时间，角度和角度的地理坐标 . “资源

    等等...

    This list是一个很好的起点 .

    回复于
  • 5

    散列字符串（例如在Rabin-Karp算法中）通常将字符串评估为由n个数字组成的base-b数字（其中n是字符串的长度，b是一些足够大的选定基数） . 例如，字符串"ABCD"可以散列为：

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

    将ASCII值替换为字符并将b替换为256，

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

    但是，在大多数实际应用中，所得到的值是以一些合理大小的数量为模，以保持结果足够小 .

    回复于
  • 5

    好问题 . 名单确实很长 . 告诉时间是混合基数的简单实例（天|小时|分钟|秒|上午/下午）

    如果您有兴趣了解它，我已经创建了一个元基础枚举n元组框架 . 对于基本编号系统来说，这是一种非常甜的语法糖 . 它尚未发布 . 通过电子邮件发送我的用户名（在Gmail） .

    回复于
  • 1

    我依稀记得一些关于加速某些矩阵乘法的双基系统 .

    双基系统是一个冗余系统，它使用两个基数作为一个数字 .

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

    冗余意味着可以通过多种方式指定一个数字 .

    您可以通过Vassil Dimitrov，Todor Cooklev查找文章“计算矩阵多项式的混合算法” .

    我试图给出最好的简短概述 .

    他们试图计算矩阵多项式 G(N,A) = I + A + ... + A^{N-1} .

    Supoosing 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

    因为它是"obvious"（开玩笑地说）这些方程中的一些在第一个系统中很快而在第二个系统中更好 - 所以根据 N 选择最好的方程是个好主意 . 但是这需要对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

    请查看文章以获得更好的解释，因为我不是这方面的专家 .

    回复于
  • 9

    here is a good post关于使用三元数来解决"counterfeit coin"问题（你必须在普通的一包中检测一个假币，使用尽可能少的余额）

    回复于

相关问题