Thanks for the positive posts! Anyway here's the last update on this class. In this update I fix even more off-by-1 errors (in the byte shifting code), I added division and modulus operators and fixed a bug in the comparison code where the comparison would stop if one of the two numbers had more digits.
I've also added a destructor and 2 new support operators for bit- and bytewise shifting and a function to extract the remainder of a previous devision.
The division code is not the of the same quality as the other operators, since devision was too complex to do bytewise (sheer recursiveness) I used repeated subtraction to find the answer. Once you start dividing any number by another number with more then 16 digits you're in trouble. When the divisor is smaller then 16 digits the division is fast enough. If you want to optimize I suggest changing the multiplication operator and the copy constructor in such a way that they don't grow your number when multiplying with another instance of this class (it currently does this to accommodate to the possible increase in digits due to the multiplication)
For instance if you were to multiply 00001 and 00001 you'd get: 000000001.
ExtendedArithmetic.cpp
Code:
#include "ExtendedArithmetic.h"
#include <iostream>
ArbitraryArithmetic::ArbitraryArithmetic(long Length, unsigned __int64 n){
MyLength = Length;
Number = new unsigned char[ Length ];
int i = 0;
if( n ){
unsigned char* nPtr = (unsigned char*) &n;
int Lesser = sizeof( unsigned __int64 ) < MyLength ? sizeof( unsigned __int64 ) : MyLength;
for( i = 0; i < Lesser; i++){
Number[i] = nPtr[i];
}
if( Lesser == MyLength)
return;
}
for(; i < MyLength; i++){
Number[i] = 0;
}
return;
}
ArbitraryArithmetic::ArbitraryArithmetic( ArbitraryArithmetic &n ){
MyLength = n.getsize();
Number = new unsigned char[ MyLength ];
memcpy( (void*) Number, (void*) n.getnumber(), MyLength );
return;
}
ArbitraryArithmetic::~ArbitraryArithmetic(){
delete [] Number;
}
void ArbitraryArithmetic::print(){
for( int i = MyLength-1; i >= 0 ; i--)
printf("%.2x", Number[i]);
printf("\n");
}
long ArbitraryArithmetic::getsize() const{
return MyLength;
}
unsigned __int64 ArbitraryArithmetic::getremainder() const{
return Remainder;
}
unsigned __int64* ArbitraryArithmetic::touint64(){
return (unsigned __int64*)Number;
}
unsigned char* ArbitraryArithmetic::getnumber() const{
return Number;
}
void ArbitraryArithmetic::operator =(unsigned __int64 n){
if( MyLength < sizeof( unsigned __int64) ){
delete [] Number;
Number = new unsigned char[ sizeof( unsigned __int64) ];
}
memcpy( (void*)Number, (void*)&n, sizeof( unsigned __int64) );
for(int i = sizeof( unsigned __int64); i < MyLength; i++)
Number[i] = 0;
}
void ArbitraryArithmetic::operator =(const ArbitraryArithmetic &n){
//if I am myself :p
if(&n == this)
return;
int Lesser = n.getsize() < MyLength ? n.getsize() : MyLength;
if( Lesser == MyLength && MyLength != n.getsize() ){
MyLength = n.getsize();
if( Number )
delete [] Number;
Number = new unsigned char[ MyLength ];
memcpy( (void*)Number, (void*)n.getnumber(), MyLength );
} else {
unsigned char* nPtr = n.getnumber();
int i = 0;
for( i = 0; i < Lesser; i++)
Number[i] = nPtr[i];
for( i; i < MyLength; i++)
Number[i] = 0;
}
return;
}
void ArbitraryArithmetic::shift( int numdigits ){
if( !numdigits ) return;
Number[ MyLength-1 ] = 0;
do{
for(int i = MyLength-2; i >= 1; i--){
Number[i] = Number[i-1];
}
Number[0] = 0;
} while( --numdigits );
return;
}
void ArbitraryArithmetic::bitshift( int bits ){
if( !bits ) return;
bool bitset;
do{
unsigned char* tmp = new unsigned char[ MyLength ];
memset((void*)tmp, 0, MyLength);
for(int i = (MyLength*8)-1; i > 0; i--){
bitset = Number[i/8] & (1 << i-((i/8)*8) );
if( bitset ){
i++;
tmp[i/8] |= 1 << (i-((i/8)*8));
i--;
}
}
delete [] Number;
Number = tmp;
} while ( --bits );
}
void ArbitraryArithmetic::trim( int numdigits ){
if( numdigits <= 0 || MyLength <= numdigits )
return;
MyLength -= numdigits;
unsigned char* temp = new unsigned char[ MyLength ];
memcpy( (void*)temp, (void*)Number, MyLength );
delete [] Number;
Number = temp;
return;
}
void ArbitraryArithmetic::chop( int numdigits ){
if( numdigits <= 0 || MyLength <= numdigits )
return;
MyLength -= numdigits;
unsigned char* temp = new unsigned char[ MyLength ];
memcpy( (void*)temp, (void*)&Number[numdigits], MyLength );
delete [] Number;
Number = temp;
return;
}
unsigned __int64 ArbitraryArithmetic::getremainder(){
return Remainder;
}
int ArbitraryArithmetic::Compare(unsigned __int64 n) const{
int i;
for (i = MyLength-1; i >= 1; i--){
if (Number[i] != 0)
return 1;
}
return Number[0] > n ? 1 : Number[0] < n ? -1 : 0;
}
int ArbitraryArithmetic::Compare(const ArbitraryArithmetic &n) const{
int i;
unsigned char* nPtr = n.getnumber();
int Lesser = n.getsize() < MyLength ? n.getsize() : MyLength;
if (MyLength > n.getsize()){
for (i = MyLength-1; i >= n.getsize(); i--){
if (Number[i] != 0){
return 1;
}
}
}
if (n.getsize() > MyLength){
for (i = n.getsize()-1; i >= MyLength; i--){
if (nPtr[i] != 0){
return -1;
}
}
}
i = Lesser-1;
while (true){
if (Number[i] > nPtr[i]){
return 1;
}
if (Number[i] < nPtr[i]){
return -1;
}
if (i < 0){
return 0;
}
i--;
}
return 0;
}
void ArbitraryArithmetic::operator -=(unsigned __int64 n){
unsigned char* nPtr = (unsigned char*) &n;
int Lesser = sizeof( unsigned __int64 ) < MyLength ? sizeof( unsigned __int64 ) : MyLength;
for( int i = 0; i < Lesser; i++){
if( Number[i] < nPtr[i] ){
for(int y = 1; y+i < Lesser; y++){
if( Number[i+y] != 0 ){
Number[i+y]--;
break;
} else {
Number[i+y] = 0xFF;
}
}
Number[i] = ( 0x100 - (nPtr[i] - Number[i]) );
} else {
Number[i] -= nPtr[i];
}
}
}
void ArbitraryArithmetic::operator -=(const ArbitraryArithmetic &n){
unsigned char* nPtr = (unsigned char*) n.getnumber();
int Lesser = n.getsize() < MyLength ? n.getsize() : MyLength;
for( int i = 0; i < Lesser; i++){
if( Number[i] < nPtr[i] ){
for(int y = 1; y+i < MyLength; y++){
if( Number[i+y] != 0 ){
Number[i+y]--;
break;
} else {
Number[i+y] = 0xFF;
}
}
Number[i] = ( 0x100 - (nPtr[i] - Number[i]) );
} else {
Number[i] -= nPtr[i];
}
}
}
void ArbitraryArithmetic::operator +=(unsigned __int64 n){
unsigned short r = 0;
unsigned char* nPtr = (unsigned char*) &n;
unsigned char* rPtr = (unsigned char*) &r;
int Lesser = sizeof( unsigned __int64 ) < MyLength ? sizeof( unsigned __int64 ) : MyLength;
for(int i = 0; i < Lesser; i++){
r = Number[i] + nPtr[i];
if( r > 0xff ){
Number[i] = rPtr[0];
for(int y = 1; y+i < MyLength; i++){
if( rPtr[1] != 0){
if( y+i < Lesser )
r = Number[i+y] + nPtr[i+y] + rPtr[1];
else
r = Number[i+y] + rPtr[1];
Number[i+y] = rPtr[0];
} else {
break;
}
}
} else {
Number[i] += nPtr[i];
}
}
}
void ArbitraryArithmetic::operator +=(const ArbitraryArithmetic &n){
unsigned short r = 0;
unsigned char* nPtr = (unsigned char*) n.getnumber();
unsigned char* rPtr = (unsigned char*) &r;
int Lesser = n.getsize() < MyLength ? n.getsize() : MyLength;
for(int i = 0; i < Lesser; i++){
r = Number[i] + nPtr[i];
if( r > 0xff ){
Number[i] = rPtr[0];
for(int y = 1; y+i < MyLength; i++){
if( rPtr[1] != 0){
if( y+i < Lesser )
r = Number[i+y] + nPtr[i+y] + rPtr[1];
else
r = Number[i+y] + rPtr[1];
Number[i+y] = rPtr[0];
} else {
break;
}
}
} else {
Number[i] += nPtr[i];
}
}
}
void ArbitraryArithmetic::operator *=( __int64 n){
if( n > 1 ){
unsigned char* nPtr = (unsigned char*) &n;
ArbitraryArithmetic r( 32, 0 );
ArbitraryArithmetic rr( 32, 0 );
ArbitraryArithmetic rrr( 32, 0 );
rrr = 0;
for(int i = 0; i < MyLength; i++){
rr = 0;
for(int y = 0; y < sizeof( unsigned __int64 ); y++){
r = 0;
r += Number[i] * nPtr[y];
if( y >= 1 )
r.shift( y );
rr += r;
}
if( i >= 1 )
rr.shift( i );
rrr += rr;
}
*this = rrr;
} else if( n == 1 ) {
return;
} else {
for(int i = 0; i != MyLength; i++)
Number[i] = 0;
return;
}
return;
}
void ArbitraryArithmetic::operator *=(const ArbitraryArithmetic &n){
int Lesser = n.getsize() < MyLength ? n.getsize() : MyLength;
int Greater = Lesser < MyLength ? MyLength : Lesser;
ArbitraryArithmetic r( Greater*2, 0 );
ArbitraryArithmetic rr( Greater*2, 0 );
ArbitraryArithmetic rrr( Greater*2, 0 );
if( n > 1 ){
unsigned char* nPtr = (unsigned char*) n.getnumber();
rrr = 0;
for(int i = 0; i < MyLength; i++){
rr = 0;
for(int y = 0; y < n.getsize(); y++){
r = 0;
r += Number[i] * nPtr[y];
if( y >= 1 )
r.shift( y );
rr += r;
}
if( i >= 1 )
rr.shift( i );
rrr += rr;
}
*this = rrr;
} else if( n == 1 ) {
return;
} else {
for(int i = 0; i < MyLength; i++)
Number[i] = 0;
return;
}
return;
}
void ArbitraryArithmetic::operator /=(__int64 n){
ArbitraryArithmetic r( 32, n );
if( r < 1 ){
Remainder = 0;
*this = 0;
}
if( r == *this ){
Remainder = 0;
*this = 1;
return;
}
if( r > *this ){
Remainder = n;
*this = 0;
return;
}
unsigned __int64 qotient = 1;
while( true ){
qotient++;
r = qotient*n;
if( r == *this ){
Remainder = 0;
*this = qotient;
return;
}
if( r > *this ){
qotient--;
r = qotient*n;
Remainder = ( *this->touint64() - *r.touint64() );
*this = qotient;
return;
}
}
return;
}
void ArbitraryArithmetic::operator /=(const ArbitraryArithmetic &n){
if( n < 1 ){
Remainder = 0;
*this = 0;
return;
}
if( n == *this ){
Remainder = 0;
*this = 1;
return;
}
if( n > *this ){
*this = n;
Remainder = *this->touint64();
*this = 0;
return;
}
ArbitraryArithmetic qotient( n.getsize(), 1);
ArbitraryArithmetic r( n.getsize()*2, 0);
while( true ){
qotient += 1;
r = qotient;
r *= n;
r.trim( r.getsize() - this->getsize() );
if( r == *this ){
Remainder = 0;
*this = qotient;
return;
}
if( r > *this ){
qotient -= 1;
r = qotient;
r *= n;
r.trim( r.getsize() - this->getsize() );
Remainder = ( *this->touint64() - *r.touint64() );
*this = qotient;
return;
}
}
return;
}
void ArbitraryArithmetic::operator %=(__int64 n){
ArbitraryArithmetic r( *this );
r /= n;
*this = r.getremainder();
return;
}
void ArbitraryArithmetic::operator %=(const ArbitraryArithmetic &n){
ArbitraryArithmetic r( *this );
r /= n;
*this = r.getremainder();
return;
}
ExtendedArithmetic.h
Code:
#ifndef EXT_AR_H
#define EXT_AR_H
/*
infinite-precision arithmetic class
by SCHiM
*/
class ArbitraryArithmetic{
long MyLength;
unsigned __int64 Remainder;
unsigned char* Number;
public:
//constructor
ArbitraryArithmetic(long Lenght, unsigned __int64 n);
ArbitraryArithmetic( ArbitraryArithmetic &);
~ArbitraryArithmetic();
//debug/verification
void print();
//information
long getsize() const;
unsigned __int64 getremainder() const;
unsigned char* getnumber() const;
unsigned __int64 *touint64();
//support operators
void shift( int numdigits );
void bitshift( int bits );
void trim( int numdigits );
void chop( int numdigits );
unsigned __int64 getremainder();
int Compare(unsigned __int64 n) const;
int Compare(const ArbitraryArithmetic &) const;
//assignment operators
void operator = (unsigned __int64 n);
void operator = (const ArbitraryArithmetic &);
void operator -= (unsigned __int64 n);
void operator -= (const ArbitraryArithmetic &);
void operator += (unsigned __int64 n);
void operator += (const ArbitraryArithmetic &);
void operator *= ( __int64 n);
void operator *= (const ArbitraryArithmetic &);
void operator /= (const __int64 n);
void operator /= (const ArbitraryArithmetic &);
void operator %= (const __int64 n);
void operator %= (const ArbitraryArithmetic &);
//comparason operators
bool ArbitraryArithmetic::operator == (unsigned __int64 n) const {return Compare(n) == 0;}
bool ArbitraryArithmetic::operator != (unsigned __int64 n) const {return Compare(n) != 0;}
bool ArbitraryArithmetic::operator > (unsigned __int64 n) const {return Compare(n) > 0;}
bool ArbitraryArithmetic::operator >= (unsigned __int64 n) const {return Compare(n) >= 0;}
bool ArbitraryArithmetic::operator < (unsigned __int64 n) const {return Compare(n) < 0;}
bool ArbitraryArithmetic::operator <= (unsigned __int64 n) const {return Compare(n) <= 0;}
bool ArbitraryArithmetic::operator == (const ArbitraryArithmetic &n) const {return Compare(n) == 0;}
bool ArbitraryArithmetic::operator != (const ArbitraryArithmetic &n) const {return Compare(n) != 0;}
bool ArbitraryArithmetic::operator > (const ArbitraryArithmetic &n) const {return Compare(n) > 0;}
bool ArbitraryArithmetic::operator >= (const ArbitraryArithmetic &n) const {return Compare(n) >= 0;}
bool ArbitraryArithmetic::operator < (const ArbitraryArithmetic &n) const {return Compare(n) < 0;}
bool ArbitraryArithmetic::operator <= (const ArbitraryArithmetic &n) const {return Compare(n) <= 0;}
};
#endif
.
