试图理解简单的大数计算
Trying to understand simple big number calculations
我正在努力更好地理解 'big numbers' 库的工作原理(例如 GMP)。
我想自己写函数到Add()
/Subtract()
/Multiply()
/Divide()
传统上定义class ...
std::vector<unsigned char> _numbers; // all the numbers
bool _neg; // positive or negative number
long _decimalPos; // where the decimal point is located
// so 10.5 would be 1
// 10.25 would be 2
// 10 would be 0 for example
首先我需要对数字进行标准化,这样我就可以
使用2个号码
10(x) + 10.25(y) = 20.25
为简单起见,我会让它们的长度相同,
对于 x:
_numbers = (1,0,0,0) 小数 = 2
对于你:
_numbers = (1,0,2,5) 小数 = 2
然后我可以在循环中反向将 x 添加到 y
...
// where x is 10.00 and y is 10.25
...
unsigned char carryOver = 0;
int totalLen = x._numbers.size();
for (size_t i = totalLen; i > 1 ; --i )
{
unsigned char sum = x._numbers[i-1] + y._numbers[i-1] + carryOver;
carryOver = 0;
if (sum > _base)
{
sum -= _base;
carryOver = 1;
}
numbers.insert( number.begin(), sum);
}
// any left over?
if (carryOver > 0)
{
numbers.insert( number.begin(), 1 );
}
// decimal pos is the same for this number as x and y
...
上面的示例适用于将两个正数相加,但是一旦我需要将一个负数与一个正数相加,它很快就会失败。
当涉及到减法时,这会变得更加复杂,而对于乘法和除法则更糟。
有人可以向 Add() / Subtract() / Multiply() / Divide() 推荐一些简单的函数吗
我不是要重写/改进库,我只是想了解它们如何处理数字。
加法和减法非常简单
您需要检查操作数的符号和大小,如果需要,请转换运算 to/from +/-
。我的典型 C++ 实现是这样的:
//---------------------------------------------------------------------------
arbnum arbnum::operator + (const arbnum &x)
{
arbnum c;
// you can skip this if you do not have NaN or Inf support
// this just handles cases like adding inf or NaN or zero
if ( isnan() ) return *this;
if (x.isnan() ) { c.nan(); return c; }
if ( iszero()) { c=x; return c; }
if (x.iszero()) return *this;
if ( isinf() ) { if (x.isinf()) { if (sig==x.sig) return *this;
c.nan(); return c; } return *this; }
if (x.isinf()) { c.inf(); return c; }
// this compares the sign bits if both signs are the same it is addition
if (sig*x.sig>0) { c.add(x,this[0]); c.sig=sig; }
// if not
else{
// compare absolute values (magnitudes)
if (c.geq(this[0],x)) // |this| >= |x| ... return (this-x)
{
c.sub(this[0],x);
c.sig=sig; // use sign of the abs greater operand
}
else { // else return (x-this)
c.sub(x,this[0]);
c.sig=x.sig;
}
}
return c;
}
//---------------------------------------------------------------------------
arbnum arbnum::operator - (const arbnum &x)
{
arbnum c;
if ( isnan() ) return *this;
if (x.isnan() ) { c.nan(); return c; }
if ( iszero()) { c=x; c.sig=-x.sig; return c; }
if (x.iszero()) return *this;
if ( isinf() ) { if (x.isinf()) { if (sig!=x.sig) return *this;
c.nan(); return c; } return *this; }
if (x.isinf()) { c.inf(); c.sig=-x.sig; return c; }
if (x.sig*sig<0) { c.add(x,this[0]); c.sig=sig; }
else{
if (c.geq(this[0],x))
{
c.sub(this[0],x);
c.sig=sig;
}
else {
c.sub(x,this[0]);
c.sig=-x.sig;
}
}
return c;
}
//---------------------------------------------------------------------------
其中:
geq
是无符号比较大于等于
add
是无符号的 +
sub
是无符号的 -
除法有点复杂
参见:
- bignum divisions
approximational bignum divider
对于部门,你需要已经实现了 +,-,*,<<,>>
之类的东西,对于一些更高级的方法,你甚至需要这样的东西:绝对比较(你需要它们 +/-
anyway) , sqr, 使用的数量 bits 通常分开小数和整数部分。
最重要的是乘法见Fast bignum square computation因为它是大多数除法算法的核心。
性能
一些提示见BigInteger numbers implementation and performance
文本转换
如果您的号码是 ASCII 或 BASE=10^n
数字,那么这很容易,但是如果您出于性能原因使用 BASE=2^n
,那么您需要具有能够在 [=21] 之间进行转换的快速函数=] 和 hex
字符串,这样你就可以实际加载和打印一些数字 to/from 你的 class。见:
- How to convert a gi-normous integer (in string format) to hex format?
我正在努力更好地理解 'big numbers' 库的工作原理(例如 GMP)。
我想自己写函数到Add()
/Subtract()
/Multiply()
/Divide()
传统上定义class ...
std::vector<unsigned char> _numbers; // all the numbers
bool _neg; // positive or negative number
long _decimalPos; // where the decimal point is located
// so 10.5 would be 1
// 10.25 would be 2
// 10 would be 0 for example
首先我需要对数字进行标准化,这样我就可以
使用2个号码 10(x) + 10.25(y) = 20.25
为简单起见,我会让它们的长度相同,
对于 x: _numbers = (1,0,0,0) 小数 = 2
对于你: _numbers = (1,0,2,5) 小数 = 2
然后我可以在循环中反向将 x 添加到 y
...
// where x is 10.00 and y is 10.25
...
unsigned char carryOver = 0;
int totalLen = x._numbers.size();
for (size_t i = totalLen; i > 1 ; --i )
{
unsigned char sum = x._numbers[i-1] + y._numbers[i-1] + carryOver;
carryOver = 0;
if (sum > _base)
{
sum -= _base;
carryOver = 1;
}
numbers.insert( number.begin(), sum);
}
// any left over?
if (carryOver > 0)
{
numbers.insert( number.begin(), 1 );
}
// decimal pos is the same for this number as x and y
...
上面的示例适用于将两个正数相加,但是一旦我需要将一个负数与一个正数相加,它很快就会失败。
当涉及到减法时,这会变得更加复杂,而对于乘法和除法则更糟。
有人可以向 Add() / Subtract() / Multiply() / Divide() 推荐一些简单的函数吗
我不是要重写/改进库,我只是想了解它们如何处理数字。
加法和减法非常简单
您需要检查操作数的符号和大小,如果需要,请转换运算 to/from +/-
。我的典型 C++ 实现是这样的:
//---------------------------------------------------------------------------
arbnum arbnum::operator + (const arbnum &x)
{
arbnum c;
// you can skip this if you do not have NaN or Inf support
// this just handles cases like adding inf or NaN or zero
if ( isnan() ) return *this;
if (x.isnan() ) { c.nan(); return c; }
if ( iszero()) { c=x; return c; }
if (x.iszero()) return *this;
if ( isinf() ) { if (x.isinf()) { if (sig==x.sig) return *this;
c.nan(); return c; } return *this; }
if (x.isinf()) { c.inf(); return c; }
// this compares the sign bits if both signs are the same it is addition
if (sig*x.sig>0) { c.add(x,this[0]); c.sig=sig; }
// if not
else{
// compare absolute values (magnitudes)
if (c.geq(this[0],x)) // |this| >= |x| ... return (this-x)
{
c.sub(this[0],x);
c.sig=sig; // use sign of the abs greater operand
}
else { // else return (x-this)
c.sub(x,this[0]);
c.sig=x.sig;
}
}
return c;
}
//---------------------------------------------------------------------------
arbnum arbnum::operator - (const arbnum &x)
{
arbnum c;
if ( isnan() ) return *this;
if (x.isnan() ) { c.nan(); return c; }
if ( iszero()) { c=x; c.sig=-x.sig; return c; }
if (x.iszero()) return *this;
if ( isinf() ) { if (x.isinf()) { if (sig!=x.sig) return *this;
c.nan(); return c; } return *this; }
if (x.isinf()) { c.inf(); c.sig=-x.sig; return c; }
if (x.sig*sig<0) { c.add(x,this[0]); c.sig=sig; }
else{
if (c.geq(this[0],x))
{
c.sub(this[0],x);
c.sig=sig;
}
else {
c.sub(x,this[0]);
c.sig=-x.sig;
}
}
return c;
}
//---------------------------------------------------------------------------
其中:
geq
是无符号比较大于等于add
是无符号的+
sub
是无符号的-
除法有点复杂
参见:
- bignum divisions
approximational bignum divider
对于部门,你需要已经实现了
+,-,*,<<,>>
之类的东西,对于一些更高级的方法,你甚至需要这样的东西:绝对比较(你需要它们+/-
anyway) , sqr, 使用的数量 bits 通常分开小数和整数部分。最重要的是乘法见Fast bignum square computation因为它是大多数除法算法的核心。
性能
一些提示见BigInteger numbers implementation and performance
文本转换
如果您的号码是 ASCII 或 BASE=10^n
数字,那么这很容易,但是如果您出于性能原因使用 BASE=2^n
,那么您需要具有能够在 [=21] 之间进行转换的快速函数=] 和 hex
字符串,这样你就可以实际加载和打印一些数字 to/from 你的 class。见:
- How to convert a gi-normous integer (in string format) to hex format?