阿波羅網論壇

 找回密碼
 注冊
搜索
熱搜: 活動 交友
查看: 151|回復: 0
收起左側

古代三大算法的公式

[復制鏈接]
發表於 2017-11-21 21:59:51 | 顯示全部樓層 |閱讀模式
古代有三大算法:第一是尋找素數的埃拉特斯特尼篩法,。
第二是求方根的開方法。
第三是歐幾里得輾轉相除法。
這些算法已經有兩千多年,直到最近幾年才找到公式。                                             

  第一,尋找素數的篩法公式

                                                                           素數的普遍公式
      要得到不大於某個自然數 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.
每一步多取一位數。計算次數與計算精確度成為正比。這個方法又叫反饋開方,即使你輸入一個錯誤的數值,也沒有關系,輸出值會自動調節,接近准確值。 這個方法的依據是根據牛頓切線法得來。也可以通過牛頓二項式定理推出。

第三,歐幾里得輾轉相除法
公式還沒有找到。


您需要登錄後才可以回帖 登錄 | 注冊

本版積分規則

手機版|Archiver|阿波羅網

快速回復 返回頂部 返回列表