瀏覽單個文章
沒問題
Major Member
 

加入日期: Dec 2015
文章: 210
引用:
作者奶油銓
被除數有幾位根本不重要,重點是除數位數。假設你的除數是n位,依據被除數的最高位數與除數的最高位數,你每次選取被除數最高n或n+1位數做運算,這時商最多也不過是0到9。求一個商你也不過是進行 n次的個位數的乘法運算,與n位數的減法。

最浪費時間的是因為除數大,要用的計算紙很浪費而已。

即使是使電腦來算,對你這幾百位的數字,也是需要想想辦法。畢竟電腦預設的數值也沒法儲存到這麼多位(大概是20位吧)。你採用了各種奇怪的算法,反而增加了運算的次數。

你其實簡單的用python或是C寫個程式,比較一下運行的速度就好了啊。你甚至可以比較一下總共進行的乘法與減法的次數,按照次數來比較效率。


本來是不想回的,不過,還是有幾點要說一下。

一、不管多大位數的被除數,你都要先假設,如果你的除數是一,那你的計算次數就是由被除數決定,雖然答案很明顯,但是電腦沒這麼聰明。
二、你說對一部份,大部份的時候,是除數決定計算的次數,當遇到很小的除數時「千位或萬位的除數」,你確實可以用乘法先去算乘積,但是當你的除數多達七十幾位到一百位的時候『還包含五十位小數』,這對電腦來說也是很痛苦的。
三、有人可能沒經歷過那個古早時代的電腦計算,當年最大的被除數最多也只能表示到正負三萬二千七百六十七。想一下,你要怎麼計算阿波羅計劃的地月軌道?
四、為什麼總是要增加這麼多步去計算乘法?那是因為除法很明顯沒有快速計算的解,所以你就算在網上能找到的計算方式絕大多數都是先算乘法。
五、當你的數大於二十一位以後,就算你用現代的超算,你的計算時間也是指數級的提升。或許你一輩子都不會遇到這麼大的數,一但你遇到了,你就會知道這樣的計算耗時有多恐怖。
六、如果你用純軟體的方式來做計算,你如果不想方設法做最佳化,你還會以為你的電腦當機了,當你要計算的數不論是除數或被除數都這麼大,而且我只是寫出一筆而以,我手上還有十幾萬筆要算。
七、我也想過用客制化的硬體去計算,就算假設你手上的數只有四十位就好,你要做的減法就六十五次含以上,還不計算你要猜你的除數的商或是乘積,你不會擁有無限的面積跟資源去建構一個可以一次連減六十五次的除法器。就算你建構出來,這樣的除法器其實也沒有非常快。
八、你也會想如果我重覆計算六十五次就能得出答案,但是你知道當你如果可以使用乘法來計算的話,你的計算次數可能減少到只剩下三十三次或更少,你只要假設每計算一次只花你三十秒就行。這是相當可觀的速度提升。而且,乘法計算一次所需要的時間比除法更少,最好的最差狀況可能只要十秒一次甚至更少。
九、許多數學及計算機科學的高手無不絞盡腦汁渴求更快速的除法算法,你或許會問,INTEL跟AMD不是讓乘除法都做到一樣快嗎?事實是,他們做得到,但是你卻不知道他們如何做到。你在網上找得到的解答,我不是沒有試過,但是效果不盡理想。
十、這個問題在台灣問,大家可能不會非常有感覺,但是你到對岸去問,那可能很多計算機科學的人會認真跟你討論,因為他們的總量太大,就算只是用軟體計算,他們都要去考慮超出的數要怎麼更快的計算。
十一、我重申,我的目的是希望找到一種可以預先計算餘數的算法,而且最好的能優先使用乘法來計算,如果可以,也可以將除數及被除數分拆部份計算,也可以平行計算。
十二、對於那些不是計算機行業的人、非數學專業的人或是其他產業的人,保持開放的心,這世上有很多奇怪的問題,對你而言是無意義,但是對其他人而言這並非無聊找事做,純粹的智力思考其實也很有趣。

補充幾點:
一、我確實一開始要求是適合『人』算的算法,唯一的差別是,古代人肯定沒有機會計算一百位數以上的數。
二、我一直強調,你幾乎沒有看到有那位數學的大神去討論除法的快速求解,就算是現代人也一樣。
三、為了快速的求出商或餘,你在網上找得到的大量算法,仍是從乘法入手。
四、為什麼我會要求用這麼複雜的算法去求除法?雖然古代不會有這麼多無聊人士或實際需要得去求這麼大的除數及被除數,但是我得去尋找古人是怎麼解決這類大除數及被除數的問題,或許能夠找到有用的相關方法。
五、從求圓周率這個問題來看,就可以知道,古人的求解精度及效度也就五到六位數而以『不管是計算小數或是計算整數』,而且很顯然要求到這麼長位數的數,計算所花去的時間都太長了。
舊 2024-07-25, 07:40 PM #40
回應時引用此文章
沒問題離線中