为中国数学做贡献，写一个大数计算类

pdshjf

[这个贴子最后由pdshjf在 2008/11/19 08:17pm 第 1 次编辑]

以下是我二月份写的一个C++大数计算类，请大家多提宝贵意见！
#include "StdAfx.h"
#include ".\super.h"
Super::Super()
{
BitLength = 0;
Fat = NULL;
}
Super::Super(UINT val)
{
BitLength = 1;
Fat = new UINT[BitLength];
if(Fat == NULL)throw "Memory error!";
Fat[0] = val;
}
Super::Super(Super &val)
{
BitLength = val.BitLength;
Fat = new UINT[BitLength];
if(Fat == NULL)throw "Memory error!";
memcpy(Fat,val.Fat,BitLength*sizeof(UINT));
}

//接收一个字符串，以前缀0x来判断是十进制还是十六进制
Super::Super(char* val)
{
UINT len = UINT(strlen(val));
char ch;
BYTE* tmp;
if(val[0] == ';0'; && val[1] == ';x'; || val[1] == ';X';)
{
UINT j = 0;
BitLength = ((len-1)/2+(sizeof(UINT)-1))/sizeof(UINT);
Fat = new UINT[BitLength];
if(Fat == NULL)throw "Memory error!";
memset(Fat,0,BitLength*sizeof(UINT));
tmp = (BYTE*)Fat;
for(int i=len-1;i>=2;i--)
{
if(val>=';0'; && val<=';9';)
{
if(j%2 == 0)
tmp[j/2] = val & 0x0f;
else
tmp[j/2] |= (val & 0x0f)<<4;
}
else
{
ch = val | 0x20;
if(ch>=';a'; && ch<=';f';)
{
if(j%2 == 0)
tmp[j/2] = (val & 0x0f) + 9;
else
tmp[j/2] |= ((val & 0x0f) + 9) << 4;
}
else
{
delete []Fat;
Fat = NULL;
throw "String Valuse Erroe!";
return;
}
}
j++;
}
}
else
{
Super rank(1);
BitLength = 1;
Fat = new UINT[BitLength];
if(Fat == NULL)throw "Memory error!";
Fat[0] = 0;
for(int i=len-1;i>=0;i--)
{
if(val>=';0'; && val<=';9';)
{
*this = *this + Super(UINT(val&0x0f))*rank;
}
else
{
delete []Fat;
Fat = NULL;
throw "String Valuse Erroe!";
return;
}
rank = rank * 10;
}
}
}
Super::~Super(void)
{
if( Fat != NULL)delete []Fat;
}

void Super:perator =(Super val)
{
if(BitLength != val.BitLength)
{
if (Fat != NULL)delete []Fat;
BitLength = val.BitLength;
Fat = new UINT[BitLength];
if(Fat == NULL)throw "Memory error!";
}
memcpy(Fat,val.Fat,BitLength*sizeof(UINT));
}

Super Super:perator+(Super val)
{
Super result;
if(BitLength < val.BitLength)
result.BitLength = val.BitLength + 1;
else
result.BitLength = BitLength + 1;
result.Fat = new UINT[result.BitLength];
if(result.Fat == NULL)throw "Memory error!";
memset(result.Fat,0,result.BitLength*sizeof(UINT));
for(UINT i=0;i<result.BitLength-1;i++)
{
if(i>=BitLength)
{
result.Fat = result.Fat + val.Fat;
continue;
}
if(i>=val.BitLength)
{
result.Fat = result.Fat + Fat;
continue;
}
result.Fat = result.Fat + Fat + val.Fat;
if(result.Fat<Fat && result.Fat<val.Fat)
result.Fat[i+1] = 1;
}
for(UINT i=result.BitLength-1;i>0;i--)
{
if(result.Fat == 0)
result.BitLength--;
else
break;
}
return result;
}
Super Super:perator-(Super val)
{
Super result;
UINT overflow = 0;
if(Compare(&val) >= 0)
{
result.BitLength = BitLength;
result.Fat = new UINT[result.BitLength];
if(result.Fat == NULL)throw "Memory error!";
memset(result.Fat,0,result.BitLength*sizeof(UINT));
}
else
{
throw "Be Subtrahend Oversize";
return result;
}
for(UINT i=0;i<result.BitLength;i++)
{
if(i<val.BitLength)
result.Fat = Fat - val.Fat - overflow;
else
result.Fat = Fat - overflow;
if(overflow)
{
if (result.Fat >= Fat)
overflow = 1;
else
overflow = 0;
}
else
{
if (result.Fat > Fat)
overflow = 1;
else
overflow = 0;
}
}
for(UINT i=result.BitLength-1;i>0;i--)
{
if(result.Fat == 0)
result.BitLength--;
else
break;
}
return result;
}
Super Super ::operator*(Super val)
{
Super result;
UINT i,j,tmp;
__int64 a;
if(val == UINT(0) || *this == UINT(0)) return UINT(0);
result.BitLength = BitLength + val.BitLength;
result.Fat = new UINT[result.BitLength];
if(result.Fat == NULL)throw "Memory error!";
memset(result.Fat,0,result.BitLength*sizeof(UINT));
//做移位乘法运算
tmp = 0;
for(i=0;i<val.BitLength;i++)
{
for(j=0;j<BitLength;j++)
{
a = Fat[j];
a *=  val.Fat;
tmp = UINT(result.Fat[j+i] + a);
if(tmp < result.Fat[j+i])
result.Fat[j+i+1]++;
result.Fat[j+i] = tmp;
tmp = UINT(result.Fat[j+i+1] + (a>>32));
if(tmp < result.Fat[j+i+1])
result.Fat[j+i+2]++;
result.Fat[j+i+1] = tmp;
}
}
for(UINT i=result.BitLength-1;i>0;i--)
{
if(result.Fat == 0)
result.BitLength--;
else
break;
}
return result;
}
Super Super::operator/(Super val)
{
Super result,tmp,move;
UINT count = 0;
UINT i,j,bitmove,mul;
UINT uint_bit = sizeof(UINT)*8;
int S;
//判断除数是否为0
if(val.BitLength == 1 && val.Fat[0] == 0)
{
throw "Divisor is zero";
return result;
}
//如果除数大于被除数直接返回0
S = val.Compare(this);
if(S == 1) return UINT(0);
if(S == 0) return UINT(1);
//计算除数有效位
bitmove = 1<<(uint_bit-1);
mul = val.Fat[val.BitLength-1];
for(i=0;i<uint_bit;i++)
{
if((mul & (bitmove>>i))==0)count++;
else break;
}
count = val.BitLength * uint_bit - count;
//初化结果
result.BitLength = BitLength - val.BitLength  + 1;
result.Fat = new UINT[result.BitLength];
if(result.Fat == NULL)throw "Memory error!";
memset(result.Fat,0,result.BitLength*sizeof(UINT));
//初化减数
move.BitLength = this->BitLength;
move.Fat = new UINT[move.BitLength];
if(move.Fat == NULL)throw "Memory error!";
//初始化被除数、除数和商值
bitmove = 1;
tmp = *this;
do
{
//查找被除数最高有效位
i = tmp.BitLength * uint_bit;
bitmove = 1<<(uint_bit-1);
mul = tmp.Fat[tmp.BitLength-1];
for(j=0;j<uint_bit;j++)
{
if((mul & (bitmove>>j)) == 0)i--;
else break;
}
if(i<count)break;
i -= count;
LOOP:
//确定减数的位置
memset(move.Fat,0,move.BitLength*sizeof(UINT));
for(UINT k=0;k<val.BitLength;k++)
{
move.Fat[i/uint_bit+k] += val.Fat[k]<<(i%uint_bit);
if(i%uint_bit)
if(val.Fat[k] >> (uint_bit-(i%uint_bit)))
move.Fat[i/uint_bit+k+1] = val.Fat[k]>>(uint_bit-(i%uint_bit));
}
for(UINT k=move.BitLength-1;k>0;k--)
{
if(move.Fat[k] ==0)move.BitLength--;
else break;
}
S = tmp.Compare(&move);
if(S == 1)
{
tmp = tmp - move;
result.Fat[i/uint_bit] |=  1 << (i%uint_bit);
}
if(S == 0)
{
result.Fat[i/uint_bit] |= 1 << (i%uint_bit);
break;
}
if(S == -1)
{
if(i == 0) break;
i--;
goto LOOP;
}
}while(i>0);
//规格化结果数据
for(i=result.BitLength-1;i>0;i++)
{
if(result.Fat == 0)result.BitLength --;
else break;
}
return result;
}
Super Super::operator%(Super val)
{
Super result,move;
UINT count = 0;
UINT i,j,bitmove,mul;
UINT uint_bit = sizeof(UINT)*8;
int S;
//判断除数是否为0
if(val.BitLength == 1 && val.Fat[0] == 0)
{
throw "Divisor is zero";
return result;
}
//如果除数大于被除数直接返回0
S = val.Compare(this);
if(S == 1) return *this;
if(S == 0) return UINT(0);
//计算除数有效位
bitmove = 1<<(uint_bit-1);
mul = val.Fat[val.BitLength-1];
for(i=0;i<uint_bit;i++)
{
if((mul & (bitmove>>i))==0)count++;
else break;
}
count = val.BitLength * uint_bit - count;
//初化结果
result = *this;
//初化减数
move.BitLength = this->BitLength;
move.Fat = new UINT[move.BitLength];
if(move.Fat == NULL)throw "Memory error!";
//初始化被除数、除数和商值
bitmove  = 1<<(uint_bit-1);
do
{
//查找被除数最高有效位
i = result.BitLength * uint_bit;
mul = result.Fat[result.BitLength-1];
for(j=0;j<uint_bit;j++)
{
if((mul & (bitmove>>j)) == 0)i--;
else break;
}
if(i<count)break;
i -= count;
LOOP:
//确定减数的位置
memset(move.Fat,0,move.BitLength*sizeof(UINT));
for(UINT k=0;k<val.BitLength;k++)
{
move.Fat[i/uint_bit+k] += val.Fat[k]<<(i%uint_bit);
if(i%uint_bit)
if(val.Fat[k] >> (uint_bit-(i%uint_bit)))
move.Fat[i/uint_bit+k+1] = val.Fat[k]>>(uint_bit-(i%uint_bit));
}
for(UINT k=move.BitLength-1;k>0;k--)
{
if(move.Fat[k] ==0)move.BitLength--;
else break;
}
S = result.Compare(&move);
if(S == -1)
{
if(i==0)break;
i--;
goto LOOP;
}
if(S == 0)
{
result = result - move;
break;
}
result = result - move;
}while(i>0);
//规格化结果数据
for(i=result.BitLength-1;i>0;i++)
{
if(result.Fat == 0)result.BitLength --;
else break;
}
return result;
}
int Super::Compare(Super *val)
{
if(BitLength > val->BitLength)return 1;
if(BitLength < val->BitLength)return -1;
for(int i=BitLength-1;i>=0;i--)
{
if(Fat == val->Fat)continue;
if(Fat > val->Fat)return 1;
if(Fat < val->Fat)return -1;
}
return 0;
}
BOOL Super::operator ==(Super val)
{
if(BitLength != val.BitLength)return FALSE;
for(int i=BitLength-1;i>=0;i--)
{
if(Fat == val.Fat)continue;
if(Fat != val.Fat)return FALSE;
}
return TRUE;
}
BOOL Super::operator >(Super val)
{
if(BitLength > val.BitLength)return TRUE;
if(BitLength < val.BitLength)return FALSE;
for(int i=BitLength-1;i>=0;i--)
{
if(Fat > val.Fat)return TRUE;
if(Fat < val.Fat)return FALSE;
}
return FALSE;
}
BOOL Super::operator <(Super val)
{
if(BitLength > val.BitLength)return FALSE;
if(BitLength < val.BitLength)return TRUE;
for(int i=BitLength-1;i>=0;i--)
{
if(Fat > val.Fat)return FALSE;
if(Fat < val.Fat)return TRUE;
}
return FALSE;
}
BOOL Super::IsEmpty()
{
if(BitLength == 0 || Fat == NULL) return TRUE;
else return FALSE;
}
char* Super::Outstr(HD hd)
{
if(hd == Hex)
{
UINT len = BitLength*sizeof(UINT);
char *result = new char[len*2+1];
result[len*2] = 0;
BYTE* po = (BYTE*)Fat;
po = po + len-1;
for(UINT i=0;i<len;i++)
{
if((*po >> 4) > 9)
result[i*2] = (*po >> 4) - 10 + ';A';;
else
result[i*2] = (*po >> 4) + ';0';;
if((*po & 0x0f) > 9)
result[i*2+1] = (*po & 0x0f) - 10 + ';A';;
else
                result[i*2+1] = (*po & 0x0f) + ';0';;
po--;
}
return result;
}
else
{
UINT len = BitLength * sizeof(UINT);
char *tmp = new char[len*3];
Super C,T;
UINT i=0;
C = *this;
while(C > UINT(0))
{
T = C % 10;
C = C / 10;
tmp = char(T.Fat[0] + ';0';);
i++;
}
tmp = 0;
char * result = new char[i+1];
result = 0;
for(UINT j=0;j<i;j++)
result[j] = tmp[i-j-1];
delete []tmp;
return result;
}
}

Landyer

既然要大家提意见，又要用积分买，搂主真不够意思

moranhuishou

下面引用由pdshjf在 2008/04/28 09:23pm 发表的内容：
(保密帖子)

很棒，可惜我看不大懂，能译成VB6.0语言吗？

Bardo

我觉得，如果要用这种类，目前有现成的，国产的有郭先强的HugeCalc
国际上有相当有名的GMP,CRYPT API等多种。
所以，不想看你的代码了。
有一点，国内写的10进制字串的，实际都不很快。大数计算类，通常是用的2^32进制用2^64的数组进行计算的。乘法使用了FFT，GMP则是用汇编的FFT，所以，快多了
国内写的10进制字串的转成数组的，开方都用的是平方和公式法。明显慢于铺地锦。

Bardo

下面引用由moranhuishou在 2008/09/27 04:10pm 发表的内容：
很棒，可惜我看不大懂，能译成VB6.0语言吗？

现在网上还有JAVASCRIPT的，专门有大数计算网站，完全用JS做的大数计算器

instemast

一个问题：
程序中的“=”和数学的“=”意义不同。
不知道，用数学方程如何分析程序代码？

pdshjf

很久没看自己的贴子了，还有这么多人关注，谢谢大家！
回答instemast朋友的问题：程序中的＝是赋值的意思，就是把等号右边计算的内容保存到左边的变量中，这和数学中的＝是不同的。

pdshjf

Bardo显是真的没看到程序代码，要是用十进制方法或字符串的形式进行大数计算，就根本没必要放这里献丑了。这个计算类是可变位长度，计算的位数只跟你系统内存的可用大小有关，其中没用到汇编，也没用fft，至于速度嘛我手头也没别人的大数计算程序，你可以自己编译一下试试。

instemast

[这个贴子最后由instemast在 2008/12/08 02:16am 第 1 次编辑]

下面引用由pdshjf在 2008/11/19 08:13pm 发表的内容：
很久没看自己的贴子了，还有这么多人关注，谢谢大家！
回答instemast朋友的问题：程序中的＝是赋值的意思，就是把等号右边计算的内容保存到左边的变量中，这和数学中的＝是不同的。

呵呵，在下是做游戏开发的。
最近感到，程序中滴“=”用起来实在辛苦（一个游戏通常有几十万行代码），而且修改起来就难上加难。所以我正在研究，用数学函数式（最好是一定程度的方程等式）来书写程序。系统自动生成算法去仿真所给的函数式（或者最好是方程式）。
（仿真，并非一般的“算法”那么简单，它需要每时每刻地计算，不停更新系统状态）
目前，在程序中用函数思想，的确可以减轻不少工作量，但是还不根本，而且速度也慢。
比如程序中有2个变量，我让他们永远保持一定的关系，比如 x == 3y ，
这用函数就可以非常方便，我只需要存储y变量， 而x每次都从y求出，这样很方便。
－－但是对于含有复杂方程式的问题，用函数式的方式编写，会有递规问题。
函数式可以看作半个方程式吧，我想解决的就是直接用一些方程式。。。