全國最多中醫師線上諮詢網站-台灣中醫網
發文 回覆 瀏覽次數:3527
推到 Plurk!
推到 Facebook!

無限長度數字運算【DWORD快速版】

 
way99
一般會員


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

發送簡訊給我
#1 引用回覆 回覆 發表時間:2004-05-28 23:24:45 IP:220.141.xxx.xxx 未訂閱
這次用 DWORD 為基本運算單位,比起之前用字串快很多, 除法也用了新的方法,也能加快運算速度 這次只提供 += -= *= /= 的operator,避免暫時的object被產生出來。
Number n1=99.999;
n1 /= 11.111l;
Caption = n1.toString();
toString()會用到之前的 StringNumber: http://delphi.ktop.com.tw/topic.php?TOPIC_ID=50498 Number.h
//---------------------------------------------------------------------------
#ifndef NumberH
#define NumberH
//---------------------------------------------------------------------------
#include     class Number
{
public:
  //String str; // for test      int sign;                     // 0 ==> ' '  or  1 ==> '-'
  int length;                   // length of data 
  DWORD *data;                  // integer[begin..begin icnt-1].fraction[begin icnt..begin icnt fcnt-1];
  int begin;                    // index of beginning
  int icnt, fcnt;               // counts of used DWORDs      __fastcall Number(void);
  __fastcall Number(int i);
  __fastcall Number(double d);
  __fastcall ~Number(void);      const Number & __fastcall operator=(const Number & num);
  const Number & __fastcall operator=(int i);
  const Number & __fastcall operator=(unsigned __int64 ui64);
  const Number & __fastcall operator=(double d);      void __fastcall operator =(const Number & num);
  void __fastcall operator-=(const Number & num);
  void __fastcall operator*=(const Number & num);
  void __fastcall operator/=(const Number & num);      void __fastcall operator =(int i);
  void __fastcall operator-=(int i);
  void __fastcall operator*=(int i);
  void __fastcall operator/=(int i);      void __fastcall operator =(double d);
  void __fastcall operator-=(double d);
  void __fastcall operator*=(double d);
  void __fastcall operator/=(double d);      bool isZero(void);
  AnsiString toString(void);      int __fastcall compare(const Number & num);
  bool __fastcall operator==(const Number & num);
  inline bool __fastcall operator>(const Number & num)
  {
    return (compare(num) > 0);
  }
  inline bool __fastcall operator>=(const Number & num)
  {
    return (compare(num) >= 0);
  }
  inline bool __fastcall operator<(const Number & num)
  {
    return (compare(num) < 0);
  }
  inline bool __fastcall operator<=(const Number & num)
  {
    return (compare(num) <= 0);
  }
};    #endif
Number.cpp
//---------------------------------------------------------------------------
#include 
#pragma hdrstop    #include "Number.h"
#include "StringNumber.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)    // 除法小數部份最多 DivMaxLen 個 DWORD
const int DivMaxLen = 20;    // new data 的基本長度單位
const int GrowthLen = 16;    __fastcall Number::Number(void)
{
  //  0.0
  sign = 0;
  length = GrowthLen;
  data = new DWORD[GrowthLen];
  //memset(data, 0, GrowthLen * sizeof(DWORD));
  data[0] = data[1] = 0;
  begin = 0;
  icnt = fcnt = 1;      //str = toString();
}    __fastcall Number::Number(int i)
{
  length = GrowthLen;
  data = new DWORD[GrowthLen];      operator=(i);      //str = toString();
}    __fastcall Number::Number(double d)
{
  length = GrowthLen;
  data = new DWORD[GrowthLen];      operator=(d);      //str = toString();
}    __fastcall Number::~Number(void)
{
  delete[]data;
}    const Number & __fastcall Number::operator=(const Number & num)
{
  sign = num.sign;
  if(length < num.length)
  {
    delete[]data;        length = num.length;
    data = new DWORD[length];
  }
  begin = num.begin;
  icnt = num.icnt;
  fcnt = num.fcnt;
  memcpy(data, num.data,
         (begin   icnt   fcnt) /* num.length */  * sizeof(DWORD));      //str = toString();
  return *this;
}    const Number & __fastcall Number::operator=(int i)
{
  memset(data, 0, length * sizeof(DWORD));      sign = 0;
  if(i < 0)
  {
    i = -i;
    sign = 1;
  }
  begin = 0;
  fcnt = 1;
  icnt = 1;
  data[0] = i;      //str = toString();
  return *this;
}    const Number & __fastcall Number::operator=(unsigned __int64 ui64)
{
  memset(data, 0, length * sizeof(DWORD));      sign = 0;
  begin = 0;
  fcnt = 1;      icnt = 0;
  DWORD *dw = (DWORD *) & ui64;
  if(dw[1] != 0)
  {
    data[0] = dw[1];
    icnt  ;
  }
  data[icnt] = dw[0];
  icnt  ;      //str = toString();
  return *this;
}    const Number & __fastcall Number::operator=(double d)
{
  memset(data, 0, length * sizeof(DWORD));      if(d == 0)
  {
    sign = 0;
    begin = 0;
    //data[0] = data[1] = 0;
    icnt = fcnt = 1;
    return *this;
  }      unsigned __int64 i = *(unsigned __int64 *)&d;      // IEEE Standard 754 Floating-Point
  // sign
  sign = i >> 63;
  i &= 0x7fffffffffffffff;      begin = 0;      int exp = (i >> 52) - 1023;   // Exponent
  i <<= 11;
  i |= 0x8000000000000000;      // Mantissa      // integer
  unsigned __int64 integer = i;
  integer >>= (63 - exp);      DWORD *dw = (DWORD *) & integer;
  icnt = 0;
  if(dw[1] != 0)
  {
    data[0] = dw[1];
    icnt  ;
  }
  data[icnt] = dw[0];
  icnt  ;      // fraction
  exp  ;
  if(exp > 0)
    i <<= exp;
  else if(exp < 0)
  {
    exp = -exp;
    i >>= exp;
  }      dw = (DWORD *) & i;
  fcnt = 1;
  data[icnt] = dw[1];
  if(dw[0] != 0)
  {
    data[icnt   1] = dw[0];
    fcnt  ;
  }      //str = toString();
  return *this;
}    int __fastcall Number::compare(const Number & num)
{
  register int cmp = sign - num.sign;
  if(cmp != 0)
    return -cmp;      int icnt0 = icnt, icnt1 = num.icnt;      // compare integer
  cmp = icnt0 - icnt1;
  if(cmp != 0)
    return cmp;      int beg0 = begin, beg1 = num.begin;
  DWORD *data0 = data, *data1 = num.data;      DWORD q, r;
  register int i0 = beg0, i1 = beg1;
  int len = beg0   icnt0;
  do
  {
    q = data0[i0];
    r = data1[i1];
    cmp = q - r;
    i0  ;
    i1  ;
  }
  while(i0 < len && cmp == 0);      // compare fraction
  if(cmp == 0)
  {
    int fcnt0 = fcnt, fcnt1 = num.fcnt;
    int l0 = beg0   icnt0   fcnt0;
    int l1 = beg1   icnt1   fcnt1;
    len = l0 > l1 ? l0 : l1;        // now i==beg icnt
    do
    {
      q = r = 0;
      if(i0 < l0)
        q = data0[i0];
      if(i1 < l1)
        r = data1[i1];
      cmp = q - r;
      i0  ;
      i1  ;
    }
    while(i0 < len && cmp == 0);
  }      if(cmp)
    if(q > r)
      cmp = 1;
    else
      cmp = -1;      if(sign)
    cmp = -cmp;      return cmp;
}    bool __fastcall Number::operator==(const Number & num)
{
  if(sign != num.sign || icnt != num.icnt || fcnt != num.fcnt)
    return false;      int i1 = icnt   fcnt - 1;
  int i2 = num.begin   i1;
  i1  = begin;      bool equal;
  do
  {
    equal = (data[i1] == num.data[i2]);
    i1--;
    i2--;
  }
  while(i1 >= begin && equal);
  return equal;
}    void __fastcall Number::operator =(const Number & num)
{
  if(sign   num.sign == 1)
    if(sign)                    // -this    num ==  num -  this
    {
      sign = 0;
      Number n = num;
      n -= *this;
      *this = n;
      return;
    }
    else                        //  this   -num ==  this -  num
    {
      Number n = num;
      n.sign = 0;
      operator-=(n);
      return;
    }      int il0 = icnt;
  int fl0 = fcnt;
  int il1 = num.icnt;
  int fl1 = num.fcnt;      int ticnt = il0 > il1 ? il0 : il1;
  int tfcnt = fl0 > fl1 ? fl0 : fl1;
  int tcnt = ticnt   tfcnt;      // 假設會進位
  int tlen = (((tcnt   1)   (GrowthLen - 1)) / GrowthLen) * GrowthLen;
  DWORD *tdata = new DWORD[tlen];
  //memset(tdata, 0, tlen * sizeof(DWORD));      unsigned __int64 n;
  bool trimFraction = true;      int beg0 = begin;
  int beg1 = num.begin;
  il0  = beg0;
  il1  = beg1;
  // set cnt
  fl0  = il0;
  fl1  = il1;
  // set index
  il0  = tfcnt;
  il1  = tfcnt;
  // set 進位
  n = 0;
  do
  {
    il0--;
    il1--;
    if(il0 >= beg0 && il0 < fl0)
      n  = data[il0];
    if(il1 >= beg1 && il1 < fl1)
      n  = num.data[il1];        tdata[tcnt] = n;
    if(tdata[tcnt] == 0 && trimFraction && tfcnt > 1)
      tfcnt--;
    else
      trimFraction = false;        tcnt--;        n >>= 32;
  }
  while(tcnt > 0);      begin = 1;
  // 有進位
  if((DWORD) n)
  {
    tdata[0] = 1;
    ticnt  ;
    begin = 0;
  }      delete[]data;      icnt = ticnt;
  fcnt = tfcnt;
  length = tlen;
  data = tdata;
  //str = toString();
}    void __fastcall Number::operator-=(const Number & num)
{
  if(sign)
  {
    if(num.sign == 0)           // -this -  num == -( this    num)
    {
      sign = 0;
      operator =(num);
      sign = 1;
      return;
    }
    else                        // -this - -num ==   num -  this
    {
      Number n = num;
      n.sign = 0;
      sign = 0;
      n -= *this;
      *this = n;
      return;
    }
  }
  else if(num.sign)             //  this - -num ==  this    num
  {
    Number n = num;
    n.sign = 0;
    operator =(n);
    return;
  }      // 確定是 大 - 小
  int cmp = compare(num);
  if(cmp == 0)
  {
    begin = 0;
    icnt = fcnt = 1;
    data[0] = data[1] = 0;
    return;
  }      DWORD *big, *small;
  int beg0, beg1;
  int il0, il1, fl0, fl1;
  if(cmp > 0)
  {
    big = this->data;
    small = num.data;
    beg0 = begin;
    beg1 = num.begin;
    il0 = icnt;
    il1 = num.icnt;
    fl0 = fcnt;
    fl1 = num.fcnt;
  }
  else
  {
    sign = (~sign) & 1;         // ' '->'-'  or  '-'->' '
    big = num.data;
    small = this->data;
    beg0 = num.begin;
    beg1 = begin;
    il0 = num.icnt;
    il1 = icnt;
    fl0 = num.fcnt;
    fl1 = fcnt;
  }      int ticnt = il0 > il1 ? il0 : il1;
  int tfcnt = fl0 > fl1 ? fl0 : fl1;
  int tcnt = ticnt   tfcnt;      int tlen = ((tcnt   (GrowthLen - 1)) / GrowthLen) * GrowthLen;
  DWORD *tdata = new DWORD[tlen];
  //memset(tdata, 0, tlen * sizeof(DWORD));      unsigned __int64 n;
  bool trimFraction = true;
  il0  = beg0;
  il1  = beg1;
  // set cnt
  fl0  = il0;
  fl1  = il1;
  // set index
  il0  = tfcnt;
  il1  = tfcnt;
  // set 借位
  DWORD borrow = 0;
  do
  {
    il0--;
    il1--;
    n = 0x100000000;
    if(il0 >= beg0 && il0 < fl0)
      n  = big[il0];        n -= borrow;        if(il1 >= beg1 && il1 < fl1)
      n -= small[il1];        tcnt--;
    tdata[tcnt] = n;        if(trimFraction && tdata[tcnt] == 0 && tfcnt > 1)
      tfcnt--;
    else
      trimFraction = false;        borrow = 0;
    if(((DWORD) (n >> 32) & 1) == 0)
      borrow  ;
  }
  while(tcnt > 0);      // trim integer
  begin = 0;
  while(ticnt > 1 && tdata[begin] == 0)
  {
    begin  ;
    ticnt--;
  }      delete[]data;      icnt = ticnt;
  fcnt = tfcnt;
  length = tlen;
  data = tdata;
  //str = toString();
}    void __fastcall Number::operator*=(const Number & num)
{
  int il0 = icnt;
  int fl0 = fcnt;
  int il1 = num.icnt;
  int fl1 = num.fcnt;      DWORD *lon = data;
  DWORD *sho = num.data;      int beg0 = begin;
  int end0 = beg0   il0   fl0 - 1;
  if(lon[beg0] == 0)
  {
    beg0  ;
    il0--;
  }
  if(lon[end0] == 0)
  {
    end0--;
    fl0--;
  }
  if(beg0 > end0)               // *this==0.0
  {
    return;
  }      int beg1 = num.begin;
  int end1 = beg1   il1   fl1 - 1;
  if(sho[beg1] == 0)
  {
    beg1  ;
    il1--;
  }
  if(sho[end1] == 0)
  {
    end1--;
    fl1--;
  }
  if(beg1 > end1)               // num==0.0
  {
    sign = 0;
    begin = 0;
    icnt = fcnt = 1;
    lon[0] = lon[1] = 0;
    return;
  }      int cnt0 = il0   fl0;
  int cnt1 = il1   fl1;
  int tcnt = cnt0   cnt1;
  int tcnt1 = tcnt;      int tlen = (((tcnt   2)   (GrowthLen - 1)) / GrowthLen) * GrowthLen;
  DWORD *tdata = new DWORD[tlen];
  memset(tdata, 0, tlen * sizeof(DWORD));      // 結果 = 被乘數 * 乘數
  if(cnt1 > cnt0)
  {
    lon = sho;
    sho = data;        int tmp = beg0;
    beg0 = beg1;
    beg1 = tmp;        tmp = end0;
    end0 = end1;
    end1 = tmp;
  }      unsigned __int64 n, nn;
  do
  {
    nn = 0;
    if(sho[end1] != 0)
    {
      n = sho[end1];          // set tdata index
      cnt0 = tcnt;
      cnt1 = end0;
      do
      {
        nn  = n * lon[cnt1];
        nn  = tdata[cnt0];
        tdata[cnt0] = nn;
        nn >>= 32;            cnt0--;
        cnt1--;
      }
      while(cnt1 >= beg0);
      tdata[cnt0] = nn;
    }
    else
      cnt0 = tcnt - (end0 - beg0   1);        tcnt--;
    end1--;
  }
  while(end1 >= beg1);      icnt = il0   il1;
  fcnt = fl0   fl1;
  if(icnt == 0)
  {
    icnt  ;
    cnt0--;
    if(tdata[tcnt1] == 0)
    {
      fcnt--;
    }
  }
  else if(fcnt == 0)
  {
    fcnt  ;
  }      begin = cnt0;
  if((DWORD) nn == 0 && icnt > 1)
  {
    begin  ;
    icnt--;
  }      delete[]data;      length = tlen;
  data = tdata;
  sign ^= num.sign;      //str = toString();
}    Number ZERO;
Number Divisor, M, Q, S, R, M1, Result;
void __fastcall Number::operator/=(const Number & num)
{
  if(isZero())
    return;
  // avoid warning
  if(((Number *) (&num))->isZero())
  {
    // 除以零!!!
    throw new EDivByZero("Division by Zero");
    //return;
  }      // M=1.0, Q=0x0.00000001;
  M = 1;
  Result = Q = ZERO;
  Q.data[1] = 1;      int newsign = sign ^ num.sign;
  sign = 0;
  Divisor = num;
  Divisor.sign = 0;      int icnt0 = icnt, icnt1 = Divisor.icnt;
  if(data[begin] == 0)
    icnt0--;      // 取得 Divisor 第一個非零的數字
  int idx = Divisor.begin;
  unsigned __int64 nn, na, na1;
  na = Divisor.data[idx];
  if((DWORD) na == 0)
  {
    do
    {
      idx  ;
      na = Divisor.data[idx];
      icnt1--;
    }
    while((DWORD) na == 0);
  }
  na1 = na   1;      if(icnt0 > icnt1)
  {
    S = (unsigned __int64)0x100000000;
    do
    {
      M *= S;                   // M<<=32
      icnt1  ;
    }
    while(icnt0 > icnt1);
  }
  else if(icnt0 < icnt1)
  {
    do
    {
      M *= Q;                   // M>>=32
      icnt1--;
    }
    while(icnt0 < icnt1);
  }      int beg, len, idx0, idx1;
  idx = -icnt0;
  do
  {
    beg = begin   icnt;
    len = beg   fcnt;        //暫存起來
    idx0 = idx;
    M1 = M;        idx1 = beg   idx;
    nn = data[idx1];
    if(nn < na)
      do
      {
        idx  ;
        idx1  ;
        nn <<= 32;
        if(idx1 < len)
          nn  = data[idx1];            M *= Q;
      }
      while(nn < na);
    R = nn / na;
    R *= M;
    S = Divisor;
    S *= R;        if(compare(S) < 0)
    {
      idx = idx0;
      M = M1;          idx1 = beg   idx;
      nn = data[idx1];
      if(nn < na1)
        do
        {
          idx  ;
          idx1  ;
          nn <<= 32;
          if(idx1 < len)
            nn  = data[idx1];              M *= Q;
        }
        while(nn < na1);
      R = nn / na1;
      R *= M;
      S = Divisor;
      S *= R;
    }        operator-=(S);
    Result  = R;
  }
  while(!isZero() && Result.fcnt <= DivMaxLen);
  //     ==0(整除)   ~=0(無法整除)      operator=(Result);
  sign = newsign;      //str = toString();
}    bool Number::isZero(void)
{
  int idx = begin;
  if(icnt == 1 && data[idx] == 0)
  {
    idx  ;
    if(fcnt == 1 && data[idx] == 0)
      return true;
  }
  return false;
}    AnsiString Number::toString(void)
{
  StringNumber snum;
  StringNumber two = 2.0;
  StringNumber n = 1.0;
  int i, j;
  DWORD dw;
  // integer
  for(i = begin   icnt - 1; i >= begin; i--)
  {
    dw = data[i];
    for(j = 0; j < 32; j  )
    {
      if(dw & 1)
        snum = snum   n;
      dw >>= 1;
      n = n * two;
    }
  }      // fraction
  n = two = 0.5;
  int k = begin   icnt;
  for(i = fcnt; i > 0; i--, k  )
  {
    dw = data[k];
    for(j = 0; j < 32; j  )
    {
      if(dw & 0x80000000)
        snum = snum   n;
      dw <<= 1;
      n = n * two;
    }
  }      if(sign)
    snum.sign = '-';
  return snum.toString();
}    Number TmpNum;
void __fastcall Number::operator =(int i)
{
  TmpNum = i;
  operator =(TmpNum);
}
void __fastcall Number::operator-=(int i)
{
  TmpNum = i;
  operator-=(TmpNum);
}
void __fastcall Number::operator*=(int i)
{
  TmpNum = i;
  operator*=(TmpNum);
}
void __fastcall Number::operator/=(int i)
{
  TmpNum = i;
  operator/=(TmpNum);
}    void __fastcall Number::operator =(double d)
{
  TmpNum = d;
  operator =(TmpNum);
}
void __fastcall Number::operator-=(double d)
{
  TmpNum = d;
  operator-=(TmpNum);
}
void __fastcall Number::operator*=(double d)
{
  TmpNum = d;
  operator*=(TmpNum);
}
void __fastcall Number::operator/=(double d)
{
  TmpNum = d;
  operator/=(TmpNum);
}
系統時間:2024-04-26 15:50:34
聯絡我們 | Delphi K.Top討論版
本站聲明
1. 本論壇為無營利行為之開放平台,所有文章都是由網友自行張貼,如牽涉到法律糾紛一切與本站無關。
2. 假如網友發表之內容涉及侵權,而損及您的利益,請立即通知版主刪除。
3. 請勿批評中華民國元首及政府或批評各政黨,是藍是綠本站無權干涉,但這裡不是政治性論壇!