注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

itoedr的it学苑

记录从IT文盲学到专家的历程

 
 
 

日志

 
 

中国数学发明:幂进制  

2016-01-22 20:35:44|  分类: big-data |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
收集两篇文章希望对数据库开发者们有用。
用整数树的研究成果 探索软件的创新发展

中国软件行业协会嵌入式系统分会副理事长兼秘书长 郭淳学

1、整数树与软件创新

人类对自然界中的数的认识和使用是从1、2、3……自然数开始,以后使用0表示没有、相等、起始、终点等现象。负自然数的出现,使数发展为整数,包含正整数(自然数)、0和负整数(负自然数)。并且,正、负整数以0为中点成相互对称排序,也可视为以0为中心相互成镜像。

一般人对自然数最熟悉和常用,都知道自然数是以1为增量由小到大排序的无限数列。但是,说自然数7和11与3有固定的直接关系,且与1与有固定的间 接关系时就不一定知道了。对整数的研究发现,整数的这种关系都是在二叉树上的关系:7和11同是3的子结点,3是1的子结点。1另外还有1个子结点5,而 5也有两个子结点分别是9和13……整数和整数间的这种固定关系是客观存在的,不是人为设计的产物。同时,还发现所有的整数全部都各自有规律地分别固定在 相同结构的四棵二叉树上,且整数无限多,这四棵二叉树也对应无限大。对于这四棵二叉树,现统称为整数树。

现代数学已经使用很多种数,数除整数外还有分数、无理数、虚数等。但是这些数,除正整数(自然数)是自然界中客观存在的数以外,其他数都是在正整数 基础上由人根据需要发明的。即然这些数是在正整数基础上发明的,必然都可以转换成正整数。正如,分数可转换成小数,小数再通过改变单位换成整数。例如:四 分之一公斤换成0.25公斤,0.25公斤等于250克等。实际软件算法中,对小数常用浮点运算,通过移位将小数变整数运算后,再反移位变回小数。因此,对整数的深入研究,将会促进软件的发展。

从宏观看,所有软件的结构都是由数据输入、数据处理和数据数出三部分构成。每个软件的数据输入、数据数出的部分有较多的共性,数据处理部分在数学模型、数据结构和算法等方面至少有一部分有较大的不同。

评价软件的整体水平看系统软件、系统软件水平看底层技术、底层技术看采用的数学模型、数据结构和算法等的水平。因此,研究出或发现新的、高水平的数学模型、数据结构和算法等是发展软件的关键,是软件创新的主战场。

创新的核心是思路和方法的创新。整数树的发现和对其规律及派生的二的幂次方数制的研究,不仅是在涉及数学模型、数据结构和算法等软件底层技术方面进行突破的尝试、也是为软件创新在思路和方法上进行变革的探索。

苹果熟透了从树上落下来,是极普通的自然现象,千百年来没有人注意。有一天,牛顿注意了,并进行了探索,发现了地球引力的存在和研究出其关系的定律,为物理学的创新做出重大贡献。

整数树和反映整数树层间与结点间关系的二的幂次方数制不是以往的一些数据结构和数制是由人设定的,他们是客观存在。因此,值得对整数树和二的幂次方数制做进一步了解。

2、整数树的结构

整数树是最近一时期,北京乾坤化物数字技术有限公司和中国软件行业协会嵌入式系统分会的技术人员共同对整数进行研究时,由北京乾坤化物数字技术有限公司的技术人员首先发现整数是按照一定的规律,并以对称二叉树的形式进行生长的,为此提出了整数树的概念。

理论上整数树有同样结构的四棵树,都是以0为起点,对应各自表现的四个整数群,以无限大的形式存在。这四个整数群分别为正、负奇数群和正、负偶数 群。所有的正、负奇数各组成一个二叉树,所有的正、负偶数也各组成一个二叉树。由于负奇数二叉树和负偶数二叉树是以0为起点的正奇数二叉树和正偶数二叉树 的镜像,结构上一样,为简便起见,就不再一同介绍。

 正奇数二叉树和正偶数二叉树的特点是,都以0为同一父结点,每个父结点有且只有两个子结点。每层结点数,呈与该层数相对应的2的幂次相等。如0为 第0层,有1个结点。第一层有2个结点,为奇数1和偶数2,分别是正奇数树和正偶数树的起始结点。第二层有4个结点,分别是奇数3和5,偶数2和4。第三 层有8个结点,分别是奇数7、9、11和13,偶数8、10、12和14……以此类推,所有整数以结点方式在整数树上严格地按2的幂次方规则无限增长。

下面三点是了解整数树的比较重要的关键点:

(1)整数的生长公式:MN+1 = MN + X*2N,这是一个递归方程式,其中X={1,2},X是数字符号,也代表整数树的2个分支。N={0,1,2,…}, N是整数分布的层数,MN 为第N层的整数值,该整数是MN+1 层的父整数,当N=0时,MN =0,它表示整数树的开始,对于N>0的任何一个MN ,其子整数有并且必须有2个,分别为MN+1 = MN + 1*2N,MN+1 = MN + 2*2N。

(2)整数树。整数按照其生长公式,得到一个二叉树,这个树就是整数树。树结点是按照顺序分布的,它记录的是一个事件发生的过程。整数按照生长顺序分布在各自的树结点上。

(3)整数树结点代码和整数的对应关系是,每个整数树结点代码等于该结点整数,其中结点代码的排列顺序为从右向左(也可以规定为从左向右排列),最右边的位置为0位(二的零次幂位),表示数最小位;然后向左依次按二的幂次以1为增量排序增大。

四层的二的幂次方进制的正整数树结构图如下:

图中圆圈为二叉树的每个结点,圆圈内上部数字为用二的幂次方数制表示出的整数的结点代码,下部数字为对应的十进制整数。

字母N表示整数树的层数,字母R表示各父结点与子结点的差值。

中国数学发明:幂进制 - itoedr - itoedr的it学苑

 

从图中可以明显看到一些规律:

(1)整数按奇数和偶数有规则地组成为两个二叉树。

(2)二叉树的每层的结点数为2n,个,n=层数。

(3)每个父结点有两个子结点:奇数子结点和偶数子结点。父结点与奇数子结点间的差值R=2n-1,与偶数子结点的差值R=2*2n-1,n=子结点的层数。

(4)两个子结点之间为父结点与小子结点的差值R=2n-1,,n=子结点的层数。

(5)在二叉树中每层各结点的二的幂进制结点代码的位数都等于该层的层数N。

(6)在二叉树中每层各结点的二的幂进制结点代码都等于该结点整数值。

(7)在二叉树中每层各结点的二的幂进制结点代码和对应整数值的位置固定不变等等。

当我们对整数树进行更深入的研究时,可能会发现更多的关系和规律,会对整数产生更多的认识和新的算法。

3、二的幂次方进制数

数制是人类表示自然界物质数量的方法或规则。某一数制的产生或消亡与需求、环境、文化等有关。因此,各数制间存在产生时间、消亡时间、应用领域等不同;而且,有些数制还会长期并存,被相互转换应用。

人类从远古结绳计数发展到产生不同数制,是因生产技术的不断提高和经济活动的需求而演变来的。历史上表示数的数制曾有很多种:古代巴比伦时用60进 制,我国的天干地支、时间的分钟等也是60进制,著名的玛雅文化时代用20进制,一年中的月份和时间的小时用12进制等。近代,随着科学和经济的发 展,10进制数成为人们日常进行数学运算时最常用的数制。进入20世纪以后,电子计算机的出现逐步开始使用2进制、8进制、16进制、二—十进制等。由于 2进制数可直接对应表示日常生活中的存在与没有、开和关等现象,并且在硬件上结构也相对简单,所用的元器件少,因此,成为计算技术中的主要数制。

2进制数制为现代计算技术的发展提供了有力的支撑。但是,现代计算技术快速发展到今日,在软件和硬件方面都遇到了瓶颈。由于数字社会的信息出现着爆 炸性的增长,对计算机硬件和软件设 计者来说,如何能更快速地进行大量的数据运算和处理,成为技术难题。以往,计算机硬件设计者通过不断增加计算机位长,以提高计算机的每次并行运算和处理能 力,来满足不断增长的大量运算和处理的需求。现代微电子技术在芯片设计和制造上已几乎达到物理的极限,这意味着以2进制数为支撑的计算机硬件技术遇到发展 障碍。同时,海量的信息存储和检索需求,向现代计算机软件技术提出挑战。Google公司宣布他们已具有处理200亿个的网络页面能力,这也接近当前软件 技术的极限。但是,未来的网络页面将会大大超过这个数字。高清晰度视频通信的数据传输带来的海量信息,也为通信专家带来攻克难题。今后、数字社区,数字国 家,数字地球建设所需处理的信息将会是及乎无限的数据,如何对这些数据进行定位存储和进行删、改、加操作, 2进制数的电子计算机已难以胜任。

电子计算机是通过高速处理2进制数据来实现管理和控制的。计算机处理2进制数的最基本运算是加法。通常软件设计人员将复杂的问题的算法,都简化为2进制数加法或所需的逻辑运算进行操作。因此,通过硬件或软件加大电子计算机每次运算数据的量是解决问题关键。

乘法是加法的速运算,幂则是乘法的速运算。如果,我们在2进制数的基础上,进行数制变革,采用二的幂次方进制数,对目前计算技术所遇到的发展瓶颈可能会有所突破。

二的幂次方进制数的提出是为了解决整数树的运算问题。二的幂次方进制数是一个新的计数方法,它由二个基本数字符号1,2组成(也可以规定为0和1或 A或B等)。二的幂次方进制数还有一个字符:0 (也可以规定为3或C等),用于表示第三种状态,如:相等、起始、高阻等。在二的幂次方进制数中,0不用于表示数。

二的幂次方进制数计数规律是满二的幂次方再进一,且进位位恢复系数为1。为符合人们日常十进制运算习惯,我们将二的幂次方进制数中,用数字符号1直 接表示整数1,用数字符号2直接表示整数2,可使这二个数字符号的表示与十进制的整数1和2相同。整数3以后的整数将用不同的数字符号表示。如:整数3将 产生进位,用两位数字符号11表示,整数4不产生进位,用两位数字12表示,整数5产生进位,用2位数字21表示,整数6不产生进位,用两位数字22表 示,整数7产生两次进位,用三位数字111表示……。由此可以看到:二的幂次方进制数对应N位整数Z的表示应为:

           Z= X(N)X(N-1) …X(N-N+3)X(N-N+2)X(N-N+1)X(N-N)

其中X={1,2},X数字符号,N={0,1,2…}, N是位数。

每个整数在二的幂次方进制数中仅表示出每位的数字符号,省略了每位对应的数位的权,即二的幂。这与十进制、二进制和十六进制等数字表示时省略数位的权一样。

4、二的幂次方进制整数与10进制整数间的转换

(1)二的幂次方进制整数转换为10进制整数

二的幂次方进制数整数中每个整数转换成十进制整数的公式为:

  整数(十进制)=X*2N+ X*2N-1+…+ X*2 N- N+3+ X*2 N- N+2+X*2 N-N+1+X*2 N-N

其中X={1,2},X是数字符号,N={0,1,2…}, N是位数,2N是每位对应的数位的权。

如二的幂次方进制整数1212、111、222 转换成十进制整数时为:

1212=1*23+ 2*22+ 1*21+ 2*20= 1*8+ 2*4+ 1*2+ 2*1=8+8+2+2=20(十进制)

111=1*22+ 1*21+1*20=1*4+ 1*2+1*1=4+2+1=7(十进制)

     222=2*22+ 2*21+2*20=2*4+ 2*2+2*1=8+4+2=14(十进制)

(2)十进制数整数转换为二的幂次方进制整数的规则:

    整数1的结点代码为1,整数2的结点代码为2.。

一个大于2的十进制数整数Z,计算其结点代码过程:

(a) 用Z除以2,得到倍数X和余数Y,若Y=1则该整数为奇数,其分段代码为1,若Y=0则该整数为偶数,其分段代码为2,其层数N=1;

(b) 若倍数X > 1,则倍数X除以2,并得到一个新的倍数,其层数N加1;

(c) 重复执行(b),直到倍数X = 1,得到的N为该整数所在整数树的层位置;

(d) 计算出该层中最小分支上的2个结点整数Z1和Z2的结点代码,其中Z1 < Z2;

(e) 若Z1≤Z<Z2,则该整数在第N层上的分段代码为1,若Z≥Z2,则该整数在第N层上的分段代码为2;

(f)  Z减掉第N层与第N—1层差值R,就得到其父结点即第N-1层结点的整数ZN-1;

(g) 对整数ZN-1重复(a)到(f),直到N=2为止,这样就得到了该整数的结点代码;

上述的结点整数Z1和Z2的获得方式为:对于一个确定的层N,先构建整数Z1和Z2对应的结点代码,对于Z1,第一个分段代码等于整数Z第一次处理 时得到的分段代码,第N个位置的分段代码为1,中间的N-1至N=2那个位置的分段代码为1,对于Z2,第一个分段代码等于整数Z第一次处理时得到的分段 代码,第N个位置的分段代码为2,中间的N-1至N=2个位置的分段代码为1;然后对这Z1和Z2的2个结点代码进行整数转换,就得到了Z1和Z2对应的 十进制数整数值;可与十进制数整数Z比大小。

上述对于第N层的结点的数值R为,若第N层的分段代码为1,则R=2N-1,若第N层的分段代码为2,则R=2N。

例如十进制数20按上述规则转换为二的幂次方进制数的步骤如下:

1、20除以2,得到倍数X=10,和余数Y=0, 因Y=0该整数为偶数,其分段代码为2,层数N=1。

2、倍数10再除以2,得到倍数X=5,其层数N加1等于2。

3、倍数5再除以2,得到倍数X=2,其层数N加1等于3。

4、倍数2再除以2,得到倍数X=1,其层数N加1等于4。

因倍数X=1,且N=4,得知十进制数20是二的幂次方进制数的整数树上第4层中某个结点上的整数。其整数树结点代码为4位。

5、计算第4层中最小分支上的2个结点整数Z1和Z2的结点代码:

Z1的第一个分段代码等于十进制数20第一次处理时得到的分段代码2,第4个位置的分段代码为1,第3个位置和第2个位置都是1,所以Z1的结点代码为1112。

Z2的结点代码与Z1的不同在第N位,本例中为第4位是2,所以Z2的结点代码为2112。

6、由于Z1的结点代码为1112,转换为十进制数是16;Z2的结点代码为2112,转换为十进制数是24,且Z1≤20<Z2,所以十进制数20的结点代码第4位为1。

7、因十进制数20的结点代码第4位为1,整数树上第4层差值R=2N-1=8。

8、十进制数20在二的幂次方进制数的整数树上的父结点即第N-1层结点的整数ZN-1=20—8=12。

9、循环上述一些相关步骤求十进制数20转换为二的幂次方进制数的结点代码第N-1位分段代码。具体如下:

(1)12除以2,得到倍数X=6,层数N=1。

(2)倍数6再除以2,得到倍数X=3,其层数N加1等于2。

(3)倍数3再除以2,得到倍数X=1,其层数N加1等于3。

(4)计算第3层中最小分支上的2个结点整数Z1和Z2的结点代码:

Z1的第一个分段代码等于十进制数20第一次处理时得到的分段代码2,第3个位置的分段代码为1,第2个位置是1,所以Z1的结点代码为112。

Z2的结点代码与Z1的不同在第N位,本例中为第3位是2,所以Z2的结点代码为212。

(5)由于Z1的结点代码为112,转换为十进制数是8,Z2的结点代码为212,转换为十进制数是12,且Z≥Z2,所以十进制数12的结点代码第3位为2。

(6)第3层差值R,因十进制数12(也是十进制数20)的结点代码第3位为2,差值R=2N=8。

(7)十进制数12在二的幂次方进制数的整数树上的父结点即第N-1层结点的整数ZN-1=12—8=4。

(8)循环上述一些相关步骤求十进制数20转换为二的幂次方进制数的结点代码第N-2位分段代码。具体如下:

(1)4除以2,得到倍数X=2,层数N=1。

(2)倍数2再除以2,得到倍数X=1,其层数N加1等于2。

(3)计算第2层中最小分支上的2个结点整数Z1和Z2的结点代码:

Z1的第一个分段代码等于十进制数20第一次处理时得到的分段代码2,第2个位置的分段代码为1,第2个位置是1,所以Z1的结点代码为12。

Z2的结点代码与Z1的不同在第N位,本例中为第2位是2,所以Z2的结点代码为22。

(4)由于Z1的结点代码为12,转换为十进制数是4,Z2的结点代码为22,转换为十进制数是6,且Z1≤4<Z2,所以十进制数4(也是十进制数20)的结点代码第2位为1。

(5)因经本次循环后,层数N=2,表示十进制数20转换为二的幂次方进制数的结点代码计算结束。

将各分段代码按顺序组合,可得到十进制数20转换为二的幂次方进制数的结点代码为1212。

为比较清楚介绍转换原理,列出了上述转换的每一步骤,实际转换可以简化。

5、发现整数树和采用二的幂次方进制数制的意义

 整数在自然界中客观存在,人们只是发现了它,并按照它的规律来进行计数和应用。生活中的十进制、二进制、巴比伦时代的六十进制、玛雅文化时期的二 十进制,只是整数的不同表现形式,没有改变,也不可能改变整数。但是,由于这些数制都建立了自己的完整数学体系,所以为人类文明的发展起到重要作用。同 时,也应看到随着生产和经济的发展,一些不适和数制会逐渐消亡,新的数制也会产生。采用什么数制是生产和经济的发展的需要,采用什么数制也反映当时的生产 和经济的水平。

发现整数树的存在,为进一步了解整数打开新的数学大门。整数树是整数存在的客观数据结构,是数学领域的重大新发现。发现整数树的意义,将随对整数树 的不断深入研究会逐渐显露出来。整数是一切数的基础,通过研究整数树,必然能发现更多的整数新奥密,为数、数学、计算技术的软件、硬件的发展带来新的促 进。

二的幂次方进制数能反映出整数树的各个结点关系,能对整数树上的整数进行运算,因次是研究和应用整数树的工具。整数树表示出的整数新的数据结构和用二的幂次方进制数表示整数的数制,将改变软件的底层技术,对软件的发展带来新算法和创新机遇。

现已发现的对整数的新算法有:

(1)在二的幂次方进制中,两个整数需比大小时,首先比结点代码的位数;位数多的为大;如位数一样时,再比偏移位;偏移位大的为大。偏移位是整数与同层第一个整数的差。规定同层第一个整数的偏移位为1。

(2)对1亿个整数进行排序,采用整数树进行比较,需要的时间为C*1亿次计算,C为小于10的一个常数。而传统的方式所需要的时间为1亿的组合次计算,即1亿*(1亿-1)*(1亿-2)*…*3*2。

(3)用整数树处理整数时只需处理其四分之一:因为偶数均比奇数整多1,将偶数都减1后按奇数处理,处理结果再加1变回偶数。又因每个父结点的两子结点之间固定相差2n-1,,所以只处理一个奇数子结点数,另一偶数子结点数通过加2n-1,就可以得到了。

(4)根据整数树的特性,二的幂次方进制数可以设计成一个二维运算体系,一维计算层数,为Y运算器,另一维是一个指定长度的运算器,为X运算器。比如采用六层结构作为基本运算器,那么层数和基本运算器的结合就可以很容易地组合一个任意大的运算器等等。

对整数树的研究和二的幂次方进制数的数字体系的建立工作还仅是开始,需要研究和完善的的内容还很多,有待进行更深入的研究和完善工作。

  评论这张
 
阅读(71)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017