1. Delphi K.Top 討論區
  2. 會員作品發表區(限本人創作發表)
  3. 無限長度數字(整數,小數)加減乘除運算
線上訂房服務-台灣趴趴狗聯合訂房中心
發文 回覆 瀏覽次數：4557
推到 Plurk!
推到 Facebook!

無限長度數字(整數,小數)加減乘除運算
 
way99
一般會員


發表：10
回覆：10
積分：4
註冊：2003-06-16

發送簡訊給我
#1 引用回覆 回覆 發表時間：2004-05-21 13:49:16 IP:140.125.xxx.xxx 未訂閱
因為在做無損失壓縮(Lossless Compression)時 有用到算術編碼(Arithmetic Coding)，所以需要用到一個很精確的小數運算， 但 float,double,long double 都無法達到我的要求，所以就用字串來自己做。 雖然做出來了，卻發生另一個很大的問題，就是在做大量運算時， 要花很多時間在字串處理上，所以這個也就沒辦法用了， 這個小程式就放出來給大家參考參考了。    使用方式也很簡單，例： Number n1 = -987.654; Number n2 = 123.456; Number n3 = n1 / n2; Caption=AnsiString(n3.sign) + n3.integer + "." + n3.fraction;    改了一下，除法長度改用設定位數的方式和乘除法小數改用四捨五入的方式    Number.h  
//---------------------------------------------------------------------------
#ifndef NumberH
#define NumberH
//---------------------------------------------------------------------------
#include     class Number
{
public:
  char sign;
  AnsiString integer;
  AnsiString fraction;      __fastcall Number();
  __fastcall Number(const double &d);        Number & __fastcall operator = (const Number & num);
    Number & __fastcall operator = (const double &d);      Number __fastcall operator   (const Number & num);
  Number __fastcall operator - (const Number & num);
  Number __fastcall operator * (const Number & num);
  Number __fastcall operator / (const Number & num);      int __fastcall compare(const Number & num);      bool __fastcall operator==(const Number & num)
  {
    return (sign == num.sign) &&
      (integer == num.integer) && (fraction == num.fraction);
  }
  bool __fastcall operator>(const Number & num)
  {
    return (compare(num) > 0);
  }
  bool __fastcall operator>=(const Number & num)
  {
    return (compare(num) >= 0);
  }
  bool __fastcall operator<(const Number & num)
  {
    return (compare(num) < 0);
  }
  bool __fastcall operator<=(const Number & num)
  {
    return (compare(num) <= 0);
  }
};    #endif
Number.cpp 
//---------------------------------------------------------------------------
#include 
#include 
#pragma hdrstop    #include "Number.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)    // 做乘法時 小數點第幾位
const int MulMaxLen = INT_MAX - 1;    // 做除法時 小數後第幾位
const int DivMaxLen = 25;    __fastcall Number::Number()
{
  sign = ' ';
  integer = "0";
  fraction = "0";
}
__fastcall Number::Number(const double &d)
{
  operator=(d);
}    Number & __fastcall Number::operator =(const Number & num)
{
  sign = num.sign;
  integer = num.integer;
  fraction = num.fraction;
  return *this;
}    Number & __fastcall Number::operator =(const double &d)
{
  double dd = d;
  sign = ' ';
  if(dd < 0)
  {
    sign = '-';
    dd = -dd;
  }
  __int64 i = dd;
  integer = i;
  dd = dd - i;
  if(dd > 0)
  {
    int i;
    fraction = "";
    do
    {
      dd *= 10;
      i = dd;
      fraction = fraction   AnsiString(i);
      dd = dd - i;
    }
    while(dd > 0);
  }
  else
    fraction = "0";
  return *this;
}    Number __fastcall Number::operator  (const Number & num)
{
  Number result;      if(sign == '-' && num.sign == ' ')
  {
    result = *this;
    result.sign = ' ';
    Number n = num;
    result = n - result;
    return result;
  }
  if(sign == ' ' && num.sign == '-')
  {
    result = num;
    result.sign = ' ';
    result = *this - result;
    return result;
  }
  if(sign == '-' && num.sign == '-')
  {
    result.sign = '-';
  }      int l0 = fraction.Length();
  int l1 = num.fraction.Length();
  int len = (l0 > l1) ? l0 : l1;
  result.fraction.SetLength(len);      int i, q, r, s = 0;
  for(i = len; i >= 1; i--)
  {
    q = (i <= l0) ? fraction[i] - '0' : 0;
    r = (i <= l1) ? num.fraction[i] - '0' : 0;
    s  = (q   r);
    q = s % 10;
    s /= 10;
    result.fraction[i] = '0'   q;
  }
  if(len >= 2 && result.fraction[len] == '0')
  {
    do
    {
      result.fraction[len] = ' ';
      len--;
    }
    while(len >= 2 && result.fraction[len] == '0');
    result.fraction = result.fraction.TrimRight();
  }
  //---------------------------
  l0 = integer.Length();
  l1 = num.integer.Length();
  i = len = ((l0 > l1) ? l0 : l1)   1;
  result.integer.SetLength(len);
  for(; i > 0; i--, l0--, l1--)
  {
    q = (l0 > 0) ? integer[l0] - '0' : 0;
    r = (l1 > 0) ? num.integer[l1] - '0' : 0;
    s  = (q   r);
    q = s % 10;
    s /= 10;
    result.integer[i] = '0'   q;
  }
  i = 1;
  if(i < len && result.integer[i] == '0')
  {
    do
    {
      result.integer[i] = ' ';
      i  ;
    }
    while(i < len && result.integer[i] == '0');
    result.integer = result.integer.TrimLeft();
  }      return result;
}    Number __fastcall Number::operator -(const Number & num)
{
  Number result;      if(sign == '-' && num.sign == ' ')
  {
    result = *this;
    result.sign = ' ';
    result = result   num;
    result.sign = '-';
    return result;
  }
  if(sign == ' ' && num.sign == '-')
  {
    result = num;
    result.sign = ' ';
    result = *this   result;
    return result;
  }
  if(sign == '-' && num.sign == '-')
  {
    result = *this;
    result.sign = ' ';
    Number n = num;
    n.sign = ' ';
    result = n - result;
    return result;
  }      int l0 = fraction.Length();
  int l1 = num.fraction.Length();
  int len = (l0 > l1) ? l0 : l1;
  result.fraction.SetLength(len);      int i, q, r, s = 0;
  for(i = len; i >= 1; i--)
  {
    q = (i <= l0) ? fraction[i] - '0' : 0;
    r = (i <= l1) ? num.fraction[i] - '0' : 0;
    s = 10   q - r   s;
    q = s % 10;
    s = (s / 10) - 1;
    result.fraction[i] = '0'   q;
  }
  if(len >= 2 && result.fraction[len] == '0')
  {
    do
    {
      result.fraction[len] = ' ';
      len--;
    }
    while(len >= 2 && result.fraction[len] == '0');
    result.fraction = result.fraction.TrimRight();
  }
  //---------------------------
  l0 = integer.Length();
  l1 = num.integer.Length();
  i = len = (l0 > l1) ? l0 : l1;
  result.integer.SetLength(len);
  for(; i > 0; i--, l0--, l1--)
  {
    q = (l0 > 0) ? integer[l0] - '0' : 0;
    r = (l1 > 0) ? num.integer[l1] - '0' : 0;
    s = 10   q - r   s;
    q = s % 10;
    s = (s / 10) - 1;
    result.integer[i] = '0'   q;
  }
  i = 1;
  if(i < len && result.integer[i] == '0')
  {
    do
    {
      result.integer[i] = ' ';
      i  ;
    }
    while(i < len && result.integer[i] == '0');
    result.integer = result.integer.TrimLeft();
  }      return result;
}    Number __fastcall Number::operator*(const Number & num)
{
  Number result;
  if(sign == '-' && num.sign == ' ')
  {
    result.sign = '-';
  }
  else if(sign == ' ' && num.sign == '-')
  {
    result.sign = '-';
  }      int div10 = 0;
  AnsiString n0, n1;      if(integer != "0")
    n0 = integer;
  if(fraction != "0")
  {
    n0 = n0   fraction;
    div10 = fraction.Length();
  }
  if(num.integer != "0")
    n1 = num.integer;
  if(num.fraction != "0")
  {
    n1 = n1   num.fraction;
    div10  = num.fraction.Length();
  }
  // n0==0 or n1==0 return 0.0
  if(n0 == "" || n1 == "")
    return result;      int l0 = n0.Length(), l1 = n1.Length();
  int len = l0   l1;
  int len0 = len;
  AnsiString n2;
  n2.SetLength(len);
  int i = 1;
  for(; i <= len; i  )
    n2[i] = '0';      // 確定 n0>=n1
  if(l0 < l1)
  {
    i = l0;
    l0 = l1;
    l1 = i;
    i = l0 - l1;
    AnsiString s;
    s.SetLength(i);
    for(; i > 0; i--)
      s[i] = '0';
    s = s   n0;
    n0 = n1;
    n1 = s;
  }
  else if(l0 == l1)
  {
    if(CompareStr(n0, n1) < 0)
    {
      AnsiString s = n0;
      n0 = n1;
      n1 = s;
    }
  }
  else
    //l0>l1
  {
    i = l0 - l1;
    AnsiString s;
    s.SetLength(i);
    for(; i > 0; i--)
      s[i] = '0';
    n1 = s   n1;
  }      int n2i;
  int cnt, qq, q, r, s, t;
  for(cnt = l1; cnt >= 1; cnt--, len--)
  {
    t = s = 0;
    qq = n1[l0 - (l1 - cnt)] - '0';
    for(n2i = len, i = l0; i >= 1; i--, n2i--)
    {
      r = n0[i] - '0';
      s = s   qq * r;
      q = s % 10;
      s = s / 10;          r = n2[n2i] - '0';
      t = t   q   r;
      q = t % 10;
      t = t / 10;          n2[n2i] = '0'   q;
    }
    t  = s;
    if(t != 0)
    {
      n2[n2i] = '0'   t;
    }
  }      s = len0 - div10;
  if(s)
    result.integer = n2.SubString(1, s);
  if(div10)
    result.fraction = n2.SubString(s   1, div10);      len = result.integer.Length();
  i = 1;
  if(i < len && result.integer[i] == '0')
  {
    do
    {
      result.integer[i] = ' ';
      i  ;
    }
    while(i < len && result.integer[i] == '0');
    result.integer = result.integer.TrimLeft();
  }      len = result.fraction.Length();
  // 設定小數點後的最長字串
  // 四捨五入
  if(len > MulMaxLen)
  {
    if(result.fraction[MulMaxLen   1] >= '5')
    {
      n0.SetLength(MulMaxLen);
      for(i = 1; i < MulMaxLen; i  )
        n0[i] = '0';
      n0[i] = '1';          Number v;
      v.fraction = n0;          result = result   v;
    }
    result.fraction.SetLength(MulMaxLen);
    len = MulMaxLen;
  }      if(len >= 2 && result.fraction[len] == '0')
  {
    do
    {
      result.fraction[len] = ' ';
      len--;
    }
    while(len >= 2 && result.fraction[len] == '0');
    result.fraction = result.fraction.TrimRight();
  }      return result;
}    int __fastcall Number::compare(const Number & num)
{
  if(sign == ' ' && num.sign == '-')
    return 1;
  if(sign == '-' && num.sign == ' ')
    return -1;      Number n0, n1;
  if(sign == ' ' && num.sign == ' ')
  {
    n0 = *this;
    n1 = num;
  }
  else
  {
    n0 = num;
    n1 = *this;
  }      int l0 = n0.integer.Length();
  int l1 = n1.integer.Length();
  if(l0 > l1)
    return 1;
  if(l0 < l1)
    return -1;      l0 = CompareStr(n0.integer, n1.integer);
  if(l0)
    return l0;      return CompareStr(n0.fraction, n1.fraction);
}    Number __fastcall Number::operator/(const Number & num)
{
  // N=0.0
  Number N;
  if(*this == N)
    return N;      if(N == num)
  {
    // 除以零!!!!!
    return N;
  }      N = 1.0;
  if(N == num)
  {
    return *this;
  }      int div10 = 0;
  int l0 = fraction.Length();
  int l1 = num.fraction.Length();      String s0, s1, tmp;
  if(integer != "0")
    s0 = integer;
  if(num.integer != "0")
    s1 = num.integer;      int i;
  if(l0 > l1)
  {
    i = l0 - l1;
    tmp.SetLength(i);
    for(; i >= 1; i--)
      tmp[i] = '0';
    s0 = s0   fraction;
    s1 = s1   num.fraction   tmp;
  }
  else if(l0 < l1)
  {
    i = l1 - l0;
    tmp.SetLength(i);
    for(; i >= 1; i--)
      tmp[i] = '0';
    s0 = s0   fraction   tmp;
    s1 = s1   num.fraction;
  }
  else
  {
    s0 = s0   fraction;
    s1 = s1   num.fraction;
  }      l0 = s0.Length();
  l1 = s1.Length();
  i = l0 - l1;
  if(i <= 0)
  {
    i = 1 - i;
    div10  = i;
    tmp.SetLength(i);
    for(; i >= 1; i--)
      tmp[i] = '0';
    s0 = s0   tmp;
  }
  else if(i >= 2)
  {
    i = i - 1;
    div10 -= i;
    tmp.SetLength(i);
    for(; i >= 1; i--)
      tmp[i] = '0';
    s1 = s1   tmp;
  }      Number n0, n1;
  n0.integer = s0;
  n1.integer = s1;      Number U(100.0);
  Number L(1.0);
  int l = 1, u = 100, d;
  Number D(1.0);
  Number v;      int len = DivMaxLen   s0.Length() - div10;
  // 用十分逼近法得到除法結果
  while(D.fraction.Length() < len)
  {
    d = u - l;
    if(d == 1)
    {
      u = 10;
      l = 0;
      d = 5;
      if(D.integer == "0")
      {
        D.fraction = "0"   D.fraction;
      }
      else
      {
        D.integer = "0";
        D.fraction = "1";
      }
    }
    else
    {
      // up 與 low 的中間值
      d /= 2;
    }        N = D * d;
    N = N   L;
    v = N * n1;        int cmp = v.compare(n0);
    if(cmp > 0)
    {
      U = N;
      u = d   l;
    }
    else if(cmp < 0)
    {
      L = N;
      l = d   l;
    }
    else
    {
      break;
    }
  }      // 將小數點位置 移到正確的位置
  // 可直接對 integer 和 fraction 字串做處理
  // 這裡我用偷懶的方法 直接用乘法做
  if(div10 > 0)
  {
    v = 0.1;
    do
    {
      N = N * v;
      div10--;
    }
    while(div10 > 0);
  }
  else if(div10 < 0)
  {
    v = 10;
    do
    {
      N = N * v;
      div10  ;
    }
    while(div10 < 0);
  }      // 四捨五入
  if(N.fraction.Length() > DivMaxLen)
  {
    if(N.fraction[DivMaxLen   1] >= '5')
    {
      s0.SetLength(DivMaxLen);
      for(i = 1; i < DivMaxLen; i  )
        s0[i] = '0';
      s0[i] = '1';          v = 0.0;
      v.fraction = s0;          N = N   v;
    }
    N.fraction.SetLength(DivMaxLen);
  }      len = N.fraction.Length();
  if(len >= 2 && N.fraction[len] == '0')
  {
    do
    {
      N.fraction[len] = ' ';
      len--;
    }
    while(len >= 2 && N.fraction[len] == '0');
    N.fraction = N.fraction.TrimRight();
  }      if(N.integer != "0" || N.fraction != "0")
    if(sign == '-' && num.sign == ' ')
    {
      N.sign = '-';
    }
    else if(sign == ' ' && num.sign == '-')
    {
      N.sign = '-';
    }      return N;
}
發表人 - way99 於 2004/05/21 13:51:17 發表人 - way99 於 2004/05/21 13:52:30 發表人 - way99 於 2004/05/21 18:45:18
領航天使
站長


發表：12216
回覆：4186
積分：4084
註冊：2001-07-25

發送簡訊給我
#2 引用回覆 回覆 發表時間：2004-05-22 06:48:54 IP:192.168.xxx.xxx 未訂閱
相關文章請見: 【討論】站長出個題目給大家寫寫:無限位數的加減乘除 ～～～Delphi K.Top討論區站長～～～
------
～～～Delphi K.Top討論區站長～～～
tokimeki
一般會員


發表：1
回覆：5
積分：1
註冊：2003-02-17

發送簡訊給我
#3 引用回覆 回覆 發表時間：2004-05-26 21:02:46 IP:218.162.xxx.xxx 未訂閱
我寫了一個BitList的容器，希望對你有幫助，程式碼我貼在 http://delphi.ktop.com.tw/topic.php?TOPIC_ID=47401 你可以教我算數編碼該怎麼寫嗎？ 原理與概念我懂，但不知道要使用何種資料結構來演算....
way99
一般會員


發表：10
回覆：10
積分：4
註冊：2003-06-16

發送簡訊給我
#4 引用回覆 回覆 發表時間：2004-05-27 14:56:42 IP:140.125.xxx.xxx 未訂閱
現在我又用 DWORD array 來存資料，加減乘已寫好了， 除法用個新的方法來做， 流程大概是： 被除數 DD / 除數 DN na = DN 第一個非零的 DWORD 值 nn = DD 前一個或二個的 DWORD 值 且 >= na R = nn/na S = R * DN DD -= S Result = R 重覆以上步驟直到被除數 DD == 0 (整除) 或 趨近於零(無法整除) Result 就是除法的結果了 速度比用String做快得很多。 算數編碼很難用幾句話能解釋清楚，你可以用google就可以找到一堆資料了。
chengwei
一般會員


發表：18
回覆：9
積分：5
註冊：2005-04-04

發送簡訊給我
#5 引用回覆 回覆 發表時間：2005-04-15 17:10:14 IP:163.28.xxx.xxx 未訂閱
可以post DWORD array 寫的"算術編碼"完整程式 , 供參考?
chengwei
一般會員


發表：18
回覆：9
積分：5
註冊：2005-04-04

發送簡訊給我
#6 引用回覆 回覆 發表時間：2005-04-18 15:05:10 IP:163.28.xxx.xxx 未訂閱
我用板上所附的"算術編碼"程式在bcb上compiler , n1,n2,n3要如何宣告?
系統時間：2024-05-15 2:42:18
聯絡我們 | Delphi K.Top討論版
本站聲明
1. 本論壇為無營利行為之開放平台，所有文章都是由網友自行張貼，如牽涉到法律糾紛一切與本站無關。
2. 假如網友發表之內容涉及侵權，而損及您的利益，請立即通知版主刪除。
3. 請勿批評中華民國元首及政府或批評各政黨，是藍是綠本站無權干涉，但這裡不是政治性論壇！
5151線上健康照護網 | 台灣西醫網 | 台灣中醫網 | 台灣牙科網 | 台灣照護網 | 趴趴狗旅遊網
大花蓮旅遊網 | 大花蓮民宿網 | 花蓮旅遊網 | 花蓮旅遊 | 花蓮旅遊 | 花蓮住宿
花蓮民宿網 | 花蓮旅遊 | 花蓮住宿 | 花蓮民宿 | 花蓮旅遊 | 花蓮民宿
花蓮住宿 | 大南投旅遊網 | 大南投民宿網 | 日月潭風景區 | 日月潭旅遊網 | 日月潭民宿網
日月潭住宿網 | 宜蘭旅遊網 | 宜蘭民宿網 | 宜蘭住宿網 | 宜蘭旅遊網 | 宜蘭民宿網
宜蘭住宿網 | 宜蘭旅遊網 | 宜蘭民宿網 | 宜蘭住宿網 | 台東旅遊網 | 台東民宿網
台東住宿網 | 台東旅遊網 | 台東民宿網 | 台東住宿網 | 台東旅遊 | 台東民宿
台東住宿 | 綠島旅遊網 | 綠島民宿網 | 綠島住宿網 | 綠島旅遊網 | 綠島民宿網
綠島住宿網 | 綠島旅遊網 | 綠島民宿網 | 綠島住宿網 | 集集旅遊網 | 集集民宿網
集集住宿網 | 關子嶺旅遊網 | 關子嶺民宿網 | 白河旅遊網 | 白河民宿網 | 心脈大師
尊榮牙醫診所 |