作者 主題: 不限位數精準度的四則運算  (閱讀 13633 次)

0 會員 與 1 訪客 正在閱讀本文。

stlee

  • 鑽研的研究生
  • *****
  • 文章數: 817
    • 檢視個人資料
不限位數精準度的四則運算
« 於: 2007-01-01 20:40 »
前陣子把以前買來但是看不懂的書(買的時後以為看的懂)重翻了一遍,書名
叫做:C名題精選100則-碁峰出版,作者:先鏡光
其中的一個問題就是[不限位數精準度的正整數加法與乘法]
小弟依據裡面的概念寫了相同的[不限位數精準度的數值加法與乘法]
所謂的數值當然包含正整數與浮點數(負數部份有其它解決方案)
現在正要往減法與除法邁進,不過我想除法應該比較困難
所以想請問一下有沒有這方面的參考資料
謝謝
程式是人寫的,別讓工具的限制成為您想像力的極限
~程式中最重要的部份應該是註解而不是程式碼,這是因為解讀註解一定比解讀程式碼簡單
~程式寫好後約一個月就會忘的差不多了,所以花點時間把註解寫好至少能讓自己(或別人)看的懂當初在寫什麼

thyme

  • 老人組
  • 俺是博士!
  • *****
  • 文章數: 1281
    • 檢視個人資料
Re: 不限位數精準度的四則運算
« 回覆 #1 於: 2007-01-02 09:55 »
引述: "stlee"
前陣子把以前買來但是看不懂的書(買的時後以為看的懂)重翻了一遍,書名
叫做:C名題精選100則-碁峰出版,作者:先鏡光
其中的一個問題就是[不限位數精準度的正整數加法與乘法]
小弟依據裡面的概念寫了相同的[不限位數精準度的數值加法與乘法]
所謂的數值當然包含正整數與浮點數(負數部份有其它解決方案)
現在正要往減法與除法邁進,不過我想除法應該比較困難
所以想請問一下有沒有這方面的參考資料
謝謝


我很好奇,怎麼做出不限位數精準度的除法?

stlee

  • 鑽研的研究生
  • *****
  • 文章數: 817
    • 檢視個人資料
不限位數精準度的四則運算
« 回覆 #2 於: 2007-01-09 01:13 »
除法在今天剛搞定...但還沒測試;不過已經能將商數的位置正確填入

不限位數的除法其實並沒比加減乘法複雜
您用一張紙和筆就能辦到了(其實程式就是將在紙上的動作搬過去)
一個除法其實也就是乘法和減法的應用(求商數用到乘法,餘數用到減法)
而乘法也有用到加法(乘積相加);所以除法也就是加減乘法的綜合運用罷了
這四個運算的概念其實您只要回想一下小學時學過的技巧便能豁然開朗
程式的訴求是[不限位數]當然不能以一般字串轉數字函數達成
而是用[字串]將其逐[位元]作運算即可,難度在於能夠[填入正確的位置]
加法的重點在於[小數點位置標齊]及進位的數字處理(加法最多只能進位1)
乘法在加法完成後幾乎也完成[因為乘法的架構和加法相同]
減法的重點除[小數點位置標齊]及借位的問題外尤其是[小數點後面的借位]也是重點
除法在上面三個模組完成後要寫的並不多(除法必須有一個[精確度]的參數)
1.除數如果有小數點則須與被除數依同右移或補0的作業
2.商數的預測,如以456除123則先取456的4除123的1可得4再以[無限位乘法]以
4*123如大於餘數則4-1再乘123直到小於餘數傳回的值就是該位數的商
3.字串前面有0必須左移(減法造成)
4.餘數長度小於除數則須補位或補0也不可忽視
5.在補位或補0時商數也必須有相對動作也是個重點
..........除法因為剛好所以還有些重點我還在註解(測試)當中所以列一些目前有遇到的
以上大概就是我寫此程式的流程...先寫加法(不困難)再寫乘法(其實跟加法差不多)
不過當初沒注意到除法也要用到乘法所以改的要死...再寫減法(跟加法差不多的概念但被借位問題困惑了一陣子).....寫完上面3個再寫除法......大概就是這樣了
程式是人寫的,別讓工具的限制成為您想像力的極限
~程式中最重要的部份應該是註解而不是程式碼,這是因為解讀註解一定比解讀程式碼簡單
~程式寫好後約一個月就會忘的差不多了,所以花點時間把註解寫好至少能讓自己(或別人)看的懂當初在寫什麼

stlee

  • 鑽研的研究生
  • *****
  • 文章數: 817
    • 檢視個人資料
不限位數精準度的四則運算
« 回覆 #3 於: 2007-01-09 01:48 »
修正:乘法在加法完成後幾乎也完成[因為乘法的架構和加法相同]
乘法在加法完成後幾乎也完成[但外圍多一層迴路呼叫加法累加乘積並處理左移]
程式是人寫的,別讓工具的限制成為您想像力的極限
~程式中最重要的部份應該是註解而不是程式碼,這是因為解讀註解一定比解讀程式碼簡單
~程式寫好後約一個月就會忘的差不多了,所以花點時間把註解寫好至少能讓自己(或別人)看的懂當初在寫什麼

dean

  • 管理員
  • 俺是博士!
  • *****
  • 文章數: 1279
  • 性別: 男
  • 有些人,有些事,值得.
    • 檢視個人資料
不限位數精準度的四則運算
« 回覆 #4 於: 2007-01-09 03:22 »
用建構式數學的除法原理.

如要進行小數點運算的話,其商的預測也可使用建構式數學的除法原理解會比較簡單..
456 除 123
123*1=123 小於 456
123*2=246 小於 456
123*3=369 小於 456
123*4=492 大於 456,商為3,求餘數後進行小數點運算.

thyme

  • 老人組
  • 俺是博士!
  • *****
  • 文章數: 1281
    • 檢視個人資料
不限位數精準度的四則運算
« 回覆 #5 於: 2007-01-10 09:34 »
我在想,類似1/3的除法怎麼算出無限位數的結果,
原來是有「餘數」,以及「不限」位數,並不是「無限」位數 ;>

stlee

  • 鑽研的研究生
  • *****
  • 文章數: 817
    • 檢視個人資料
不限位數精準度的四則運算
« 回覆 #6 於: 2007-01-12 15:11 »
謝謝版主提供的辦法:用建構式數學的除法原理.
不過這將造成效能的問題:如餘數為100除數為99時將作9次的乘法
才能求到商數1的所要結果......
其實有一個辦法可加快商數的預測...其中有一個昨天測試時找到的bug
方法如下:
取餘數最高位除以除數最高位:如餘數為967,除數是234則取9除2得n
這樣迴路內只要從n*234開始:當乘積大於除數則減少n的值直到乘積小於234該n
即是所要的商數了;不過bug也在這裡:當餘數的最高位數值小於除數的最高位數值
如餘數101除數99時怎麼辦呢?
當時的想法是取第二位不過這又有另一個問題:程式是要求不限位數的所以如
除數是123456789遇到餘數是123456780這樣就會求出不正確的商數了
所以需加入一判斷其原型如下:
/*
進行比較兩字串的numcmp()不是標準函數的字串比較函數因為標準函數的字串
比較函數在遇到999和1000的字串時999是比1000大的,但數字999比1000小;
不過numcmp()也有用到標準函數memcmp()只不過需先標齊小數點位置後
(整數的小數點位置在個位數右邊一位)再以memcmp()比較後傳回memcmp()
的傳回值
*/

if( (x=numcmp(rem,divisor,maxlen)) < 0)
__return(0)/*該位的商數為0,返回呼叫者函數進行補位或補0*/
/*底下就是商數可能值的預測:通過numcmp()則rem已大於或等於divisor*/
if(x>0)
{
__if(*(divisor+0) >= *(rem+0))/*除數最高位>=餘數最高位*/
__{
____if(strlen(rem)==strlen(divisor))/*兩字串長度相同*/
______buf[0]='1';
____else
______buf[0]='9';/*將執行1~9次*/
__}
__else/*除數最高位<餘數最高位*/
__{
____bfs[0]=*(divisor+0);
____bfr[0]=*(rem+0);
____buf[0]=atoi(bfb)/atoi(bfa)+48;
__}
else/*x==0 rem字串與divisor字串相同*/
__buf[0]='1';
loopmax=atoi(buf);

底下就是進行乘法的迴路了;從上面的預測中最好的狀況下只要進行1次乘法
即可令乘積小於餘數而返回n值(商數);一般情況則最多兩次;最差的就是9次了
不過最差的情況要有一定條件(未補位前的餘數是一接近整除的值如10除9)所以
效能上並不會太差,不過應該還有更好的方法吧?只是我現在還不會

家裡的網路牽好了應該這幾天就可以將程式貼上來了到時希望各位能給予指教
還有一個問題是該程式有將近800行不知道應該一次貼上來還是分成函數個別
貼這點請版主給點意見
還有一個問題:貼上來的文章空白(前面的)都會被吃掉;所以縮排就有問題了這點該怎麼解決啊??
程式是人寫的,別讓工具的限制成為您想像力的極限
~程式中最重要的部份應該是註解而不是程式碼,這是因為解讀註解一定比解讀程式碼簡單
~程式寫好後約一個月就會忘的差不多了,所以花點時間把註解寫好至少能讓自己(或別人)看的懂當初在寫什麼

stlee

  • 鑽研的研究生
  • *****
  • 文章數: 817
    • 檢視個人資料
不限位數精準度的四則運算
« 回覆 #7 於: 2007-01-12 15:18 »
修正:buf[0]=atoi(bfa)/atoi(bfb)+48;
buf[0]=atoi(bfr)/atoi(bfs)+48;
不好意思!!沒看清楚又傳上來了
程式是人寫的,別讓工具的限制成為您想像力的極限
~程式中最重要的部份應該是註解而不是程式碼,這是因為解讀註解一定比解讀程式碼簡單
~程式寫好後約一個月就會忘的差不多了,所以花點時間把註解寫好至少能讓自己(或別人)看的懂當初在寫什麼

stlee

  • 鑽研的研究生
  • *****
  • 文章數: 817
    • 檢視個人資料
不限位數精準度的四則運算
« 回覆 #8 於: 2007-01-14 13:19 »
代碼: [選擇]

if( (x=numcmp(rem,divisor,maxlen)) < 0)
  return(0)/*該位的商數為0,返回呼叫者函數進行補位或補0*/
/*底下就是商數可能值的預測:通過numcmp()則rem已大於或等於divisor*/
if(x>0)
{
  if(*(divisor+0) >= *(rem+0))/*除數最高位>=餘數最高位*/
  {
    if(strlen(rem)==strlen(divisor))/*兩字串長度相同*/
      buf[0]='1';
    else
      buf[0]='9';/*將執行1~9次*/
  }
  else/*除數最高位<餘數最高位*/
  {
    bfs[0]=*(divisor+0);
    bfr[0]=*(rem+0);
    buf[0]=atoi(bfb)/atoi(bfa)+48;
  }
else/*x==0 rem字串與divisor字串相同*/
  buf[0]='1';
loopmax=atoi(buf);



...................
...................
程式是人寫的,別讓工具的限制成為您想像力的極限
~程式中最重要的部份應該是註解而不是程式碼,這是因為解讀註解一定比解讀程式碼簡單
~程式寫好後約一個月就會忘的差不多了,所以花點時間把註解寫好至少能讓自己(或別人)看的懂當初在寫什麼

stlee

  • 鑽研的研究生
  • *****
  • 文章數: 817
    • 檢視個人資料
Re: 不限位數精準度的四則運算
« 回覆 #9 於: 2013-02-09 01:49 »
除法在今天剛搞定...但還沒測試;不過已經能將商數的位置正確填入

不限位數的除法其實並沒比加減乘法複雜
您用一張紙和筆就能辦到了(其實程式就是將在紙上的動作搬過去)
一個除法其實也就是乘法和減法的應用(求商數用到乘法,餘數用到減法)
而乘法也有用到加法(乘積相加);所以除法也就是加減乘法的綜合運用罷了
這四個運算的概念其實您只要回想一下小學時學過的技巧便能豁然開朗
程式的訴求是[不限位數]當然不能以一般字串轉數字函數達成
而是用[字串]將其逐[位元]作運算即可,難度在於能夠[填入正確的位置]
加法的重點在於[小數點位置標齊]及進位的數字處理(加法最多只能進位1)
乘法在加法完成後幾乎也完成[因為乘法的架構和加法相同]
減法的重點除[小數點位置標齊]及借位的問題外尤其是[小數點後面的借位]也是重點
除法在上面三個模組完成後要寫的並不多(除法必須有一個[精確度]的參數)
1.除數如果有小數點則須與被除數依同右移或補0的作業
2.商數的預測,如以456除123則先取456的4除123的1可得4再以[無限位乘法]以
4*123如大於餘數則4-1再乘123直到小於餘數傳回的值就是該位數的商
3.字串前面有0必須左移(減法造成)
4.餘數長度小於除數則須補位或補0也不可忽視
5.在補位或補0時商數也必須有相對動作也是個重點
..........除法因為剛好所以還有些重點我還在註解(測試)當中所以列一些目前有遇到的
以上大概就是我寫此程式的流程...先寫加法(不困難)再寫乘法(其實跟加法差不多)
不過當初沒注意到除法也要用到乘法所以改的要死...再寫減法(跟加法差不多的概念但被借位問題困惑了一陣子).....寫完上面3個再寫除法......大概就是這樣了

好多年前的問題,最近有比較新的想法:
1.乘法就是加法的延伸,比如2*2即為把2加兩遍的意思,2*3就是把2加三遍,所以乘法函數就弄個迴路呼叫加法去算吧!
2.既然乘法是加法的延伸,那除法可不可以是減法的延伸呢?拿5來除2好了
第一次運算5-2=3商為1餘為3,餘數大於除數進入第二次運算
第二次運算3-2=1商加1(=2)餘為1,餘數小於除數停止運算
每減一次(運算一次減法)商數就加1,判斷餘數比除數大時就進入下一次運算並用現在的餘數去減除數直到餘數小於除數,不過還是必須先補位&補0
哈哈,還是兜回建構式數學了^_^
« 上次編輯: 2013-02-09 01:54 由 stlee »
程式是人寫的,別讓工具的限制成為您想像力的極限
~程式中最重要的部份應該是註解而不是程式碼,這是因為解讀註解一定比解讀程式碼簡單
~程式寫好後約一個月就會忘的差不多了,所以花點時間把註解寫好至少能讓自己(或別人)看的懂當初在寫什麼