花了点时间写了这么个东西，目前只支持正整数的运算。
还有很多重要的功能，如素性的检测等还没有完成。
增加了负数 --20060823
decnum.h
#include <stdio.h>
#include <math.h>
#include <iostream>
using namespace std;
class decnum
{
friend decnum pow(const decnum& x, int n);
friend decnum root(const decnum& x, int n);
friend decnum div(const decnum& x, const decnum& y, decnum& r);
friend decnum abs(const decnum& x);
friend bool operator==(const decnum& x, const decnum&y);
friend bool operator!=(const decnum& x, const decnum&y);
friend bool operator>(const decnum& x, const decnum&y);
friend bool operator<(const decnum& x, const decnum&y);
friend bool operator>=(const decnum& x, const decnum&y);
friend bool operator<=(const decnum& x, const decnum&y);
friend ostream& operator<<(ostream&os, const decnum& x);
public:
decnum() : cap(0), num(0), sign(0), val(NULL) { }
decnum(const char *v, int n)
{
int i, j;
val = new char[n];
if(v[0] == '-') {
sign = 1;
v++;
n--;
}
else {
sign = 0;
if(v[0] == '+')
v++;
}
for(i = 0; i < n && v == '0'; i++);
for(j=0; i<n; i++, j++)
if(v[n-1-i] >= '0' && v[n-1-i] <= '9')
val[j] = v[n-1-i] - '0';
else
break;
num = j;
cap = n;
}
decnum(const decnum& x)
{
val = new char[x.num];
memcpy(val, x.val, x.num);
sign = x.sign;
num = x.num;
cap = x.num;
}
decnum(int x)
{
if(x==0) {
cap = num = 0;
val = NULL;
return;
}
if(x < 0) {
sign = 1;
x = -x;
}
else
sign = 0;
char temp[20];
sprintf(temp, "%d", x);
int n = strlen(temp);
num = cap = n;
val = new char[n];
for(int i=0; i<n; i++)
val = temp[n-1-i] - '0';
}
decnum(long long x)
{
if(x==0) {
cap = num = 0;
val = NULL;
return;
}
if(x < 0) {
sign = 1;
x = -x;
}
else
sign = 0;
char temp[20];
sprintf(temp, "%lld", x);
int n = strlen(temp);
num = cap = n;
val = new char[n];
for(int i=0; i<n; i++)
val = temp[n-1-i] - '0';
}
~decnum() { delete[] val; }
int size() const { return num; }
decnum&
operator=(const decnum& x)
{
if (this != &x) {
if(cap < x.num) {
delete[] val;
val = new char[x.num];
cap = x.num;
}
memcpy(val, x.val, x.num);
num = x.num;
sign = x.sign;
}
return *this;
}
decnum&
operator=(int x)
{
*this = decnum(x);
return *this;
}
decnum&
operator=(long long x)
{
*this = decnum(x);
return *this;
}
decnum& abs()
{
sign = 0;
return *this;
}
decnum& operator+=(const decnum& x);
decnum& operator-=(const decnum& x);
decnum& operator*=(const decnum& x);
decnum& operator/=(const decnum& x);
decnum& operator%=(const decnum& x);
decnum operator+(const decnum& x) const;
decnum operator-(const decnum& x) const;
decnum operator*(const decnum& x) const;
decnum operator/(const decnum& x) const;
decnum operator%(const decnum& x) const;
bool ispow(int n, decnum& r) const;
bool ispow() const;
private:
int cap;
int num;
int sign;
char *val;
private:
char root_1(int n);
decnum& absadd(const decnum& x);
decnum& abssub(const decnum& x);
bool absge(const decnum& x);
};
decnum.cpp
#include "decnum.h"
decnum&
decnum::absadd(const decnum& x)
{
int i, max;
char carry = 0, ch;
if(x.num == 0) return *this;
if(num < x.num)
max = x.num + 1;
else
max = num + 1;
if(max > cap)
{
cap = max;
char *newval = new char[cap];
memcpy(newval, val, num);
memset(newval+num, 0, cap - num);
delete[] val;
val = newval;
}
else
{
memset(val+num, 0, max - num);
}
num = max-1;
for(i=0; i<x.num; i++) {
ch = val + x.val + carry;
if(ch > 9) {
carry = 1;
val = ch - 10;
}
else {
carry = 0;
val = ch;
}
}
for(; i<=num && carry == 1; i++) {
ch = val + 1;
if(ch > 9) {
carry = 1;
val = ch - 10;
}
else {
carry = 0;
val = ch;
}
}
if(i>num) num = i;
return *this;
}
decnum&
decnum::abssub(const decnum& x)
{
if(x.num == 0) return *this;
int i;
char carry = 0, ch;
for(i=0; i<x.num; i++) {
ch = val - x.val - carry;
if(ch < 0) {
carry = 1;
val = ch + 10;
}
else {
carry = 0;
val = ch;
}
}
for(; i<num && carry == 1; i++) {
ch = val - 1;
if(ch < 0) {
carry = 1;
val = ch + 10;
}
else {
carry = 0;
val = ch;
}
}
for(i=num; i>0 && val[i-1] == 0; i--);
num = i;
return *this;
}
bool
decnum::absge(const decnum& x)
{
if(num > x.num) return true;
if(num < x.num) return false;
for(int i=num-1; i >= 0; i--)
if(val > x.val)
return true;
else if(val < x.val)
return false;
return true;
}
decnum&
decnum::operator+=(const decnum& x)
{
if(x.sign == sign)
return absadd(x);
else if(absge(x))
return abssub(x);
else {
decnum tmp(*this);
*this = x;
return abssub(tmp);
}
}
decnum&
decnum::operator-=(const decnum& x)
{
if(x.sign != sign)
return absadd(x);
else if(absge(x))
return abssub(x);
else {
decnum tmp(*this);
*this = x;
return abssub(tmp);
}
}
decnum&
decnum::operator*=(const decnum& x)
{
if(num == 0) return *this;
if(x.num == 0) {
num = 0;
return *this;
}
if(sign == x.sign)
sign = 0;
else
sign = 1;
int mul, i, n, newcap, max;
char ch, carry;
char *newval = new char[num + x.num];
newcap = num + x.num;
memset(newval, 0, num + x.num);
decnum a, b;
char *ptr;
for(i=0; i<num && val == 0; i++);
int na = i;
a.val = val + i;
a.num = num - i;
for(i=0; i<num && x.val == 0; i++);
int nb = i;
b.val = x.val + i;
b.num = x.num - i;
ptr = newval + na + nb;
for(n=0; n <= a.num + b.num - 2; n++) {
mul = 0;
if(n > b.num - 1)
i = n - b.num + 1;
else
i=0;
max = n < a.num-1 ? n : a.num-1;
for(; i<=max; i++)
mul += a.val*b.val[n-i];
carry = 0;
for(i=n; mul > 0 || carry > 0; mul /= 10, i++) {
ch = ptr + mul % 10 + carry;
if(ch > 9) {
carry = 1;
ptr = ch - 10;
}
else
{
carry = 0;
ptr = ch;
}
}
}
for(i=a.num + b.num; i>0 && ptr[i-1] == 0; i--);
num = i + na + nb;
if(cap >= num) {
memcpy(val, newval, num);
delete[] newval;
}
else {
cap = newcap;
delete[] val;
val = newval;
}
a.val = b.val = NULL;
return *this;
}
decnum&
decnum::operator/=(const decnum& x)
{
char ch, carry, fac;
decnum tmp;
int i;
if(x.num == 0) return *this;
if(num < x.num) {
num = 0;
return *this;
}
if(sign == x.sign)
sign = 0;
else
sign = 1;
char *newval = new char[num - x.num + 1];
memset(newval, 0, num - x.num + 1);
carry = 0;
fac = x.val[x.num-1] + 1;
tmp.val = val + num - x.num + 1;
tmp.cap = tmp.num = x.num -1;
for(i=num-1; i>= x.num-1; i--) {
tmp.val--;
tmp.num++;
ch = (carry * 10 + val) / fac;
tmp -= x * ch;
while(tmp >= x) {
tmp -= x;
ch++;
}
newval[i-x.num+1] = ch;
carry = val;
}
tmp.val = NULL;
for(i=num-x.num+1; i>0 && newval[i-1] == 0; i--);
num = i;
delete[] val;
val = newval;
return *this;
}
decnum&
decnum::operator%=(const decnum& x)
{
char ch, carry, fac;
decnum tmp;
int i;
if(x.num == 0) return *this;
if(num < x.num) return *this;
carry = 0;
fac = x.val[x.num-1] + 1;
tmp.val = val + num - x.num + 1;
tmp.num = x.num - 1;
for(i=num-1; i>= x.num-1; i--) {
tmp.val--;
tmp.num++;
ch = (carry * 10 + val) / fac;
tmp -= x * ch;
while(tmp >= x) {
tmp -= x;
ch++;
}
carry = val;
}
tmp.val = NULL;
num = tmp.num;
return *this;
}
decnum
decnum::operator+(const decnum& x) const
{
decnum tmp = *this;
return tmp += x;
}
decnum
decnum::operator-(const decnum& x) const
{
decnum tmp = *this;
return tmp -= x;
}
decnum
decnum::operator*(const decnum& x) const
{
decnum tmp = *this;
return tmp *= x;
}
decnum
decnum::operator/(const decnum& x) const
{
decnum tmp = *this;
return tmp /= x;
}
decnum
decnum::operator%(const decnum& x) const
{
decnum tmp = *this;
return tmp %= x;
}
decnum abs(const decnum& x)
{
decnum tmp(x);
tmp.sign = 0;
return tmp;
}
decnum pow(const decnum& x, int n)
{
decnum tmp(1), fac(x);
for(; n>0; n>>=1) {
if(n&0x01)
tmp *= fac;
fac *= fac;
}
return tmp;
}
char decnum::root_1(int n)
{
char r = (int)(pow(1+val[num-1], 1.0/n) * pow(10,(num-1.0)/n));
for(; r>0 && pow(decnum(r), n) > *this; r--);
return r;
}
bool decnum::ispow(int n, decnum& r) const
{
if(num == 0) {
r.num = 0;
return true;
}
if(sign == 1 && (n&1 == 0)) {
r.num = 0;
return false;
}
decnum tmp, p;
r.cap = r.num = (num+n-1) / n;
r.val = new char[r.num];
r.sign = sign;
memset(r.val, 0, r.num);
tmp.val = val + (r.num-1)*n;
tmp.num = num - (r.num-1)*n;
r.val[r.num-1] = tmp.root_1(n);
tmp.val = new char[r.num+1];
tmp.cap = r.num+1;
int v;
p = pow(r, n);
if(p == *this) return true;
for(int i=r.num-2; i>=0; i--) {
memset(tmp.val, 0, i+1);
tmp.val = 1;
tmp.num = i+1;
tmp += r;
p = (*this - p) / (pow(tmp, n) - p);
if(p.num > 1)
v = 9;
else if(p.num > 0)
v = p.val[0];
else
v = 0;
for(; v>=0; v--) {
r.val = v;
p = pow(r, n);
if(p == *this)
return true;
if(p < *this)
break;
}
}
return false;
}
bool decnum::ispow() const
{
decnum r, dec2("2", 1);
if(ispow(2, r)) return true;
for(int n=3; r > dec2; n+=2) {
if(ispow(n, r)) return true;
}
return false;
}
decnum
root(const decnum& x, int n)
{
decnum r;
x.ispow(n, r);
return r;
}
decnum
div(const decnum& x, const decnum& y, decnum& r)
{
char ch, carry, fac;
decnum d = x, tmp;
int i;
if(y.num == 0) return x;
if(d.num < y.num) {
r = x;
d = 0;
return d;
}
char *newval = new char[d.num - y.num + 1];
memset(newval, 0, d.num - y.num + 1);
carry = 0;
fac = y.val[y.num-1] + 1;
tmp.val = d.val + d.num - y.num + 1;
tmp.num = y.num - 1;
for(i=d.num-1; i>= y.num-1; i--) {
tmp.val--;
tmp.num++;
ch = (carry * 10 + d.val) / fac;
tmp -= y * ch;
while(tmp >= y) {
tmp -= y;
ch++;
}
newval[i-y.num+1] = ch;
carry = d.val;
}
r = tmp;
tmp.val = NULL;
for(i=d.num-y.num+1; i>0 && newval[i-1] == 0; i--);
d.num = i;
delete[] d.val;
d.val = newval;
return d;
}
bool operator==(const decnum& x, const decnum&y)
{
if(x.sign != y.sign) return false;
if(x.num != y.num) return false;
for(int i=0; i < x.num; i++)
if(x.val != y.val)
return false;
return true;
}
bool operator!=(const decnum& x, const decnum&y)
{
return !(x==y);
}
bool operator>(const decnum& x, const decnum&y)
{
if(x.sign > y.sign) return false;
if(x.sign < y.sign) return true;
bool retval = (x.sign == 0);
if(x.num > y.num) return retval;
if(x.num < y.num) return !retval;
for(int i=x.num-1; i >= 0; i--)
if(x.val > y.val)
return retval;
else if(x.val < y.val)
return !retval;
return false;
}
bool operator<(const decnum& x, const decnum&y)
{
return y > x;
}
bool operator>=(const decnum& x, const decnum&y)
{
if(x.sign > y.sign) return false;
if(x.sign < y.sign) return true;
bool retval = (x.sign == 0);
if(x.num > y.num) return retval;
if(x.num < y.num) return !retval;
for(int i=x.num-1; i >= 0; i--)
if(x.val > y.val)
return retval;
else if(x.val < y.val)
return !retval;
return true;
}
bool operator<=(const decnum& x, const decnum&y)
{
return y >= x;
}
ostream& operator<<(ostream&os, const decnum& x)
{
if(x.size() == 0)
os << 0;
else {
if(x.sign == 1)
os << "-";
for(int i = x.size()-1; i>=0; i--)
os << (int)x.val;
}
return os;
}
[ 本帖最后由 yuxh 于 2006-8-23 18:11 编辑 ]
flw 回复于：2006-08-18 13:16:14
传说中的沙发？
zengjin8310 回复于：2006-08-18 13:18:14
8错， 对我搞科学计算有用， 测试过效率么？
zengjin8310 回复于：2006-08-18 13:21:30
最好再加上超高精度的浮点数的混合运算支持
yuxh 回复于：2006-08-18 13:26:58
这个本来是为大素数的测试用的，这些是要用到的基本运算
可惜我的工作与加密算法无关，纯粹是业余爱好，代码也是业余水平的。
就效率而言，比较慢的就是求n次方根这个了：
root(x, n)
设x有m位，则算法应该是O(m^3*log(m)/n)的
检测一个数是否是某个数的整数次幂:
ispow()
这个就差不多是O(m^3*log(m)^2)的了
[ 本帖最后由 yuxh 于 2006-8-22 11:17 编辑 ]
默难 回复于：2006-08-18 15:00:41
支持原创
顶一下吧
aple_smx 回复于：2006-08-19 15:25:25
come on
mirnshi 回复于：2006-08-21 15:02:15
接口为10进制, 内部的进制采用unsigned long或unsigned short，是不是更能借助逻辑运算，提高效率？
hqxyn 回复于：2006-08-22 10:29:15
来凑凑热闹
decimal.h
/***************************************************************************
decimal.h - description
-------------------
begin : Wed Jan 9 2002
copyright : (C) 2002 by Xian Yining
email : [email]hqxyn@yahoo.com.cn[/email]
***************************************************************************/
/***************************************************************************
* *
* This program is free software; you can redistribute it and/or modify *
* it under the terms of the GNU General Public License as published by *
* the Free Software Foundation; either version 2 of the License, or *
* (at your option) any later version. *
* *
***************************************************************************/
#ifndef DECIMAL_H
#define DECIMAL_H
#ifndef __USE_GNU
#define __USE_GNU
#endif
/*
#ifndef __USE_ISOC99
#define __USE_ISOC99
#endif
*/
#include <typeinfo>
#include <iostream>
#include <string>
#include <limits>
const unsigned DECIMAL_DEFAULT_PRE = 20,DECIMAL_DEFAULT_DEC = 6;
class decimal
{
public :
enum Sign {PLUS=1,MINUS=-1};
enum Stat {NOINIT=-1,OK,UPFLOW,DOWNFLOW,OVERDIGITS};
enum Pre {DOUBLE_PRECISION=std::numeric_limits<double>::digits10,LDOUBLE_PRECISION=std::numeric_limits<long double>::digits10};
//构造函数
decimal(void):sn(PLUS),val("0"),exp(0),st(OK),pre(DECIMAL_DEFAULT_PRE),dec(DECIMAL_DEFAULT_DEC) {}
decimal(const std::string &,const unsigned int p=DECIMAL_DEFAULT_PRE,const unsigned int d=DECIMAL_DEFAULT_DEC) ;
decimal(const char* cstr,const unsigned int p=DECIMAL_DEFAULT_PRE,const unsigned int d=DECIMAL_DEFAULT_DEC) ;
decimal(const int,const unsigned int p=DECIMAL_DEFAULT_PRE,const unsigned int d=DECIMAL_DEFAULT_DEC) ;
decimal(const unsigned int,const unsigned int p=DECIMAL_DEFAULT_PRE,const unsigned int d=DECIMAL_DEFAULT_DEC) ;
decimal(const long,const unsigned int p=DECIMAL_DEFAULT_PRE,const unsigned int d=DECIMAL_DEFAULT_DEC) ;
decimal(const long long,const unsigned int p=DECIMAL_DEFAULT_PRE,const unsigned int d=DECIMAL_DEFAULT_DEC) ;
decimal(const unsigned long,const unsigned int p=DECIMAL_DEFAULT_PRE,const unsigned int d=DECIMAL_DEFAULT_DEC) ;
decimal(const unsigned long long,const unsigned int p=DECIMAL_DEFAULT_PRE,const unsigned int d=DECIMAL_DEFAULT_DEC) ;
decimal(const double,const unsigned int p=DECIMAL_DEFAULT_PRE,const unsigned int d=DECIMAL_DEFAULT_DEC) ;
decimal(const long double,const unsigned int p=DECIMAL_DEFAULT_PRE,const unsigned int d=DECIMAL_DEFAULT_DEC) ;
decimal(const decimal& d):sn(d.sn),val(d.val),exp(d.exp),st(d.st),pre(d.pre),dec(d.dec) {}
virtual ~decimal(){}
//赋值
decimal& operator=(const decimal&) ;
//算术运算
decimal& operator +=(const decimal&) ;
decimal& operator -=(const decimal&) ;
decimal& operator *=(const decimal&) ;
decimal& operator /=(const decimal&) ;
// decimal& operator %=(const decimal&) ;
//比较运算符
bool le(const decimal&) const ;
bool eq(const decimal&) const ;
bool gt(const decimal&) const ;
decimal& operator-(void) {sn=((sn==PLUS)?MINUS:PLUS);return *this;}
decimal& operator+(void) {return *this;}
//杂项函数
virtual std::string toString() const;
virtual std::string toShortStr() const;
virtual std::string toString(const unsigned int len,const int de) const;
//在len长度内转为十进小数字符串，超常则返回‘＊’串
virtual std::string toEString(const unsigned int len=0) const; //在len长度内转为科学表示法字符串，超常则返回‘＊’串
bool ok() const {return (st==OK)?true:false;} //数字是否有效
bool zero() const {return (val=="0")?true:false ;} //数字是否为0
virtual decimal& round(int r) ;
virtual decimal& round() ; //按dec指定的位数四舍五入
Sign getSn() const {return sn;}
const std::string &getVal() const {return val;}
int getExp() const {return exp;}
Stat getSt() const {return st;}
unsigned getPre() const {return pre;}
unsigned getDec() const {return dec;}
/****************
* 内部子程序 *
****************/
protected :
decimal& decReg() ;
decimal& decAdd(const decimal&);
decimal& decSub(const decimal&);
decimal& decMulti(const decimal&) ;
decimal& decDiv(const decimal&);
void valDiv(std::string& s1,const std::string& s2,const unsigned len) ;
char valMult(std::string& s1,const std::string& s2) ;
void valAdd(std::string& s1,int &p1,const std::string& s2,int p2) ;
int valSub(std::string& s1,int &e1,const std::string& s2,const int e2);
int digitAdd(char& c1,const char c2,const int car=0) ;
int digitSub(char& c1,const char c2,const int b=0) ;
char digitMult(char& c1,const char c2,const char m) ;
int valCmp(const std::string& s1,const int e1,const std::string& s2,const int e2) const;
void setSn(Sign s) {sn=s;}
void setVal(const std::string &s) {val=s;}
void setExp(int i) {exp=i;}
void setSt(Stat s) {st=s;}
void setPre(unsigned u) {pre=u;}
void setDec(unsigned u) {dec=u;}
private :
Sign sn; //符号
std::string val; //有效尾数
int exp; //小数点位置（指数）
//以下为辅助参数
Stat st; //状态
unsigned int pre; //精度(最大有效数字位数)
unsigned int dec; //保留小数位数
};
/*******************
* 协作函数 *
*******************/
decimal round(const decimal& ,const int) ;
//算术运算
decimal operator +(const decimal&,const decimal&) ;
decimal operator -(const decimal&,const decimal&) ;
decimal operator *(const decimal&,const decimal&) ;
decimal operator /(const decimal&,const decimal&) ;
// friend decimal& operator %(const decimal&,const decimal&) ;
//比较运算符
bool operator <(const decimal&,const decimal&) ;
bool operator <=(const decimal&,const decimal&) ;
bool operator ==(const decimal&,const decimal&) ;
bool operator >=(const decimal&,const decimal&) ;
bool operator >(const decimal&,const decimal&) ;
bool operator !=(const decimal&,const decimal&) ;
//流
std::ostream& operator <<(std::ostream&,const decimal&) ;
//unsigned int midDigits(const decimal& ,const decimal& ) ;
#endif //DECIMAL_H
[ 本帖最后由 hqxyn 于 2006-8-22 19:54 编辑 ]
hqxyn 回复于：2006-08-22 10:31:52
money.h
/***************************************************************************
decimal.cpp - description
-------------------
begin : Wed Jan 9 2002
copyright : (C) 2002 by Xian Yining
email : [email]hqxyn@yahoo.com.cn[/email]
***************************************************************************/
/***************************************************************************
* *
* This program is free software; you can redistribute it and/or modify *
* it under the terms of the GNU General Public License as published by *
* the Free Software Foundation; either version 2 of the License, or *
* (at your option) any later version. *
* *
***************************************************************************/
#ifndef _MONEY_H
#define _MONEY_H
#include "decimal.h"
const int MONEY_DEFAULT_DEC = 2;
class money : public decimal {
public :
money():decimal(0,DECIMAL_DEFAULT_PRE,MONEY_DEFAULT_DEC) {};
money(const char* cstr,const unsigned int p=DECIMAL_DEFAULT_PRE)
:decimal(cstr,p,MONEY_DEFAULT_DEC) {round();} ;
money(const int i,const unsigned int p=DECIMAL_DEFAULT_PRE)
:decimal(i,p,MONEY_DEFAULT_DEC){round();} ;
money(const unsigned int ui,const unsigned int p=DECIMAL_DEFAULT_PRE)
:decimal(ui,p,MONEY_DEFAULT_DEC){round();} ;
money(const long l,const unsigned int p=DECIMAL_DEFAULT_PRE)
:decimal(l,p,MONEY_DEFAULT_DEC){round();} ;
money(const long long ll,const unsigned int p=DECIMAL_DEFAULT_PRE)
:decimal(ll,p,MONEY_DEFAULT_DEC){round();} ;
money(const unsigned long ul,const unsigned int p=DECIMAL_DEFAULT_PRE)
:decimal(ul,p,MONEY_DEFAULT_DEC){round();} ;
money(const unsigned long long ull,const unsigned int p=DECIMAL_DEFAULT_PRE)
:decimal(ull,p,MONEY_DEFAULT_DEC){round();} ;
money(const double db,const unsigned int p=DECIMAL_DEFAULT_PRE)
:decimal(db,p,MONEY_DEFAULT_DEC){round();} ;
money(const long double ld,const unsigned int p=DECIMAL_DEFAULT_PRE)
:decimal(ld,p,MONEY_DEFAULT_DEC){round();} ;
money(const decimal& d)
:decimal(0,d.getPre(),MONEY_DEFAULT_DEC) {
setSn(d.getSn());
setVal(d.getVal());
setExp(d.getExp());
round();}
//赋值d.toEString().c_str()
money& operator=(const decimal& d) {
//精度定义(pre)和保留小数位数(dec)在变量定义时确定，?新值时不变。
setSn(d.getSn());
setVal(d.getVal());
setExp(d.getExp());
if (getVal().size()>getPre()) {setSt(OVERDIGITS);}
else setSt(d.getSt());
round();
return *this;
}
};
#endif //_MONEY_H
[ 本帖最后由 hqxyn 于 2006-8-22 10:38 编辑 ]
hqxyn 回复于：2006-08-22 10:35:03
decimal.cpp
/***************************************************************************
decimal.cpp - description
-------------------
begin : Wed Jan 9 2002
copyright : (C) 2002 by Xian Yining
email : [email]hqxyn@yahoo.com.cn[/email]
***************************************************************************/
/***************************************************************************
* *
* This program is free software; you can redistribute it and/or modify *
* it under the terms of the GNU General Public License as published by *
* the Free Software Foundation; either version 2 of the License, or *
* (at your option) any later version. *
* *
***************************************************************************/
#include <iostream>
#include <string>
#undef __DEBUG__
//#define __DEBUG__
#include "decimal.h"
unsigned int midDigits(const decimal& ,const decimal& ) ;
/***********
* 构造函数 *
***********/
decimal::decimal(const std::string &s,const unsigned int p,const unsigned int d) {
decimal x(s.c_str(),p,d);
sn=x.sn;
val=x.val;
exp=x.exp;
st=x.st;
pre=x.pre;
dec=x.dec;
this->decReg();
if (val.size()>p) {st=OVERDIGITS;/*throw*/ ;}
}
decimal::decimal(const char* ci,const unsigned int p,const unsigned int d) {
char c[strlen(ci)+1];
unsigned j=0;
int i;
strcpy(c,ci);
#ifdef __DEBUG__
std::cout<<"char*:c="<<c<<"\n";
#endif
//消前后空格
for ( i=strlen(c)-1;i>=0;--i ) {
if ( c!=' ' ) break;
c='\0';
}
for ( j=0;j<strlen(c); ) {
if (c[j]!=' ') break;
++j;
}
//判符号
if ( c[j]=='+' ) {sn=PLUS;++j;}
else {
if ( c[j]=='-' ) {sn=MINUS;++j;}
else sn=PLUS;
}
//去前导‘0’
while (j<strlen(c+j)) {if (c[j]!='0') break;++j;}
#ifdef __DEBUG__
std::cout<<"char*:j="<<c+j<<"\n";
#endif
char *fp=c+j; //尾数数组指针
#ifdef __DEBUG__
std::cout<<"char*:fp="<<fp<<"\n";
#endif
char *ep=NULL; //指数数组指针
char *dp=NULL; //小数数组指针
st=OK;
for ( j=0;j<strlen(fp) && fp[j]!='\0'; ) { //取尾数整数部分
switch(fp[j]) {
case '0':case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8':case '9':++j;break;
case '.':dp=fp+j+1;fp[j]='\0';break;
case 'E':case 'e':ep=fp+j+1;fp[j]='\0';break;
default:st=NOINIT;fp[j]='\0';
}
}
#ifdef __DEBUG__
std::cout<<"char*:fp2="<<fp<<"\n";
#endif
if ( dp!=NULL ) { //取尾数小数部分
for (j=0;j<strlen(dp) && dp[j]!='\0';){
switch(dp[j]) {
case '0':case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8':case '9':++j;break;
case 'E':case 'e':ep=dp+j+1;dp[j]='\0';break;
default:st=NOINIT;dp[j]='\0';
}
}
}
#ifdef __DEBUG__
std::cout<<"char*:fp3="<<ep<<"\n";
#endif
if ( ep!=NULL ) {
switch(ep[0]) { //检查指数首字符
case '+':case '-':
case '0':case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8':case '9':break;
default:st=NOINIT;
}
}
#ifdef __DEBUG__
std::cout<<"char*:fp4="<<fp<<"\n";
#endif
if ( ep!=NULL ) { //取指数部分
for (j=1;j<strlen(ep);){
switch(ep[j]) {
case '0':case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8':case '9':++j;break;
default:st=NOINIT;
}
#ifdef __DEBUG__
std::cout<<"char*:fp5c="<<fp[j]<<"\n";
#endif
}
}
#ifdef __DEBUG__
std::cout<<"char*:fp5="<<fp<<"\n";
#endif
if (fp!=NULL ) {
val=fp;
}
exp=0;
if (dp!=NULL) {
val.append(dp);
exp-=strlen(dp);
}
if (ep!=NULL) {
#ifdef __DEBUG__
std::cout<<"char*:*ep="<<atoi(ep)<<"\n";
#endif
exp+=atoi(ep);
}
dec=d;
pre=p;
this->decReg();
if (val.size()>p) {st=OVERDIGITS;/*throw*/ ;}
}
decimal::decimal(const int v,const unsigned int p,const unsigned int d) {
char c[std::numeric_limits<int>::digits10+2];
sprintf(c,"%i",v);
#ifdef __DEBUG__
std::cout<<"int:c="<<c<<"\n";
#endif
if (c[0]=='-') {sn=MINUS;val=c+1;}
else {sn=PLUS;val=c;}
pre=p;
dec=d;
exp=0;
st=OK;
this->decReg();
if (val.size()>p) {st=OVERDIGITS;/*throw*/ ;}
}
decimal::decimal(const unsigned int v,const unsigned int p,const unsigned int d) {
char c[std::numeric_limits<unsigned int>::digits10+2];
sprintf(c,"%u",v);
#ifdef __DEBUG__
std::cout<<"Uint:c="<<c<<"\n";
#endif
sn=PLUS;
val=c;
pre=p;
dec=d;
exp=0;
st=OK;
this->decReg();
if (val.size()>p) {st=OVERDIGITS;/*throw*/ ;}
}
decimal::decimal(const long v,const unsigned int p,const unsigned int d) {
char c[std::numeric_limits<long>::digits10+2];
sprintf(c,"%li",v);
#ifdef __DEBUG__
std::cout<<"long:c="<<c<<"\n";
#endif
if (c[0]=='-') {sn=MINUS;val=c+1;}
else {sn=PLUS;val=c;}
pre=p;
dec=d;
exp=0;
st=OK;
this->decReg();
if (val.size()>p) {st=OVERDIGITS;/*throw*/ ;}
}
decimal::decimal(const long long v,const unsigned int p,const unsigned int d) {
char c[std::numeric_limits<long long>::digits10+2];
sprintf(c,"%lli",v);
#ifdef __DEBUG__
std::cout<<"long long:c="<<c<<"\n";
#endif
if (c[0]=='-') {sn=MINUS;val=c+1;}
else {sn=PLUS;val=c;}
pre=p;
dec=d;
exp=0;
st=OK;
this->decReg();
if (val.size()>p) {st=OVERDIGITS;/*throw*/ ;}
}
decimal::decimal(const unsigned long v,const unsigned int p,const unsigned int d) {
char c[std::numeric_limits<unsigned int>::digits10+2];
sprintf(c,"%lu",v);
#ifdef __DEBUG__
std::cout<<"Ulong:c="<<c<<"\n";
#endif
val=c;
sn=PLUS;
pre=p;
dec=d;
exp=0;
st=OK;
this->decReg();
if (val.size()>p) {st=OVERDIGITS;/*throw*/ ;}
}
decimal::decimal(const unsigned long long v,const unsigned int p,const unsigned int d) {
char c[std::numeric_limits<unsigned long long>::digits10+2];
sprintf(c,"%llu",v);
#ifdef __DEBUG__
std::cout<<"UUlong:c="<<c<<"\n";
#endif
val=c;
sn=PLUS;
pre=p;
dec=d;
exp=0;
st=OK;
this->decReg();
if (val.size()>p) {st=OVERDIGITS;/*throw*/ ;}
}
decimal::decimal(const double v,const unsigned int p,const unsigned int d) {
char c[std::numeric_limits<double>::digits10+std::numeric_limits<int>::digits10+1];
char t[10],s[15]="%.";
sprintf(t,"%u",std::numeric_limits<double>::digits10);
strcat(s,t);
strcat(s,"E");
sprintf(c,s,v);
#ifdef __DEBUG__
std::cout<<"double:c="<<c<<"\n";
#endif
char *tE=strchr(c,'E');
if ( tE!=NULL ) { //取指数
exp=atoi(tE+1);
*tE='\0';
}
else exp=0;
// for (unsigned u=strlen(c)-1;u>0 && c[u]=='0';c[u]='\0',u--) {}
char *tD=strchr(c,'.');
if ( tD!=NULL ) { //将尾数变为整数，并相应调整指数
char *px=tD;
for (;*(px+1)!='\0';*px = *(px+1),--exp,++px) {}
*px='\0';
}
if (c[0]=='-') {sn=MINUS;val=c+1;}
else {sn=PLUS;val=c;}
pre=p;
dec=d;
st=OK;
this->decReg();
if (val.size()>p) {st=OVERDIGITS;/*throw*/ ;}
}
decimal::decimal(const long double v,const unsigned int p,const unsigned int d) {
char c[std::numeric_limits<long double>::digits10+std::numeric_limits<int>::digits10+1];
char t[10],s[15]="%.";
sprintf(t,"%u",std::numeric_limits<long double>::digits10);
strcat(s,t);
strcat(s,"LE");
sprintf(c,s,v);
#ifdef __DEBUG__
std::cout<<"long double:c="<<c<<"\n";
#endif
char *tE=strchr(c,'E');
if ( tE!=NULL ) { //取指数
exp=atoi(tE+1);
*tE='\0';
}
else exp=0;
// for (unsigned u=strlen(c)-1;u>0 && c[u]=='0';c[u]='\0',u--) {}
char *tD=strchr(c,'.');
if ( tD!=NULL ) { //将尾数变为整数，并相应调整指数
char *px=tD;
for (;*(px+1)!='\0';*px = *(px+1),--exp,++px) {}
*px='\0';
}
if (c[0]=='-') {sn=MINUS;val=c+1;}
else {sn=PLUS;val=c;}
pre=p;
dec=d;
st=OK;
this->decReg();
if (val.size()>p) {st=OVERDIGITS;/*throw*/ ;}
}
/************
* 赋值操作符 *
************/
decimal& decimal::operator=(const decimal& d) {
//精度定义(pre)和保留小数位数(dec)在变量定义时确定，?新值时不变。
#ifdef __DEBUG__
std::cout<<"in decimal[=]:"<<*this<<";;"<<d<<"\n";
#endif
sn=d.sn;
val=d.val;
exp=d.exp;
if (val.size()>pre) {st=OVERDIGITS;/*throw*/ ;}
else st=d.st;
return *this;
}
/**************
* 算术运算符 *
**************/
decimal& decimal::operator +=(const decimal& d2) {
if (sn==d2.sn) {
valAdd(val,exp,d2.val,d2.exp);
}
else {
if (valCmp(val,exp,d2.val,d2.exp)<0) {
std::string t=d2.val;
int et=d2.exp;
valSub(t,et,val,exp);val=t;exp=et;sn=d2.sn;
}
else valSub(val,exp,d2.val,d2.exp);
}
return this->decReg();
}
decimal& decimal::operator -=(const decimal& d2) {
if (sn==d2.sn) {
if (valCmp(val,exp,d2.val,d2.exp)<0) {
std::string t=d2.val;
int et=d2.exp;
valSub(t,et,val,exp);val=t;exp=et;
sn=(d2.sn==PLUS)?MINUS:PLUS;
}
else valSub(val,exp,d2.val,d2.exp);
}
else {
valAdd(val,exp,d2.val,d2.exp);
}
return this->decReg();
}
decimal& decimal::operator *=(const decimal& d2) {
sn=(sn==d2.sn)?PLUS:MINUS;
exp+=d2.exp;
valMult(val,d2.val);
return this->decReg();
}
decimal& decimal::operator /=(const decimal& d2) {
if (d2.zero()) {st=UPFLOW;return *this;}
sn=(sn==d2.sn)?PLUS:MINUS;
int te1,te2;
te1=exp+val.size();te2=d2.exp+d2.val.size();
te1-=te2;
valDiv(val,d2.val,pre+1);
exp=-val.size()+1+te1;
return this->decReg();
}
decimal operator +(const decimal& d1,const decimal& d2) {
decimal d(0,midDigits(d1,d2),(d1.getDec()>=d2.getDec())?d1.getDec():d2.getDec());
d=d1;
#ifdef __DEBUG__
std::cout<<"[+]:d="<<d<<"d.pre="<<d.getPre()<<"\n";
#endif
return d+=d2;
}
decimal operator -(const decimal& d1,const decimal& d2) {
decimal d(0,midDigits(d1,d2),(d1.getDec()>=d2.getDec())?d1.getDec():d2.getDec());
d=d1;
#ifdef __DEBUG__
std::cout<<"[-]:d="<<d<<"d.pre="<<d.getPre()<<"\n";
#endif
return d-=d2;
}
decimal operator *(const decimal& d1,const decimal& d2) {
decimal d(0,d1.getPre()+d2.getPre(),d1.getDec()+d2.getDec());
d=d1;
#ifdef __DEBUG__
std::cout<<"[*]:d="<<d<<"d.pre="<<d.getPre()<<"\n";
#endif
return d*=d2;
}
decimal operator /(const decimal& d1,const decimal& d2) {
decimal d(0,d1.getPre()+d2.getPre(),d1.getDec()+d2.getDec());
d=d1;
#ifdef __DEBUG__
std::cout<<"[/]:d="<<d<<"d.pre="<<d.getPre()<<"\n";
#endif
return d/=d2;
}
/**********************
* 比较运算符 *
*********************/
bool decimal::le(const decimal& d2) const {
if (sn==decimal::PLUS && d2.sn==decimal::MINUS) return false;
if (sn==decimal::MINUS && d2.sn==decimal::PLUS) return true;
int r=decimal::valCmp(val,exp,d2.val,d2.exp);
if (sn==decimal::PLUS && r<0) return true;
if (sn==decimal::MINUS && r>0) return true;
return false;
}
bool decimal::eq(const decimal& d2) const {
if ((sn==decimal::MINUS && d2.sn==decimal::PLUS) || (sn==decimal::PLUS && d2.sn==decimal::MINUS)) return false;
int r=decimal::valCmp(val,exp,d2.val,d2.exp);
if (r==0) return true;
return false;
}
bool decimal::gt(const decimal& d2) const {
if (this->sn==decimal::MINUS && d2.sn==decimal::PLUS) return false;
if (this->sn==decimal::PLUS && d2.sn==decimal::MINUS) return true;
int r=decimal::valCmp(val,exp,d2.val,d2.exp);
if (this->sn==decimal::PLUS && r>0) return true;
if (this->sn==decimal::MINUS && r<0) return true;
return false;
}
bool operator <(const decimal& d1,const decimal& d2) {
return d1.le(d2);
}
bool operator ==(const decimal& d1,const decimal& d2) {
return d1.eq(d2);
}
bool operator >(const decimal& d1,const decimal& d2) {
return d1.gt(d2);
}
bool operator <=(const decimal& d1,const decimal& d2) {
return !(d1>d2);
}
bool operator >=(const decimal& d1,const decimal& d2) {
return !(d1<d2);
}
bool operator !=(const decimal& d1,const decimal& d2) {
return !(d1==d2);
}
/*****************
* 输入输出流 *
****************/
std::ostream &operator <<(std::ostream &os,const decimal& d) {
#ifdef __DEBUG__
os<<"ok="<<d.ok();
os<<",sign="<<((d.getSn()==decimal::PLUS)?'+':((d.getSn()==decimal::MINUS)?'-':'?'));
os<<",val="<<d.getVal();
os<<",exp="<<d.getExp();
os<<",pre="<<d.getPre();
os<<",dec="<<d.getDec();
os<<"\n";
#endif
os<<d.toString(0,d.getDec());
return os;
}
/*
std::istream& operator >>(std::istream& is,decimal& d) {
std::string s;
std::cin>>s;
decimal dx(s.c_str());
d=dx;
return is;
}
*/
/**************
* 杂函数 *
**************/
std::string decimal::toEString(const unsigned len) const {
std::string s="";
s.append((sn==decimal::MINUS)?"-":((sn==decimal::PLUS)?" ":"?"));
s.append(val);
s.append("E");
char c[50];
sprintf(c,"%i",exp);
s.append(c);
if (len != 0 && len<s.size()) s.assign(len,'*');
return s;
}
std::string decimal::toShortStr() const{
std::string s=toString();
if (s.find('.')==std::string::npos) return s;
int c=0;
for (uint u=s.length()-1;u>0;--u){
if (s[u]=='0') ++c;
else break;
}
if (s[s.length()-1-c]=='.') ++c;
s=s.substr(0,s.length()-c);
return s;
}
std::string decimal::toString() const{
return toString(0,getDec());
}
std::string decimal::toString(const unsigned int len,const int de) const {
std::string s="";
if ( ! this->ok() ) return s.append((len==0)?1:len,'*'); //数字无效
s.append((sn==decimal::MINUS)?"-":((sn==decimal::PLUS)?" ":"?"));
if (exp>=0) { //整数
s.append(val).append(exp,'0').append(1,'.').append(de,'0');
}
else {
if (-exp>=val.size()) { //纯小数
s.append("0.").append(-exp-val.size(),'0').append(val);
}
else {
s.append(val.substr(0,val.size()+exp));
s.append(1,'.');
std::string x=val.substr(val.size()+exp);
s.append(x); //带小数
s.append((de>x.size())?de-x.size():0,'0');
}
}
if (len != 0 && len<s.size()) s.assign(len,'*');
return s;
}
decimal& decimal::round() {
return round(dec);
}
decimal& decimal::round(int r) {
if (r<-exp) { //末位属于舍入位
std::string x="5";
int e=-(r+1);
valAdd(val,exp,x,e);
int i=-exp-r;
if ((val.size()-i)<=0) val="0";
else val=val.substr(0,val.size()-i);
exp+=i;
}
return this->decReg();
}
decimal round(const decimal& d,const int dec) {
decimal dx(0,d.getPre(),dec);
dx=d;
dx.round(dec);
return dx;
}
/****************
* 内部子程序 *
****************/
void decimal::valDiv(std::string& s1,const std::string& s2,const unsigned len) {
std::string s(len,'0'); //商
int ed=s2.size()-s1.size(); //商的小数位数
std::string t1=s1,t2=s2;
int et1; //被除数对位指数,把两数首位对齐
et1=ed;
unsigned int i; //商数循环
int c; //借位
for (i=0;i<len;++i,++et1) {
int j=1;
for (j=1;j<=10;++j) {
if (valCmp(t1,et1,s2,0)<0) {
--j;
break;
}
c=valSub(t1,et1,s2,0) ;
}
s=char(j+48);
}
s1=s;
}
char decimal::valMult(std::string& s1,const std::string& s2) {
std::string s="0";
int es=0;
for (unsigned int i=0;i<s2.size();++i) { //乘数从末尾向前循环
char c1,c2=s2[s2.size()-1-i],m='0';
int j;
std::string pn(s1.size()+1,'0');
for (j=s1.size()-1;j>=0;--j) { //被乘数乘以当前乘数位
c1=s1[j];
m=digitMult(c1,c2,m);
pn[j+1]=c1;
}
es=-i;
pn[0]=m;
valAdd(s,es,pn,0);
}
if (s[0]!='0') s1=s;
else s1=s.substr(1);
return '0';
}
int decimal::valSub(std::string& s1,int &e1,const std::string& s2,const int e2) {
//计算差的位数
//std::cout<<"s1="<<s1<<",e1="<<e1<<",s2"<<s2<<",e2="<<e2<<"\n";
int li1,ld1,li2,ld2,li,ld;
li1= s1.size()+e1;
if ( e1>=0 ) {
li1=s1.size()+e1;
ld1=0;
}
else {
if (li1<0) li1=0;
ld1=-e1;
}
li2=s2.size()+e2;
if ( e2>=0 ) {
ld2=0;
}
else {
if (li2<0) li2=0;
ld2=-e2;
}
li=(li1>=li2)?li1:li2; //整数位数
ld=(ld1>=ld2)?ld1:ld2; //小数位数
std::string s(li+ld,'0');
int qb1, //第一串首位权数
qe1, //第一串末位权数
qb2, //第二串首位权数
qe2; //第二串末位权数
qe1=li-e1-1;qb1=qe1-s1.size()+1;
qe2=li-e2-1;qb2=qe2-s2.size()+1;
char c1,c2;
int m=0,j;
for (j=li+ld-1;j>=0;--j) {
c1=(j>=qb1 && j<=qe1)?s1[j-qb1]:'0';
c2=(j>=qb2 && j<=qe2)?s2[j-qb2]:'0';
m=digitSub(c1,c2,m);
s[j]=c1;
}
s[0]=c1;
s1=s;e1=-ld;
return m;
}
void decimal::valAdd(std::string& s1,int &e1,const std::string& s2,const int e2) {
//计算和的位数
int li1,ld1,li2,ld2,li,ld;
li1= s1.size()+e1;
if ( e1>=0 ) {
li1=s1.size()+e1;
ld1=0;
}
else {
if (li1<0) li1=0;
ld1=-e1;
}
li2=s2.size()+e2;
if ( e2>=0 ) {
ld2=0;
}
else {
if (li2<0) li2=0;
ld2=-e2;
}
li=(li1>=li2)?li1:li2; //整数位数
ld=(ld1>=ld2)?ld1:ld2; //小数位数
std::string s(li+ld+1,'0');
int qb1, //第一串首位权数
qe1, //第一串末位权数
qb2, //第二串首位权数
qe2; //第二串末位权数
qe1=li-e1;qb1=qe1-s1.size()+1;
qe2=li-e2;qb2=qe2-s2.size()+1;
char c1,c2;
int m=0,j;
for (j=li+ld;j>0;--j) {
c1=(j>=qb1 && j<=qe1)?s1[j-qb1]:'0';
c2=(j>=qb2 && j<=qe2)?s2[j-qb2]:'0';
m=digitAdd(c1,c2,m);
s[j]=c1;
}
if (m>0) {s[0]='1';s1=s;}
else s1=s.substr(1);
e1=-ld;
}
int decimal::digitAdd(char& c1,const char c2,const int car) {
int i=c1+c2-48+car;
int c=0;
if (i>57) {i-=10;c=1;}
c1=char(i);return c;
}
int decimal::digitSub(char& c1,const char c2,const int b) {
int c=(c1>=c2+b)?0:1;
int i=c1+(c*10)-c2+48-b;
c1=char(i);
return c;
}
char decimal::digitMult(char& c1,const char c2,const char m) {
int i=(c1-48)*(c2-48)+(m-48);
c1=i%10+48;
return char(i/10+48);
}
int decimal::valCmp(const std::string& s1,const int e1,const std::string& s2,const int e2) const {
unsigned int h1,h2; //第一有效位的位置
//去掉前导0
for (h1=0;h1<s1.size() && (s1[h1]=='0');++h1) {}
for (h2=0;h2<s2.size() && (s2[h2]=='0');++h2) {}
if ( (h1<s1.size()) && ((s1.size()-h1+e1)>(s2.size()-h2+e2)) ) return 1;
if ( ((s1.size()-h1+e1)<(s2.size()-h2+e2)) && (h1<s1.size()) ) return -1;
int i,j;
for (i=s1.size()-h1,j=s2.size()-h2;i>0 && j>0;--i,--j,++h1,++h2) {
if (s1[h1]<s2[h2]) return -1;
if (s1[h1]>s2[h2]) return 1;
}
if (i>j) {
for (;i>0 && s1[h1]=='0';--i,++h1) {}
return (i==0)?0:1;
}
if (i<j) {
for (;j>0 && s2[h2]=='0';--j,++h2) {}
return (j==0)?0:-1;
}
return 0;
}
decimal& decimal::decReg() {
//消去前0和尾0，调整指数exp
unsigned int b,e;
for (b=0;b<val.size()-1 && val=='0';++b){}
for (e=val.size()-1;e>b && val[e]=='0';--e,++exp){}
if (b!=0 || e!=val.size()-1) val=val.substr(b,e-b+1);
if (val.size()==1 && val[0]=='0') {exp=0;sn=PLUS;} //值为“零”,指数应为0,符号认定为正
return *this;
}
unsigned int midDigits(const decimal& d1,const decimal& d2) {
//计算和或差中间变量的位数
int li1,ld1,li2,ld2,li,ld;
li1= d1.getVal().size()+d1.getExp();
if ( d1.getExp()>=0 ) {
li1=d1.getVal().size()+d1.getExp();
ld1=0;
}
else {
if (li1<0) li1=0;
ld1=-d1.getExp();
}
li2=d2.getVal().size()+d2.getExp();
if ( d2.getExp()>=0 ) {
ld2=0;
}
else {
if (li2<0) li2=0;
ld2=-d2.getExp();
}
li=(li1>=li2)?li1:li2; //整数位数
ld=(ld1>=ld2)?ld1:ld2; //小数位数
return li+ld+1;
}
[ 本帖最后由 hqxyn 于 2006-8-22 19:55 编辑 ]
flw 回复于：2006-08-22 10:36:00
引用：原帖由 mirnshi 于 2006-8-21 15:02 发表
接口为10进制, 内部的进制采用unsigned long或unsigned short，是不是更能借助逻辑运算，提高效率？
我也这样想。
考虑到 unsigned int 在 32 位机上可以表示超过 10 亿的整数，因此倘若采用万进制来进行内部表示的话，效率应该会高很多。
至于加减法，可以直接用亿进制来进一步提高速度。
hqxyn 回复于：2006-08-22 10:56:17
开始我也曾用long long型作内部表示，但出于以下考虑，还是放弃了
1）要能表示”任意“大小的十进浮点数。
2）算术运算不能带来误差（用二进制数表示十进制小数总会有舍入误差）。
当然用字符型处理数值效率确实低，但这样作的最直接用途是处理货币类应用，并不是科学计算，也就将就了。
soaact 回复于：2006-08-22 11:36:17
弱弱的问一下楼主：
您在做除法和乘方的时候采用的是什么算法，没有看太明白？
谢谢:)
yuxh 回复于：2006-08-22 12:30:32
我写这个类的目的是想实现判断一个数是否是素数, 其中第一步就是判断这个数是否某个数的整数次幂
所以我关心的是运算的效率,而不是把它扩展成浮点数形式等更适用的情况
由于在推导一些公式时就是用10进制来考虑的,所以写的代码里也是用10进制数表示的,其实,对代码作一些相应的改动,是很方便换成16进制或别的基进制,(也可以扩展成浮点数的形式,但对我的应用来说,意义不大).
[ 本帖最后由 yuxh 于 2006-8-22 12:38 编辑 ]
yuxh 回复于：2006-08-22 13:04:39
贴一段测试代码给大家玩玩:D
#include "decnum.h"
int main()
{
decnum x, y, r;
char *line = NULL;
size_t n = 0;
int read;
cout << "input x:" << endl;
if((read = (int)getline(&line, &n, stdin)) != -1) {
x = decnum(line, read-1);
}
else
exit(-1);
cout << "input y:" << endl;
if((read = (int)getline(&line, &n, stdin)) != -1) {
y = decnum(line, read-1);
}
else
exit(-1);
cout << "x = " << x << endl;
cout << "y = " << y << endl;
cout << "x * y =" << x * y << endl;
cout << "x / y =" << x / y << endl;
cout << "x % y =" << x % y << endl;
cout << "div(x, y) =" << div(x , y, r) << endl;
cout << "mod(x, y) =" << r << endl;
cout << "y ^ 2 =" << pow(y, 2) << endl;
cout << "x ^ 1/2 =" << root(x, 2) << endl;
cout << "x is pow = " << x.ispow() << endl;
return 0;
}
引用：input x:
12934891238741902347120934871230948712390487123904871239047812390847123094871230948712309487123904871230947123980471203948712309487120394712398471239048713256129834712903847120394781239084712930487231094712394087123094123481203333333333333333333333333333333333333333333888888888888888888888888888888888888888888888888222222222222222222222222222222222222221094387123908471293048721903487123908412903471290384712398471239847213984712938471209384172093847129834712093847123904123471290384712398471209348712093847120938471297340129341
input y:
87123904781239084712309487123094871230948712390487123
x = 12934891238741902347120934871230948712390487123904871239047812390847123094871230948712309487123904871230947123980471203948712309487120394712398471239048713256129834712903847120394781239084712930487231094712394087123094123481203333333333333333333333333333333333333333333888888888888888888888888888888888888888888888888222222222222222222222222222222222222221094387123908471293048721903487123908412903471290384712398471239847213984712938471209384172093847129834712093847123904123471290384712398471209348712093847120938471297340129341
y = 87123904781239084712309487123094871230948712390487123
x * y =1126938232639833173075933852454844491172426928514059866807740841770815249456423275828974308682129087476539239375374114934208988211619943619716558347499808789403504191997992053251495407207133672212198009872845450749525122406765537233683189166639249361344448037097903846536903047332910602617949715068386039572749284661323652396812507276858460341917936752512602597008627491342253724797935606421392773895578442187710885039658694980497445673861077574294718176507864939038642062979105391800654254681231524754223749316701123751673470225808955075291647887679573776980478625133783450814975943
x / y =148465467327484275048232812439334306695533671227089122007816650126394502951501427671718661140385906942393209068225081817296775831986299773922335101921640962699307587052445014486841122328740344708845214812651256032481988250472736002705523700302442398432754627409724200156670159012028113430398315975429449502269548763370786332836604219524721316400456079938591537603272259855595623013801608933716962712146970686555106278637839124034044858476557783789374654839217122223912234300207
x % y =79300951666803804539185154310166594060311523590394880
div(x, y) =148465467327484275048232812439334306695533671227089122007816650126394502951501427671718661140385906942393209068225081817296775831986299773922335101921640962699307587052445014486841122328740344708845214812651256032481988250472736002705523700302442398432754627409724200156670159012028113430398315975429449502269548763370786332836604219524721316400456079938591537603272259855595623013801608933716962712146970686555106278637839124034044858476557783789374654839217122223912234300207
mod(x, y) =79300951666803804539185154310166594060311523590394880
y ^ 2 =7590574784330414645380746230930586484532745231159928445672223588351361500455337820516206371351345228817129
x ^ 1/2 =3596510981318130543477927424759527967760623382196876121688918127992258229306117726707700713885454867164034990294666943466289844107281148419105171980209085534883218753821511324570335831894205011649807156193955342866243572062280023407886590191390520013437462254313721
x is pow = 0
思一克 回复于：2006-08-22 13:09:09
yuxh 弄了一个伟大的工程呀
yuxh 回复于：2006-08-22 13:12:12
引用：原帖由 思一克 于 2006-8-22 13:09 发表
yuxh 弄了一个伟大的工程呀
:D
只是玩玩,呵呵~万里长征才走了第一步哇~
xiaomiao 回复于：2006-08-22 15:16:57
搞科学计算最好不用C/C++，传统的用Fortran,现代流行的用Matlab,后者矩阵运算功能超级强大
aple_smx 回复于：2006-08-22 15:29:53
顶起
soaact 回复于：2006-08-22 15:44:32
引用：原帖由 xiaomiao 于 2006-8-22 15:16 发表
搞科学计算最好不用C/C++，传统的用Fortran,现代流行的用Matlab,后者矩阵运算功能超级强大
不同意您的意见！难道MATLAB不是用C／C＋＋编写的么？
建议你去SF或BELLLAB看看，哪个科学计算用的语言是MATLAB？JAVA
倒是有的，偶尔也有PERL就是没有看见用MATLAB或MAPLE之类来做的。
为什么？效率太低了！
去你的系统上算一下：
2^1000000
看看是MATLAB快还是调用了gmp库的c/c++快！
另 to LZ ：在计算pow(A,1/n)的时候还可以用另一个迭代公式：
a[k]=(A/pow(a[k-1],n-1) + (n-1)*a[k-1])/n
A和n是初始值
再次感谢lz
rushrush 回复于：2006-08-22 15:46:56
http://www.swox.com/gmp/ :em25:
醉卧水云间 回复于：2006-08-22 16:42:40
AKS早有人测试过了，不灵。
xiaomiao 回复于：2006-08-22 18:17:14
呵呵，你的说法有点道理，从效率和性能上看C/C++是占有优势，但Matlab一类的科学计算语言在易用性、直观性还有可视化等方面有很大优势，现在很多高校的工科自控、电子等专业不都用Matlab/Simulink一类的软件做计算和仿真嘛
yuxh 回复于：2006-08-23 18:17:04
增加了负数，但负数不支持取余(%)及相应的带余除法(div)
并用它解决了醉卧水云间 的pell方程的问题
:D
assiss 回复于：2006-08-23 18:29:11
你测试过你的大数库效率吗？
我曾经仔细优化我自己写的C大数库函数，但始终没有GMP的速度快。看GMP的代码，优化到了汇编地步。实在是恐怖。
zengjin8310 回复于：2006-08-24 08:29:33
引用：原帖由 yuxh 于 2006-8-22 12:30 发表
我写这个类的目的是想实现判断一个数是否是素数, 其中第一步就是判断这个数是否某个数的整数次幂
所以我关心的是运算的效率,而不是把它扩展成浮点数形式等更适用的情况
由于在推导一些公式时就是用10进制来考虑的,所以写的代码里也是用10进制数表示的,其实,对代码作一些相应的改动,是很方便换成16进制或别的基进制,(也可以扩展成浮点数的形式,但对我的应用来说,意义不大).
费马定理？ 可以参考java RSA公私钥的生成算法， 我没研究过， 你看看那个素数寻找算法是不是比你的好
zengjin8310 回复于：2006-08-24 08:32:41
引用：原帖由 xiaomiao 于 2006-8-22 15:16 发表
搞科学计算最好不用C/C++，传统的用Fortran,现代流行的用Matlab,后者矩阵运算功能超级强大
matlab这个主要是给应用的人用， 科学计算是研究的东西跟matlab里面那一堆工具箱里面的算法实现类似的东西。 如果入门级科学计算matlab可以， 骨灰级的你不懂操作系统，不懂C/C++，lisp你给我试试看你能研究个啥
|
