very large numbers

In the same file, with division, it should be noted that repeated subtraction will not work. The numbers i am using are HUGE:

25195908475657893494027183240048398571429282126204
03202777713783604366202070759555626401852588078440
69182906412495150821892985591491761845028084891200
72844992687392807287776735971418347270261896375014
97182469116507761337985909570009733045974880842840
17974291006424586918171951187461215151726546322822
16869987549182422433637259085141865462043576798423
38718477444792073993423658482382428119816381501067
48104516603773060562016196762561338441436038339044
14952634432190114657544454178424020924616515723350
77870774981712577246796292638635637328991215483143
81678998850404453640235273819513786365643912120103
97122822120720357

or sometimes larger...also, the work will be done by a network of computers, but still with numbers this large, time is valuble...

It sounds like you are working on a serious project. Not to offend anyone who has posted ideas, but I wouldn't bet on finding expert advice for this particular problem here. The best advice I think you can use is either (a) purchase a library meant for this type of use or (b) spend some time researching in a library or possibly on the web about how to perform division and multiplication with large numbers. One reference is this chapter from "Numerical Recipes in C" (http://www.library.cornell.edu/nr/bookcpdf/c20-6.pdf). It's not C++, and I believe there are more efficient FFT algorithms out there, but this chapter will at least give you an idea about how to best perform these operations.

- Kevin

BTW, I did some rough number crunching given the outlines of complexity in the chapter from Numerical Recipes. If you did byte-wise operations, NR's algorithms would require 28 times less operations than doing it by with "familliar elementary school" methods using byte-wise operations. Using 32-bit operations would provide you with even better performance. As you said, time is valuable.

Check out this library ( http://www.shoup.net/ntl/).

And another note...

The best algorithm for computing the factorial of huge numbers is called the method of binary splitting. With binary splitting huge numbers are broken down and adjacent pairs are multiplied first, successively increasing the precision with following stages.

Sincerely, Chris.

:)

P.S. It might take a while to study up on all this stuff.

thanks for the help, subtractions works(kind of) here is current code:

// when completed, will have { + , - , * , / , > , < , == , <= , >= , %}

//=================INCLUDES============
#include <stdlib.h>
#include <iostream.h>
#include <string.h>
//====================================

//=================CONSTANTS===========
#define sz 10000
//====================================

//=================CLASSES=============
class verylong
{
private:
char vlstr[sz];// string that holds the individual digits
int vlen; // length of verylong string
verylong multdigit(int);
verylong mult10(verylong);
public:
verylong()
{
vlstr[0] = '\0';
vlen = 0;
}
verylong(char s[sz])
{
strcpy(vlstr,s);
vlen = strlen(s);
}
verylong(unsigned long n)
{
ltoa(n,vlstr,10);
strrev(vlstr);
vlen = strlen(vlstr);
}
void putvl(); // displays verylong
void getvl(); // input verylong from user
void borrow(int, verylong); // borrow for subtraction
verylong operator + (verylong); // adding verylongs
verylong operator * (verylong); // multiply verylongs
verylong operator - (verylong); // subtract verylongs
verylong operator / (verylong); // devide verylongs
int compare (verylong); // compares verylongs to see which is greater
};
//====================================

void verylong::putvl()
{
char temp[sz];
strcpy(temp,vlstr);
cout << strrev(temp);
}

void verylong::getvl()
{
cin >> vlstr;
vlen = strlen(vlstr);
strrev(vlstr);
}

verylong verylong::operator + (verylong v)
{
char temp[sz];
int maxlen = (vlen > v.vlen) ? vlen : v.vlen;
int carry = 0;
int j;
for (j = 0;j < maxlen;j++)
{
int d1 = (j > vlen - 1) ? 0 : vlstr[j] - '0';
int d2 = (j > v.vlen - 1) ? 0 : v.vlstr[j] - '0';
int digitsum = d1 + d2 + carry;
if (digitsum >= 10)
{
digitsum -= 10;
carry = 1;
}
else
carry = 0;
temp[j] = digitsum + '0';
}
if (carry == 1)
{
temp[j++] = '1';
}
temp[j] = '\0';
return verylong(temp);
}

verylong verylong::operator - (verylong v)
{
char temp[sz];
int maxlen = (vlen > v.vlen) ? vlen : v.vlen;
int j;
for (j = 0;j < maxlen;j++)
{
int d1 = (j > vlen - 1) ? 0 : vlstr[j] - '0';
int d2 = (j > v.vlen - 1) ? 0 : v.vlstr[j] - '0';
if (d1 - d2 < 0)
{
borrow(j, v);
}
int difference = (d1 - d2) + '0';
temp[j] = difference;
}
temp[j] = '\0';
return verylong(temp);
}

verylong verylong::operator * (verylong v)
{
verylong pprod;
verylong tempsum;
for (int j = 0;j < v.vlen;j++)
{
int digit = v.vlstr[j] - '0';
pprod = multdigit(digit);
for (int k = 0;k < j;k++)
{
pprod = mult10(pprod);
}
tempsum = tempsum + pprod;
}
return tempsum;
}

verylong verylong::mult10(verylong v)
{
char temp[sz];
for (int j = v.vlen - 1;j >= 0;j--)
{
temp[j + 1] = v.vlstr[j];
temp[0] = '0';
temp[v.vlen + 1] = '\0';
}
return verylong(temp);
}

verylong verylong::multdigit(int d2)
{
char temp[sz];
int carry = 0;
int j;
for (j = 0;j < vlen;j++)
{
int d1 = vlstr[j] - '0';
int digitprod = d1 * d2;
digitprod += carry;
if (digitprod >= 10)
{
carry = digitprod / 10;
digitprod -= carry * 10;
}
else
carry = 0;
temp[j] = digitprod + '0';
}
if (carry != 0)
{
temp[j++] = carry + '0';
}
temp[j] = '\0';
return verylong(temp);
}

void verylong::borrow(int whatel, verylong v)
{
int d1;
int d2;
int x;// for compare();
d1 = vlstr[whatel] - '0';
d2 = vlstr[whatel + 1] - '0';
if (d2 > 0)
{
d1 += 10;
d2 -= 1;
}
else
{
borrow(whatel + 1, v);
}
vlstr[whatel] = d1 + '0';
vlstr[whatel + 1] = d2 + '0';
d1 = v.vlstr[whatel] - '0';
d2 = v.vlstr[whatel + 1] - '0';
if (d2 > 0)
{
d1 += 10;
d2 -= 1;
}
else
{
borrow(whatel + 1, v);
}
v.vlstr[whatel] = d1 + '0';
v.vlstr[whatel + 1] = d2 + '0';
d1 = vlstr[whatel] - '0';
d2 = vlstr[whatel + 1] - '0';
if (d2 > 0)
{
d1 += 10;
d2 -= 1;
}
else
{
borrow(whatel + 1, v);
}
vlstr[whatel] = d1 + '0';
vlstr[whatel + 1] = d2 + '0';
}

int verylong::compare(verylong v)// probably overload ==, <, >, <=, >= later
{
int maxlen = (vlen > v.vlen) ? vlen : v.vlen;
if (vlen > v.vlen)
{
return 1; // greater value is this class rather than object passed
}
if (vlen < v.vlen)
{
return 2; // greater value is the value passed
}
int y = maxlen;
if ((vlen == v.vlen) && y > 0)
{
int x = 0;
y = maxlen;
while (x == 0)
{
x = v.vlstr[y] - vlstr[y];
y++;
}
if (x < 0)
{
return 1;
}
if (x > 0)
{
return 2;
}
if (x == 0)
{
return 0;
}
}
}

i appreciate the libraries of large numbers, but as what i am doing requires me to write the library myself

Well, there is an easy test. Install pari/gp on your machine and test it with numbers of that range. I would say that 1 second for 500 digits is quite slow. But depending on what your goal is, it may be OK.

Thabk guys.

KevinHall,
I knew it would be ended with math skills, which unfortunately
I lack of... those 'O(n*log(n)...' are beyond my skills.
could you please explain yourself in more simple terms?

by the way, Yves, there is a table of performance example of pari that I don't quiet understand, could you tell me please where
falls a 500*500 digits in there?

http://www.math.u-psud.fr/~belabas/pari/doc/faq.html#largeint

I won't even try to compete the speed of a solution made by
mathematicians/algorithms-engeneers nor use assembler routines, I did it for practice.
On the other hand, I don't mind to improve it as long as I don't need to rewrite it from scratch.

Thanks in advance,
Guy

Guysl,

Statements such as "<some algorithm> scales as O(log(n))" represent how complex a certain algorithm is computationally -- thus it is given the term "complexity". (This is not how complex an algorithm is to understand ;) -- just how complex it is for a computer to crunch). Remember this one, because it is very important to the idea of algorithms -- and it works itself into many places in modern programming such as the choice of an STL containter.

OK, now for the explanation. Let's say we have three algorithms A, B, and C that all try to accomplish the same thing. And we have three data sets x(1 element), y(10 elements), and z(100 elements). For the sake of multiplying large numbers, these sets could represent the number of decimal digits. Now let's say that all three algorithms compute set x with one computation. But for set y, the algorithms are not equally efficient. A must make 100 computations, B does much better with only 10 compuations, and C does it in a speedy 2 computations. For data set z, A makes 10000 compuations, B 100 computations, and C 3 computations. Let's make a table to summarize:
| 1 | 10 | 100
-+--+---+---
A| 1 | 100 | 10000
B| 1 | 10 | 100
C| 1 | 2 | 3
You may notice a pattern. For A, the number of compuations is equal to the square of the number of elements. For B, it is equal to the number of elements. For C it is equal to 1 + log10(# of elements). Or in summary:
let n = the number of elements.

computations_A(n) = n^2
computations_B(n) = n
computations_C(n) = 1+log10(n)
This is where we get the complexity. A, has the complexity of O(n^2). B has the complexity of O(n) [also known as linear complexity], and C has the complexity of O(log(n)).

That explains the basics. Complexity is best used to tell how an algorithm responds to the growth of a data set and is actually very poor for making absolute statements about speed. I am about to explain why. If you want to stop reading here, feel free to.

Let's analyze a few other imaginary algorithms D,E,F, and G. And here is the equations for the number of compuations for each:
let n = the number of elements.

computations_D(n) = 5*n^2-4*n
computations_E(n) = 10*n+3*log(n)+5
computations_F(n) = 100*log10(n)+50000
computations_G(n) = 100000

How do we describe these? D and E have multiple n's in the equation. Well, we measure complexity by the worst set with n in it. So D has O(n^2) complexity. Why not O(5*n^2)? Well, without going further into detail, it just isn't. The coefficients just aren't listed. So E has O(n) complexity, F has O(log(n)), and G has constant complexity. Now which would you rather use for small numbers? The complexities would suggest that we use G and that D would be worst. However, since we have the equations for for the number of calculations, we would find that for very small numbers D is best, and for small to large numbers E is best. Only when n becomes very large does F become a preferable choice. And only when n is a behemoth is G the best. I didn't write this last part to confuse you. The coefficients don't swing things that much in every day algorithms. But it does reinforce my original statement. That complexity tells how an algorithm behaves when its data set grows -- not how well it actually performs.