当前位置： 文江博客话题详情

基于数基系统的算法？

发布于 2024-10-22 18:16:07 字数 346 浏览 6 评论 0原文

我最近注意到有很多算法部分或全部基于在创造性基础上巧妙地使用数字。例如：

  • 二项式堆基于二进制数，更复杂的倾斜二项式堆基于倾斜二进制数。
  • 一些用于生成按字典顺序排序的排列的算法基于因子数系统。
  • 尝试可以被认为是一次查看字符串的一位数字以获取适当基数的树。
  • 霍夫曼编码树被设计为让树中的每条边以某种二进制表示形式编码零或一。
  • 斐波那契编码用于斐波那契搜索和反转某些类型的对数。

我的问题是：还有哪些其他算法使用巧妙的数字系统作为其直觉或证明的关键步骤？。我正在考虑就这个主题进行一次演讲，因此我必须引用的例子越多越好。

原文

I've noticed recently that there are a great many algorithms out there based in part or in whole on clever uses of numbers in creative bases. For example:

  • Binomial heaps are based on binary numbers, and the more complex skew binomial heaps are based on skew binary numbers.
  • Some algorithms for generating lexicographically ordered permutations are based on the factoradic number system.
  • Tries can be thought of as trees that look at one digit of the string at a time, for an appropriate base.
  • Huffman encoding trees are designed to have each edge in the tree encode a zero or one in some binary representation.
  • Fibonacci coding is used in Fibonacci search and to invert certain types of logarithms.

My question is: what other algorithms are out there that use a clever number system as a key step of their intuition or proof?. I'm thinking about putting together a talk on the subject, so the more examples I have to draw from, the better.

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（16）

本王不退位尔等都是臣 2024-10-29 18:16:07

Chris Okasaki 在他的《纯函数式数据结构》一书中有一章非常精彩的章节讨论了“数值表示”：本质上是采用数字的某种表示形式并将其转换为数据结构。为了让大家了解一下该章的各个部分：

  1. 位置数系统
  2. 二进制数（二进制随机访问列表、无零表示、惰性表示、分段表示）
  3. 倾斜二进制数（倾斜二进制随机访问列表、倾斜二项式堆）
  4. 三进制和四元数

一些最好的技巧，提炼出来：

  • 区分数字的密集和稀疏表示（通常您在矩阵或图形中看到这一点，但它也适用于数字！）
  • 冗余数字系统（具有多个数字表示形式的系统）很有用。
  • 如果将第一个数字安排为非零或使用无零表示，则检索数据结构的头部会非常有效。
  • 通过分段数据结构来避免级联借用（从列表尾部获取）和进位（从 consing 到列表）

这也是该章的参考列表：

  • Guibas、McCreight、Plass 和 Roberts ：线性列表的新表示。
  • Myers：应用随机访问堆栈
  • Carlsson、Munro、Poblete：具有恒定插入时间的隐式二项式队列。
  • Kaplan、Tarjan：通过递归减速进行串联的纯函数列表。

Chris Okasaki has a very good chapter in his book Purely Functional Data Structures that discusses "Numerical Representations": essentially, take some representation of a number and convert it into a data structure. To give a flavor, here are the sections of that chapter:

  1. Positional Number Systems
  2. Binary Numbers (Binary Random-Access Lists, Zeroless Representations, Lazy Representations, Segmented Representations)
  3. Skew Binary Numbers (Skew Binary Random Access Lists, Skew Binomial Heaps)
  4. Trinary and Quaternary Numbers

Some of the best tricks, distilled:

  • Distinguish between dense and sparse representations of numbers (usually you see this in matrices or graphs, but it's applicable to numbers too!)
  • Redundant number systems (systems that have more than one representation of a number) are useful.
  • If you arrange the first digit to be non-zero or use a zeroless representation, retrieving the head of the data structure can be efficient.
  • Avoid cascading borrows (from taking the tail of the list) and carries (from consing onto the list) by segmenting the data structure

Here is also the reference list for that chapter:

  • Guibas, McCreight, Plass and Roberts: A new representation for linear lists.
  • Myers: An applicative random-access stack
  • Carlsson, Munro, Poblete: An implicit binomial queue with constant insertion time.
  • Kaplan, Tarjan: Purely functional lists with catenation via recursive slow-down.
回复 原文
俯瞰星空 2024-10-29 18:16:07

“三进制数可以用来表示
自相似结构如
谢尔宾斯基三角或康托集
方便。” 来源

“四进制数用于
二维希尔伯特曲线的表​​示。” 来源

“四虚数系统
最早由唐纳德·高德纳 (Donald Knuth) 提出
1955年，在向一所高中提交的一份报告中
科学人才搜寻。它是一个
非标准位置数字系统
它使用虚数 2i 作为
它的基地。它能够代表
每个复数仅使用
数字 0、1、2 和 3。” 来源

“罗马数字是双进制系统。” 来源

“Senary 可能被认为在以下方面有用：
自古以来对素数的研究
素数，当以六进制表示时，
除了 2 和 3 之外还有 1 或 5 作为
最后一位数字。” 来源

“六十进制（以 60 为底）是一个数字
以六十为基数的制度。它
起源于古代苏美尔人
在公元前第三个千年，它是
流传到古代
巴比伦人，至今仍在使用——
修改后的形式——用于测量时间，
角度和地理坐标
那是角度。” 来源

等等...

此列表是一个很好的起点。

"Ternary numbers can be used to convey
self-similar structures like a
Sierpinski Triangle or a Cantor set
conveniently." source

"Quaternary numbers are used in the
representation of 2D Hilbert curves." source

"The quater-imaginary numeral system
was first proposed by Donald Knuth in
1955, in a submission to a high-school
science talent search. It is a
non-standard positional numeral system
which uses the imaginary number 2i as
its base. It is able to represent
every complex number using only the
digits 0, 1, 2, and 3." source

"Roman numerals are a biquinary system." source

"Senary may be considered useful in the
study of prime numbers since all
primes, when expressed in base-six,
other than 2 and 3 have 1 or 5 as the
final digit." source

"Sexagesimal (base 60) is a numeral
system with sixty as its base. It
originated with the ancient Sumerians
in the 3rd millennium BC, it was
passed down to the ancient
Babylonians, and it is still used — in
a modified form — for measuring time,
angles, and the geographic coordinates
that are angles." source

etc...

This list is a good starting point.

回复 原文
瞄了个咪的 2024-10-29 18:16:07

前几天我读到了你的问题，今天面临一个问题：如何生成一个集合的所有分区？我想到的、我使用的解决方案（可能是因为阅读了你的问题）是这样的：

对于一个包含（n）个元素的集合，我需要（p）个分区，计算基数中的所有（n）个数字（ p）。

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

这并不令人惊奇，但很简洁。它是完整的，不会导致冗余，并且使用任意碱基。您使用的基础取决于具体的分区问题。

I read your question the other day, and today was faced with a problem: How do I generate all partitionings of a set? The solution that occurred to me, and that I used (maybe due to reading your question) was this:

For a set with (n) elements, where I need (p) partitions, count through all (n) digit numbers in base (p).

Each number corresponds to a partitioning. Each digit corresponds to an element in the set, and the value of the digit tells you which partition to put the element in.

It's not amazing, but it's neat. It's complete, causes no redundancy, and uses arbitrary bases. The base you use depends on the specific partitioning problem.

回复 原文
凉薄对峙 2024-10-29 18:16:07

我最近遇到了一种很酷的算法，用于根据 0 到 2n - 1 之间数字的二进制表示按字典顺序生成子集。它使用数字的位来确定应选择哪些元素并对生成的集合进行本地重新排序以使它们按字典顺序排列。如果您好奇，我在此处发布了一篇文章。

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

I recently came across a cool algorithm for generating subsets in lexicographical order based on the binary representations of the numbers between 0 and 2n - 1. It uses the numbers' 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're curious, I have a writeup posted here.

Also, many algorithms are based on scaling (such as a weakly-polynomial version of the Ford-Fulkerson max-flow algorithm), which uses the binary representation of the numbers in the input problem to progressively refine a rough approximation into a complete solution.

回复 原文
把回忆走一遍 2024-10-29 18:16:07

不完全是一个聪明的基础系统，而是对基础系统的巧妙使用：Van der Corput序列是低差异序列通过反转数字的基数 n 表示形式而形成。它们用于构建二维 Halton 序列，看起来有点像 这个。

Not exactly a clever base system but a clever use of the base system: Van der Corput sequences are low-discrepancy sequences formed by reversing the base-n representation of numbers. They're used to construct the 2-d Halton sequences which look kind of like this.

回复 原文
这个俗人 2024-10-29 18:16:07

我隐约记得一些关于双基系统加速矩阵乘法的事情。

双基系统是一种冗余系统，一个数字使用两个基数。

 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}。

假设 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

因为它是“显然”（开玩笑地），其中一些方程在第一个系统中很快，而有些在第二个系统中更好 - 因此，最好根据 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

请参阅这篇文章以获得更好的解释，因为我不是该领域的专家。

I vaguely remember something about double base systems for speeding up some matrix multiplication.

Double base system is a redundant system that uses two bases for one number.

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

Redundant means that one number can be specified in many ways.

You can look for the article "Hybrid Algorithm for the Computation of the Matrix Polynomial" by Vassil Dimitrov, Todor Cooklev.

Trying to give the best short overview I can.

They were trying to compute matrix polynomial G(N,A) = I + A + ... + A^{N-1}.

Supoosing N is composite G(N,A) = G(J,A) * G(K, A^J), if we apply for J = 2, we get:

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

also,

         / (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

As it's "obvious" (jokingly) that some of these equations are fast in the first system and some better in the second - so it is a good idea to choose the best of those depending on N. But this would require fast modulo operation for both 2 and 3. Here's why the double base comes in - you can basically do the modulo operation fast for both of them giving you a combined system:

         / (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

Look at the article for better explanation as I'm not an expert in this area.

回复 原文
怕倦 2024-10-29 18:16:07

RadixSort 可以使用各种数基。
http://en.wikipedia.org/wiki/Radix_sort
BucketSort 的实现非常有趣。

RadixSort can use a various number bases.
http://en.wikipedia.org/wiki/Radix_sort
Pretty interesting implementation of a bucketSort.

回复 原文
ま昔日黯然 2024-10-29 18:16:07

这是一篇关于使用三进制数字解决“假币”问题的好文章（您可以在其中必须使用天平尽可能少地检测一袋普通硬币中的一枚假币）

here is a good post on using ternary numbers to solve the "counterfeit coin" problem (where you have to detect a single counterfeit coin in a bag of regular ones, using a balance as few times as possible)

回复 原文
孤单情人 2024-10-29 18:16:07

哈希字符串（例如在 Rabin-Karp 算法中）通常会评估字符串作为由 n 位数字组成的以 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

但在大多数实际应用中，结果值会取某个合理大小的数字的模，以保持结果足够小。

Hashing strings (e.g. in the Rabin-Karp algorithm) often evaluate the string as a base-b number consisting of n digits (where n is the length of the string, and b is some chosen base that is large enough). For example the string "ABCD" can be hashed as:

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

Substituting ASCII values for characters and taking b to be 256 this becomes,

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

Though, in most practical applications, the resulting value is taken modulo some reasonably sized number to keep the result sufficiently small.

回复 原文
我们只是彼此的过ke 2024-10-29 18:16:07

平方求幂基于指数的二进制表示。

Exponentiation by squaring is based on binary representation of the exponent.

回复 原文
北渚 2024-10-29 18:16:07

在Hackers Delight（我眼中每个程序员都应该知道的书）中有一个关于不寻常基数的完整章节，例如 -2 作为基数（是的，右负基数）或 -1+i （i 作为虚数单位 sqrt(-1)) 作为基数。
另外，我很好地计算了最好的基础是什么（就硬件设计而言，对于所有不想阅读它的人：方程的解是 e，所以你可以选择 2 或 3，3 会好一点（因子比 2) 好 1.056 倍 - 但技术上更实用)。

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

In Hackers Delight (a book every programmer should know in my eyes) there is a complete chapter about unusal bases, like -2 as base (yea, right negative bases) or -1+i (i as imaginary unit sqrt(-1)) as base.
Also I nice calculation what the best base is (in terms of hardware design, for all who dont want to read it: The solution of the equation is e, so you can go with 2 or 3, 3 would be little bit better (factor 1.056 times better than 2) - but is technical more practical).

Other things which come to my mind are gray counter (you when you count in this system only 1 bit changes, you often use this property in hardware design to reduce metastability issues) or the generalisation of the already mentioned Huffmann encoding - the arithmetic encoding.

回复 原文
断桥再见 2024-10-29 18:16:07

密码学广泛使用整数环（模算术）和有限域，其运算直观地基于具​​有整数系数的多项式的行为方式。

Cryptography makes extensive use of integer rings (modular arithmatic) and also finite fields, whose operations are intuitively based on the way polynomials with integer coefficients behave.

回复 原文
猫七 2024-10-29 18:16:07

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

I really like this one for converting binary numbers into Gray codes: http://www.matrixlab-examples.com/gray-code.html

回复 原文
雨的味道风的声音 2024-10-29 18:16:07

很好的问题。这个名单确实很长。
告诉时间是混合基数的一个简单实例（天 | 小时 | 分钟 | 秒 | am/pm）

如果您有兴趣了解它，我创建了一个元基枚举 n 元组框架。这是基本编号系统的一些非常甜蜜的语法糖。它还没有发布。通过电子邮件发送我的用户名（gmail）。

Great question. The list is long indeed.
Telling time is a simple instance of mixed bases (days | hours | minutes | seconds | am/pm)

I've created a meta-base enumeration n-tuple framework if you're interested in hearing about it. It's some very sweet syntactic sugar for base numbering systems. It's not released yet. Email my username (at gmail).

回复 原文
笑梦风尘 2024-10-29 18:16:07

我最喜欢使用基数 2 的算法之一是算术编码。这是不寻常的，因为该算法的核心使用二进制 0 到 1 之间的数字表示。

One of my favourites using base 2 is Arithmetic Encoding. Its unusual because the hart of the algorithm uses representations of numbers between 0 and 1 in binary.

回复 原文
想你的星星会说话 2024-10-29 18:16:07

可能AKS就是这种情况。

May be AKS is the case.

回复 原文
~没有更多了~

关于作者

独﹏钓一江月

暂无简介

0 文章
0 评论
24 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

初遇

文章 0 评论 0

听闻余生

文章 0 评论 0

Z_dy

文章 0 评论 0

左岸枫

文章 0 评论 0

1848719402

文章 0 评论 0

婷

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文