找回密码立即注册
搜索
热搜: 论文 科普 华科
查看: 33|回复: 0

古代三大算法的公式

[复制链接]   [推荐给好友]

45

主题

83

回复

50

博文
发表于 2017-11-21 19:16:23 | 显示全部楼层 |阅读模式
本帖最后由 wxmwrk 于 2017-11-21 22:01 编辑

    古代有三大算法:第一是寻找素数的埃拉特斯特尼筛法。
第二是求方根的开方法。
第三是欧几里得辗转相除法。


这些算法已经有两千多年,直到最近几年才找到公式。                                             

  第一,寻找素数的筛法公式
                                                                           素数的普遍公式
      要得到不大于某个自然数 n 的所有素数,只要在2— n 中将不大于素数的倍数全部划去即可。

      上述筛法可以总结为:
1,如果 n 是合数,则它有一个因子d 满足1 < d

2,若自然数n不能被不大于任何素数整除,则n是一个素数。(【代数学词典】259页,上海教育出版社)。

可以把2上面的汉字内容等价转换成为英语字母表示:


  .........(1)

其中 表示顺序素数2,3,5,....。≠0。

这样解得的 n,若 ,,则n是一个素数。


我们可以把(1)式内容等价转换同余式组表示 :

  ........(2)

由于(2)的模,,..., 两两互素, 根据孙子定理(中国剩余定理)知,对于给定的,,...,,(2)式在...范围内有唯一解。  

二,范例
例如, k=1时,

解得n=3,5,7。求得了(3,))区间的全部素数。

k=2时,

,解得n=7,13,19;

  ,解得n=5,11,17,23。
求得了(5,)区间的全部素数。

k=3时
317,3713,4319
11,4117,472329
求得了(7,)区间的全部素数。

仿此下去可以求得任意大的数以内的全部素数。
并且一个不漏地求得。
对于所有可能的值,(1)和(2)式在...范围内,有()()()...() 个解。
[url=][/url]
清华大学出版社【品数学】。




第二,求方根公式
         牛顿二项式定理在开方过程中可以与牛顿切线法等价,参见台湾中央研究院【数学传播】136期(从牛顿二项式定理开方到牛顿切线法)作者王晓明王蕊珂。
公式是迭代的。
                      .......(1)
=          .......(2)


举例:
一,开立方: 
.......(3)
例如,A=5,k=3,即求:
 5介于之间(1的3次方=1,2的3次方=8)
初始值可以取1.1,1.2,1.3,1.4,1.5,1.6,1.7,1.8,1.9,2.0都可以。例如我们取按照公式:
第一步:=2+(5/-2)1/3=1.75。输入值大于输出值,负反馈;
即5/2×2=1.25,1.25-2=-0.75,-0.75×1/3=-0.25,2+(-0.25)=1.75,比前面多取一位数。即取2位数值,即1.7。
第二步:=1.7+(5/-1.7)1/3=1.71.输入值小于输出值,正反馈。
即5/1.7×1.7=1.73010,1.7301-1.7=0.03,0.03×1/3=0.01,1.7+0.01=1.71。取3位数,比前面多取一位数。
第三步:=1.71+(5/-1.71)1/3=1.709.
第四步:=1.709+(5/-1.709)1/3=1.7099
这种方法可以自动调节,第一步与第三步取值偏大,但是计算出来以后输出值会自动转小;第二步,第四步输入值
偏小,输出值自动转大。即5=
当然初始值也可以取1.1,1.2,1.3,。。。1.8,1.9中的任何一个,都是X_{1}=1.7
1.5+(5/-1.5)1/3=1.7。

二,开平方
如果用这个公式开平方,只需将(3)式的改成,1/3改成1/2。即
......(3)
例如,A=5:
5介于2²至3²之间。我们取初始值2.1,2.2,2.3,2.4,2.5,2.6,2.7,2.8,2.9都可以,我们最好取
中间值2.5。
第一步:2.5+(5/2.5-2.5)1/2=2.2;
即5/2.5=2,2-2.5=-0.5,-0.5×1/2=-0.25,2.5+(-0.25)=2.25,取2位数2.2。
第二步:2.2+(5/2.2-2.2)1/2=2.23;
即5/2.2=2.272727,2.272727-2.2=-0.072727,-0.072727×1/2=-0.036363,2.2+0.036363=2.23。取3位数。
第三步:2.23+(5/2.23-2.23)1/2=2.236。
即5/2.23=2.242,2.242-2.23=0.012,0.012×1/2=0.006,2.23+0.006=2.236.
每一步多取一位数。计算次数与计算精确度成为正比。这个方法又叫反馈开方,即使你输入一个错误的数值,也没有关系,输出值会自动调节,接近准确值。 这个方法的依据是根据牛顿切线法得来。也可以通过牛顿二项式定理推出。
712694641033425198.jpg 1859423696152591675.jpg 3043025973220260748.jpg 1148417904980717959.jpg

第三,欧几里得辗转相除法
公式还没有找到。






回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表