一进制

計數系統

一进位系统是一个双射,以1底数记数系统。这是一个代表自然数最简单的记数系统:要表示一个自然数N,我们任意的先选用一个符号代表“一”,然后将之重复N次。举例来说,使用|(一个计数符号)作为符号,数字六则以||||||表示。若符号选用1,则数字1、 2、 3、 4、 5、 6在一进制中表示为1、 11、 111、 1111、 11111、 111111 …(OEIS数列A000042[1]。用手指计算的方法也是一种一进位系统。一进位系统对进行中结果的计数或者计算很有用,像是 体育比赛内的分数,因为一进位系统没有中介的结果需要被删去或者舍弃。

各种使用一进位代表8的方式
正字记号,被使用于汉字文化圈

为了易读性,一进位的符号常常以五个为一组凑在一起。这有点类似十进位系统里面,实际使用上常常会以空白或者逗号分隔数字,让100,000,000这种大数字比较易读。第一或者第五个符号可能会弯一个角度作为区别。其他一进位系统以五凑成一堆的例子则是汉字文化圈传统使用的字标记,这个字有五个笔划,有东西新增时就多写一笔。左边图上面的第四个范例,第五个笔划将前面四个凑成五个一组,因为这组符号的形状,有时这种方法被称为“herringbone”(鲱鱼骨)记数法。

巴西以及法国,另一类系统经常被使用:作为像是鲱鱼骨这样将这些“棍棒”排成一排的替代,这个系统是将四个符号排成一个方块,第五个符号则划过这个方块的对角。

加法减法在一进位系统使用特别容易,因为仅仅牵涉比字串的串接稍多的操作。然而,乘法除法则复杂许多。

与其他系统不同,在一进位系统里面并没有代表0的符号存在,因此一进位是只有一个符号的双射系统。如果有代表“零”的符号,那这个系统就会变成二进位。实际上存在的一进位系统没有办法明确表示零,虽然甚么都不写常常被用来隐含这个含意。即使在比较先进的计数系统,像是罗马数字里面,也不存在代表零的符号,相对的这系统使用nullae,也就是拉丁文的“甚么都没有”(nothing)。

与标准的进制相比,一进位系统在大型计算很不方便,因此不在实际上使用。不过有时因此会让这系统出现在计算理论里面的一些决定性问题(像是一些P-完全问题)作为输入,作为“人工的”缩减问题的计算时间或者空间。举例,整数分解这个问题,如果输入是以二进位给予,那一般认为的运作时间会超过输入长度的多项式时间;但是,如果输入是以一进位给予,则变成只需要线性的时间。不过这作法其实有些误导:使用一进位作为输入本来就会导致输入这动作变慢。使用一进位与其他二进位(或者以上)的输入模式,差异会根据输入本身等比例差异到对数(以二为底或者以上)倍;所以运作时间与空间看起来相对于输入长度比较好时,并非是因为我们的演算法变好,而是因为我们故意使用比较长的输入方式。

实际使用

编辑

在古代数学里面实际使用一进位系统的例子,可以参见莫斯科数学纸草书英语Moscow Mathematical Papyrus,其使用日期大约前18世纪左右。

一进位也在一些资料压缩的演算法里面使用;作为例子可参见格伦布编码

一种特殊的一进位系统TeX的软体版本号上面使用,其版本号码是一部份圆周率的十进位表示 – 版本号码是位数的个数。现在的版本号是3.1415926,而这个数字会渐渐地接近π。

参见

编辑

参考文献

编辑
  1. ^ Hext, Jan, Programming Structures: Machines and Programs, Programming Structures 1, Prentice Hall: 33, 1990, ISBN 9780724809400 .

外部链接

编辑