|
||
|
Basic Member
加入日期: Feb 2002 您的住址: 地球
文章: 20
|
引用:
這麼看來你根本就不懂電腦怎麼運行大數除法的。 或者以我的經驗來看，你沒有學過電腦程式類的課程。 大數，不管你是整數還是單/雙精度浮點數，超過宣告位數上限的數字通常使用矩陣(或是串列)來存放，有些語言比如R，用串列來記錄位數是那更方便(一個串列的長度大概是可以有約130位元吧，太久沒用了，忘了，你的位數比較大的話，兩個串列也就夠了。)把串列裡面的數值根據除數長度拆出來然後作除法然後根據餘數的位數再取合適的串列繼續除， 你口中所謂的幾百位元除法我想我的程式應該都幾分鐘內就除完了。 這種處裡大數字方法應該在很早以前人們就知道了，以我來說早在我讀書時，那時做數值分析的函式庫 IMSL 或是一般的教科書 Numerical Recipes in Fortran這類的書籍裡面都有，優化過後的程式碼都在書裡，你網路上找一下隨便都找得到。 除法要平行運算? 這程式我倒是沒寫過，直覺是不行。畢竟除法有次序性，後續的除法會依賴前一次的餘數。不過比如你要做64題的除法運算，是可以很簡單的寫一個程式一次把64個問題分別送到64台電腦或是64個核心去做計算，這就可行，網路上隨便找都有相關的程式碼( 關鍵字 mpich)。 另外，除法其實是減法(當然你也可以說除法是乘法，乘上倒數即可，隨便)，你不愛除法其實也可以不斷地計算減法，減到不能減的減法次數就是商。(這些其實我前面說的書裡面，都有介紹，) 有小數的話，也不影響，你想要求到小數點後比如n位，粗略地來說(後續的說法可能不精準)把你的被除數後面多上n個0，然後作除法，除完以後最後n位就是小數點後的位數了。 比如說 23/7 = 3.285714 你的運算只能求到3但你想算到小數點後一位，你可以計算 230/7 =32 這樣就得到小數點後第一位了。 簡單來說我完全不認同你所謂的 "當你的數大於二十一位以後，就算你用現代的超算，你的計算時間也是指數級的提升"。 請你尊重一下電腦的發展好嗎，現在計算40位的整數除法運算通常也不用1秒。即使再多10位到50位數，也不用1秒，哪來你說的現代的超算 ? 我只用i5的個人電腦好嗎。(我測試到60位數都是enter按下去以後直接有答案) |
||||||||
2024-07-25, 09:38 PM
#41
|
|
|
Major Member
 加入日期: Dec 2015
文章: 210
|
引用:
哈，我需要考慮的細節跟你要考慮的是不一樣的。 一、所有的軟體解法都只能被參考但是不能被直接採用，你要用串列來求，是的，這是很快的，但是在我要處理的問題中，不能使用串列。 二、分送也是不可行的。 三、我所謂的超算是指，你只能用『一個』單位的處理器， 四、我的比較單位是奈秒，相比於乘法，現代除法的速度遠低於乘法。 五、如果你是INTEL或是AMD那你可以分享一下，你去算一下電路複雜度就會知道，再怎麼快，都不可能比乘法快。不管你是連減或是重覆減。 此文章於 2024-07-25 10:13 PM 被 沒問題 編輯. |
|||
|
2024-07-25, 09:55 PM
#42
|
|
|
Advance Member
  加入日期: Oct 2003
文章: 324
|
大家也太激動了吧 樓主的算法 是減少除數的位數 來降低計算難度
但因為減少對後面位數的運算，所以每次除玩都要再針對那部分再次運算 用增加步驟來換取降低計算難度 只是這種算法當你每減少除數一位數 後面要補算的就愈多 有利有弊 看你怎麼看而已 |
|
2024-07-25, 10:35 PM
#43
|
|
|
Advance Member
加入日期: Sep 2015
文章: 318
|
就跟你說你還是在長除法只不過是脫褲子放屁在長除….
還要凹. 好啦我幫你褲子脫一半， 剩下你自己脫光放完屁可以吧！ 😂 |
|
2024-07-26, 09:19 AM
#44
|
|
|
Major Member
加入日期: Dec 2015
文章: 210
|
引用:
太感謝你替我脫一半的褲子。 請用力把剩下的一半也脫完。🤣 看到沒，當你把除數減小時，你可以用更多的乘法跟加減法來計算。 而且你的乘積很小，你甚至可以查表計算，而你的加減法器也很小，速度自然會提高。 我還有更快速的算法，其實網上也找得到。 但是那全都是軟體解。 Nice try. You can do it better and harder. 此文章於 2024-07-26 11:42 AM 被 沒問題 編輯. |
|
|
2024-07-26, 10:51 AM
#45
|
|
|
Golden Member
加入日期: Feb 2004 您的住址: 從來處來
文章: 2,762
|
這種特殊的算法是很多的，過去沒有計算機的時代，為了快速求解，發明了很多奇妙的算法。
你這算法並沒有比較快，但對於手算極大數來說確實能減少出錯率。但對現在來說，已經沒有任何意義。 因為你這算法看起來計算複雜度應該還是 O(N^2), 因為本質與長除法相同, 但現在用FFT配合牛頓切線法，可以達到 O(NlogNlogN), 如果用程式來算極大數，你這算法會被甩到連車尾燈都看不到。 還有電腦程式工程師比你想像中聰明多了，早就發明了快到你想都想不到的方法——魔術數字法。 反平方根快速演算法 https://zh.wikipedia.org/zh-hant/%E...%AE%97%E6%B3%95 程式碼中有一段 i = 0x5f3759df - ( i >> 1 ); // what the fuck? 其中的 0x5f3759df 就是魔術數字，計算反平方根卻出現一個固定的魔術數字，神奇吧？這是最佳化牛頓切線法來的。 （後面那段註解則可看出，當初使用這段程式的工程師的驚奇程度  ）此文章於 2024-07-26 12:23 PM 被 Adsmt 編輯. |
|
2024-07-26, 11:47 AM
#46
|
|
|
Amateur Member
 
加入日期: Jan 2005
文章: 33
|
把問題貼給chatGPT看
馬上就給答案了..... 因為我數學不好 也不知道這答案對不對就是了XD 今有一被除數3246738及除數178，當相除時，我們可以使用計算機，而且我們可以採用現代數學直式計算或是長除法等方法求解。 ChatGPT 沒問題！我們可以使用直式計算法或長除法來計算3246738除以178。以下是兩種方法的示範： 直式計算法： 除：從左邊開始取前幾位，使其值大於或等於178。 3246 ÷ 178 ≈ 18（取18作為商） 乘：將商18與除數178相乘。 18 × 178 = 3204 減：用被除數的部分3246減去3204，得到42。再把下一位數7放下來，變成427。 重複上述步驟： 427 ÷ 178 ≈ 2 2 × 178 = 356 427 - 356 = 71，再把下一位數3放下來，變成713 重複上述步驟： 713 ÷ 178 ≈ 4 4 × 178 = 712 713 - 712 = 1，再把下一位數8放下來，變成18 重複上述步驟： 18 ÷ 178 = 0（因為18小於178，商為0） 所以，3246738 ÷ 178的商為18240，餘數為18。 長除法： 把3246738寫在被除數的位置，把178寫在除數的位置。 從左邊開始，每次取被除數的一部分（最多到下一位數），直到該部分大於或等於178。 每次計算商，把商寫在上面，並用商乘以除數，再用該結果減去被除數的一部分。 把新的餘數和下一位數組合成新的被除數部分，重複以上步驟。 若你有計算機的話，也可以直接進行計算： 3246738 ÷ 178 ≈ 18240.4382022472 3246738÷178≈18240.4382022472 這結果中，小數部分表示餘數，所以18240是商，而餘數為0.4382022472乘以178，約為78。 最終，使用計算機的精確結果為：3246738 ÷ 178 = 18240.4382022472 (商為18240，餘數為18)。 |
|
2024-07-26, 04:49 PM
#47
|
|
|
Major Member
加入日期: Dec 2015
文章: 210
|
引用:
你好，這個東西我是知道的… 不過，這有助於快速計算除法嗎？ 我還是很感謝你的介紹。 FFT配合牛頓切線法，可以達到 O(NlogNlogN)這我也是知道的。 現在我們回到問題的原點，你這篇提到的FFT變換，主要是使用軟體達成的，這只是一種計算方法，而不是一種計算步驟。 一般不會被實現成真實的計算電路。 我是沒有卡馬克厲害，我也不覺得我是『聰明』的工程師。 修正… 此文章於 2024-07-26 07:19 PM 被 沒問題 編輯. |
|
|
2024-07-26, 06:34 PM
#48
|
|
|
Major Member
加入日期: Jan 2002
文章: 159
|
INTEL整數除法電路的運算速度從來沒有跟整數乘法一樣快
https://www.agner.org/optimize/instruction_tables.pdf 就算是Intel Ice Lake and Tiger Lake第十代cpu MUL IMUL r64 Latency=3 DIV IDIV r64 Latency=15 還是差好幾倍
__________________
|
|
2024-07-26, 07:04 PM
#49
|
|
|
Major Member
加入日期: Dec 2015
文章: 210
|
引用:
謝謝指教。這是我的錯誤。 那麼，雖然我錯了，但是這說明了，至少我追求的方向是有意義的。 此文章於 2024-07-26 07:15 PM 被 沒問題 編輯. |
|
|
2024-07-26, 07:12 PM
#50
|
|
