九天雁翎的博客
如果你想在软件业获得成功,就使用你知道的最强大的语言,用它解决你知道的最难的问题,并且等待竞争对手的经理做出自甘平庸的选择。 -- Paul Graham

增加无限长精确整数(infinite precision integer)给C++标准库的提案 简单翻译稿 N1692

A Proposal to add the Infinite Precision Integer to the

C++ Standard Library N1692 1 July 2004

原作者:M.J. Kronenburg

e-mail: M.Kronenburg@inter.nl.net

 原文链接:http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1692.pdf

九天雁翎简单翻译稿:

增加无限长精确整数infinite precision integerC++标准库的提案

1 动机:

对整数的需要不再适应于处理器数据长度的增加。比如,int类型的范围在一个32位电脑上是±2^31 ±10^9.对于超出这个范围的情况,程序员往往创建一个用unsigned int 和符号位组成的C++类,这个类的数据长度仅仅受可用内存的限制。并且重载了数学操作符。这个类的整数范围是±2^8mm是以字节(byte)度量的最大可用内存。以现在的内存大小来说,这个范围实际上是无限的。这个类就是一个无限长精确整数,我提议这个类的名字为integer

目前有很多无限长精确整数的实现存在,以下给出一些总的来说比较好的支持,实现和设计方案:

 

1. Gnu C++ library 中的 Integer

(C++, 限制在10^5 位以内 [7]).

 

2. The Gnu Multiple Precision Arithmetic Library

(C with assembler, 无限[6]).

 

3. 我自己设计的Integer class

(C++ with assembler, 无限)

 

在以后,我提到实现123就是分别指以上几种。

 

2           对标准的影响

作为一个有自己内存管理的独立类,没有对标准产生影响。

 

3           设计结果

有很多设计结果,但是选择通常就是在我在上面列出来的几种中进行。

 

3.1       类结构

这个被提议的C++类将是integer类。实现这个类,使用int的函数和操作符是需要被重载的,并且重载求最大公约数和最小公倍数的函数也是必须的,而且一些类似setbit,clearbit,getbit,highestbit,lowestbit等的位级(bit level)操作也是需要重载的。在实现1里面的Integer类是用包含一个struct的方式表示的。这意味着,每个类函数或者操作符调用的函数都是作用在这个struct上面。实现2是一个在C上的实现。所以要在C++上面使用,需要一个C++的封装。在实现3里,这个Integer类是一个内部没有用struct表示的简单的C++类。这里有一个从string创建对象的构造函数,因此任何数字可以由一个任意长度的string指定。

 

3.2       数据结构

在所有以上我提到的实现中,数据都是一个连在一起的可变长二进制块。一个可以保存-1(小于0),0(零),1(大于0)值的符号被存储在一个分开的地方。一个可行的方法是把数据放在一个标准库容器vector中,但是像许多integer操作在位级上实现一样,对vector容器实现的依赖是不可接受的。因此,integer不会使用任何标准库容器或者函数。

 

3.3  数据粒度(Data Granularity

为了操作integer数据,它的粒度必须被定义,即一次操作多宽的数据块。在32位处理器上,实现1short 16位粒度,因为这意味着所有的移位(shift)和传送(carry)操作可以用32位的int实现,那么就不需要使用汇编。在32位处理器上,其他的实现用32位的粒度,这意味着汇编是不可避免的了。目前我还不清楚,是否64位处理器可以控制64位粒度的integer

 

3.3       性能

所有的算术计算操作性能在使用32位粒度和汇编时都好很多。对于两个大数的乘法,很多算法存在(N 是数据的十进制或二进制位数(number of decimals or bits:

Algorithm            implementation     order                           decimals               reference

Basecase                     1,2,3              N^2                                      1 10^2

Karatsuba                    2,3                N^1.585                              10^2 10^3               [1,4]

3-way Toom-Cook                         N^1.465                               > 10^3                        [1,4]

16-way Toom-Cook                       N^1.239                               > 10^3                        [1]

Sch¨onhage NTT                           N logN log logN          > 10^3                        [2,3,4]

Strassen FFT            -                      N log^2 N                    > 10^3                        [1,3,5]

NTT是数理论上的一种转换,FFT是快速傅利叶变换)。Starassen  FFT算法因为是使用浮点计算法(arithmetic),所以对于非常大的参数它的准确性无法保证[4],因此没有被我提到实现使用,但是他的是最好的。实现1只使用了basecase乘法,因此对于大参数来说它的性能很差。在实现3里面,我发现16-way Toom-Cook算法比Sch¨onhage NTT更快(直到一些我不知道的非常大的参数)

对于除法和残余递归算法(remainder recursive algorithms)对于大参数有着更好的性能,而且在输入输出流(instream and outstream)来说也是一样的。意味着从二进制转换到十进制也是一样有着好的性能,而且反之亦然。

 

3.4       汇编的使用

在实现1里没有使用汇编,因此可以运行在任何平台上。实现2用了汇编,而且它是一个为了在类Unix平台运行的C语言编译器,它使用的汇编也是。实现3用了汇编,而且它是为了在Borland C++ Bulider 它的Turbo汇编编译器使用的。

 

3.5       总结

当的确需要从上述3个存在的实现中选一个的话,以下的情况可能要被考虑。因为实现1仅仅受限于大概10^5位(我不清楚为什么有这样的限制存在),这个实现作为无限制精确整数可能不是那么有用。而且对于很大的整数它的性能不好。实现2可能更多的在类Unix平台被选择,所有它需要的看起来是一个C++的封装。实现3可能更多地在Wintel平台被选择。另一个选项是与商业的代数运算程序开发商合作。

 

4           提案正文

4.1       需求

integer类的需求由包含在提案头文件的界面(interface)提供。这些断言(assertion)和之前之后的情况(pre/post-condition)都是很明显的,对于平均复杂度的需要也提供了,N 是数据的十进制或二进制位数:

 

class integer

{

private:

unsigned int *data, *maxdata;

signed char thesign;

public: // Complexity:

integer(); // 1

integer( int ); // 1

integer( double ); // 1

integer( const char * ); // < N^2 (see 3.4)

integer( const string & ); // < N^2 (see 3.4)

integer( const integer & ); // N

virtual ~integer(); // 1

const unsigned int size() const; // 1

integer &operator=( const integer & ); // N

integer &negate(); // 1

integer &abs(); // 1

integer &operator++(); // 1

integer &operator--(); // 1

const integer operator++( int ); // N

const integer operator--( int ); // N

integer &operator|=( const integer & ); // N

integer &operator&=( const integer & ); // N

integer &operator^=( const integer & ); // N

integer &operator<<=( unsigned int ); // N

integer &operator>>=( unsigned int ); // N

integer &operator+=( const integer & ); // N

integer &operator-=( const integer & ); // N

integer &operator*=( const integer & ); // < N^2 (see 3.4)

integer &operator/=( const integer & ); // < N^2 (see 3.4)

integer &operator%=( const integer & ); // < N^2 (see 3.4)

const integer operator-() const; // N

const integer operator<<( unsigned int ) const; // N

const integer operator>>( unsigned int ) const; // N

};

const bool operator==( const integer &, const integer & ); // N

const bool operator!=( const integer &, const integer & ); // N

const bool operator>( const integer &, const integer & ); // N

const bool operator>=( const integer &, const integer & ); // N

const bool operator<( const integer &, const integer & ); // N

const bool operator<=( const integer &, const integer & ); // N

const integer operator|( const integer &, const integer & ); // N

const integer operator&( const integer &, const integer & ); // N

const integer operator^( const integer &, const integer & ); // N

const integer operator+( const integer &, const integer & ); // N

const integer operator-( const integer &, const integer & ); // N

const integer operator*( const integer &, const integer & ); // < N^2 see 3.4)

const integer operator/( const integer &, const integer & ); // < N^2 see 3.4)

const integer operator%( const integer &, const integer & ); // < N^2 see 3.4)

const integer gcd( const integer &, const integer & ); // ?

const integer lcm( const integer &, const integer & ); // ?

ostream & operator<<( ostream &, const integer & ); // < N^2 (see 3.4)

istream & operator>>( istream &, integer & ); // < N^2 (see 3.4)

const int sign( const integer & ); // 1

const bool even( const integer & ); // 1

const bool odd( const integer & ); // 1

const bool getbit( const integer &, unsigned int ); // 1

void setbit( integer &, unsigned int ); // 1

void clearbit( integer &, unsigned int ); // 1

const unsigned int lowestbit( const integer & ); // 1

const unsigned int highestbit( const integer & ); // 1

const integer abs( const integer & ); // N

const integer sqr( const integer & ); // < N^2 (see 3.4)

const integer pow( const integer &, const integer & ); // ?

const integer factorial( const integer & ); // ?

// floor of the square root, like int sqrt( int )

const integer sqrt( const integer & ); // ?

// random integer >= first and < second argument

const integer random( const integer &, const integer & ); // ?

const int toint( const integer & ); // 1

const double todouble( const integer & ); // 1

 

为了错误控制,可能需要创建一个独立的exception:

class integer_exception : public exception

{ public:

enum type_of_error {

error_unknown, error_overflow,

error_divbyzero, error_memalloc, ...

};

integer_exception( type_of_error = error_unknown, ... );

virtual const char * what () const;

private:

type_of_error error_type;

string error_description;

};

5           没有解决的问题

5.1     需要的gcd,lcm,sqrt,pow,factorial复杂度还不清楚。

5.2     全部的无限长精确整数性能应该与著名的商业数学软件进行比较。

5.3     无限长精确整数上,真实的精度应该可以被定义。

 

6           引用

1. D.E. Knuth, The Art of Computer Programming, Volume 2 (1998).

2. P. Zimmermann, An implementation of Sch¨onhage’s multiplication algorithm (1992).

3. A. Sch¨onhage and V. Strassen, Computing 7 (1971) 281.

4. Free Software Foundation, Gnu MP manual ed. 4.1.2 (2002).

5. http://numbers.computation.free.fr/Constants/Algorithms/fft.html

6. http://www.swox.com/gmp

7. http://www.math.utah.edu/docs/info/libg++ 20.html

 

 

分类:  C++ 
标签:  C++ 

Posted By 九天雁翎 at 九天雁翎的博客 on 2007年08月16日

前一篇: 和实现有关的相同字符串存储方式检验的思考及c-string字符串 后一篇: 很久没有来了,我可不是在玩哦