[Courses] A little tutorial about big numbers :)
Bidea Cristian
phaser_programmer at yahoo.com
Tue Nov 26 01:37:13 EST 2002
Hello everybody! This is my tutorial about big numbers. I hope you like it! Excuse my english :).
Working with big numbers
------------------------
[Part I]
Content
Part 1
- Introduction
- The BigNumber data type
- Reading a big number
- Printing a big number
- Initializing a big number
- How to compare two big numbers
- How to add big numbers
- How to substract big numbers
- At the end of part I
Part 2 [Some subjects that will be covered in part 2]
- How we multiply big numbers?
- How we divide big numbers?
- Other interesting stuff about big numbers
Introduction
------------
I saw that you've learned about many things in C. I saw that the calculator
problem generated a big interest among you, so I've decided to write a tutorial
about big numbers. And by the way, Mister KMKelvin you do a great job with
these lessons :).
In C you can add, multiply, divide ... integer numbers, floating numbers etc.
but these numbers have limits. For example you can't add numbers that have,
let's say, 100 digits. This kind of numbers are too big for C. You can't extend
int data type or any other data type, so what can we do in this case?
In this tutorial I will try to show you some programing techniques that will
help you working with big numbers.
If you find this interesting then please tell me and I will release the
second part of this tutorial.
The BigNumber data type
------------------------
We will use an array to memorize our big number. The element on the first
position is the element that tells how many digits our big number has. The rest
of the elements are the digits of our number. We will store the digits backwards.
In this way we will do the operations easyer.
-[ An example: ]-
Let's say that we have the number: 19923
And the array: int a[1000]
Now, we will store 19923 in this way
h[0] h[1] h[2] h[3] h[4] h[5]
5 3 2 9 9 1
h[0] is 5 because 19923 has 5 digits.
OK! Now let's see how we will declare this in a C program:
...
#define MAX 500
...
typedef int BigNumber[MAX];
Now, we have a "big number" data type. But this is useless if we can't do
nothing with it.
Reading a big number
--------------------
Reading a big number it's a simple task. We read a sequence of digits and
then we convert the sequence into a big number.
#include <ctype.h>
#include <stdio.h>
...
void readbignumber(BigNumber N)
{
/* chrtoint converts characters '0','1','2',...,'9' into digits*/
int chrtoint(char a)
{
int i;
for (i = 48; i<=57; i++)
if (toascii(i)==a) return i-48;
}
char str[MAX];
int i;
scanf("%s", &str); /* We read the number */
N[0] = strlen(str); /* Find out how many digits our number has */
for (i = strlen(str)-1; i>=0; i--)
N[N[0]-i] = chrtoint(str[i]); /* Converting the number */
}
Printing a big number
---------------------
We store the number backwards, so we must print it backwards. You know
what I mean! :)
#include <stdio.h>
...
void printbignumber(BigNumber N)
{
int i;
if (N[0] == 0)
printf("0");
else
for (i = N[0]; i>=1; i--)
printf("%d", N[i]);
printf("\n");
}
Initializing a big number
-------------------------
We can -initialize- a big number in three ways. A big number can have the
value 0, can have the value of a number (int, float etc. - we will discuss
only the initialization with an integer bigger that zero) or can have the value
of an another big number.
-[ Initialization with 0 ]-
void Attrib0(BigNumber N)
{
/*
If a big number has 0 digits, then it's clear that the number
is 0, so...
*/
N[0] = 0;
}
-[ Initialization with a real number ]-
void AttribValue(BigNumber N, unsigned long X)
{
N[0] = 0; //For now we have 0 digits
while (X != 0)
{
/*
The next line is similar with:
N[0]++;
N[N[0]] = X % 10;
What is this? If the number is 192 then
192 % 10 = 2
*/
N[++N[0]] = X % 10;
/*
192 / 10 = 19 We cut the digit that we've used
*/
X /= 10;
}
}
Example:
We have 1932
Big Number
Step 0: [0 0 0 0 0]
Step 1: 1932 % 10 = 2 [1 2 0 0 0] 1932 / 10 = 193
Step 2: 193 % 10 = 3 [2 2 3 0 0] 193 / 10 = 19
Step 3: 19 % 10 = 9 [3 2 3 9 0] 19 / 10 = 1
Step 4: 1 % 10 = 1 [4 2 3 9 1] 1 / 10 = 0
-[ Initialization with a big number ]-
void AttribBigNumber(BigNumber N, BigNumber X)
{
int i;
for (i = 0; i <= X[0]; i++) N[i] = X[i]; //We copy X to N
}
How to compare two big numbers?
-------------------------------
We will use the next algorithm to compare two big numbers:
Step 1: We compare the number of digits
if the first number has more digits than the second one then
it's obvious that the first number is bigger. Otherwise if the
second number has more digits than the first one then the
second number is bigger. If the number of digits of the first
number it's equal with the number of digits of the second number
then we go to step 2.
Step 2: Here we compare the digits of the two big numbers. :
Example: if we compare 132 and 142 :
We compare 1 and 1 (the most important digits): 1 = 1
so we compare 3 and 4.
We stop here because we found two digits that aren't
equal. Now we can say what number is bigger.
We compare first the most semnificative digits.
If we can't find a bigger number, it means that the two numbers
are equal.
/*
-1 if N < X
/
compare returns - 0 if N = X
\
1 if N > X
*/
int compare(BigNumber N, BigNumber X)
{
int i;
/*
The numbers may include insignificant zeros so we must cut these down
*/
while (N[N[0]] == 0) N[0]--;
while (X[X[0]] == 0) X[0]--;
if (N[0]<X[0]) return -1; /* if X has more digits than N then it is bigger
than N */
else
if (N[0]>X[0]) return 1; /* if N has more digits than X then it is bigger
than X*/
else
{
/* We compare the digits of the two big numbers */
for (i = X[0]; i >= 1; i--)
if (X[i]>N[i]) return -1;
else if (X[i]<N[i]) return 1;
return 0;
}
}
How to add big numbers
----------------------
We know how to do simple stuff with big numbers (reading, initializing,
comparing and printing) but now we will see how we gonna do math operations with
these numbers.
In school if we want to add two numbers, for example 19324 and 1234, we
follow some simple steps:
1
19324+
1234
-----
20558
Step 1: 4 + 4 = 8
Step 2: 2 + 3 = 5
Step 3: 3 + 2 = 5
Step 4: 9 + 1 = 0 and we keep 1 in "mind"
Step 5: 1 + 0 + 1 (from the previous operation) = 2
Now we know that 19324 + 1234 = 20558
We will implement this simple algorithm that we've learned in school in our
program.
void AddBigNumbers(BigNumber N, BigNumber X, BigNumber result)
{
/*
Line 1 can be written in this way too:
int a;
if (N[0]>X[0])
a = N[0];
else
a = X[0];
*/
int a = N[0] > X[0] ? N[0] : X[0]; /* Line 1 */
int i, R = 0;
for (i = 1; i<=a; i++)
{
result[i] = N[i] + X[i] + R; /* Adding digit i of the first number with
digit i from the second number and the
surplus from the previous operation*/
if (result[i]>9) R = 1; /* We keep the surplus in mind :)*/
result[i] %= 10; /* we keep only the last digit of the sum(N[i],X[i],R)*/
}
result[0] = a;
if (R != 0) result[++result[0]] = R;
}
How to substract big numbers
----------------------------
When we added two big numbers we had a problem with the surplus. Here we
have a problem when we want to substract a bigger digit from a smaller digit.
How do we solve this little problem at school? Let's see:
Example:
#1
If we have to do 123 - 19 we follow these steps:
We write these numbers in 10 base:
123(10) = 1*100 + 2*10 + 3 - (10) means 10 base
19(10) = 1*10 + 9
Step 1: 3 is smaller than 9 so we take 10 from 20 (2*10) and do
10+3 - 9 = 4
Step 2: 1 - 1 (it's useless to say 1*10 - 1*10) = 0
Step 3: 1 - 0 = 1
Result: 104
#2
If we have 10003 - 999 we do:
Step1: 3 is smaller than 9 so we must take 10, but the next 3 digits
are 0 so we take 10 from 10000 (because 1(10) = 1*10000) and we will
remain with 9990.
13 - 9 = 4
After this step we have 9994 - 990
Step2: 9 - 9 = 0
Step3: 9 - 9 = 0
Step4: 9 - 0 = 9
Result: 10003 - 999 = 9004
We only substract pozitive integers and our result must be positive, so we must
assure that the number from wich we substract is bigger that the number we want
to substract.
Now we have to implement this algorithm in C.
void SubBigNumbers(BigNumber N, BigNumber X, BigNumber result)
{
void Sub(BigNumber N, BigNumber X)
{
/* We assume that N is bigger than X */
int i, j;
for (i=1; i<=X[0]; i++) /* We substract the numbers digit by digit */
if (X[i]>N[i]) /* If the digit from wich we substract is bigger than the
digit we want to substract.
*/
{
j = i;
while (N[++j] == 0); /* We must find a digit bigger than 0 to take
what we need for substracting */
N[j]--; j--; /* We decrement the digit from wich we borrowed the number
that we needed */
while (j>i)
{
N[j] = 9; /* We restore the rest of the digits
if we have 20004 - 899
in order to substract 9 from 4 we need 10 so we must
substract 10 from 20000 so after we do 20000-10 = 19990
After this operation we will remain with 19990 + (14 - 9)
= 19995. I hope you get the ideea.
So we must do 2 -= 1 and all the 0 must become 9.
That's all.
*/
j--;
}
N[i] += 10; /* Now we actually substract those digits */
N[i] -= X[i]; /* */
}
else
{
N[i] -= X[i]; /* Here we have no problem */
}
while ((N[N[0]] == 0) && (N[0]>0)) N[0]--; /* We must find out how many
digits our number has */
}
int a = compare(N, X); /* We compare the numbers */
if ((a == 1) || (a == 0)) /* If N >= X */
{
AttribBigNumber(result, N);
Sub(result, X);
}
else /* if N < X */
{
AttribBigNumber(result, X);
Sub(result, N);
}
}
At the end of part I
--------------------
I would like to say that english is not my native language. I know that this
document may contain many mistakes. I'm sorry for that!
I know that I don't explain everything in detail, but that is because I'm
not so sure about my english. So if you don't understand the words, maybe you
will understand the source code :).
I must say that I've learned all this from Catalin Francu's book - "The
psihology of the informatics contests". It's a great book and it's a pity that
this book isn't translated in english.
Source code--->-----------------------
#include <stdio.h>
#include <string.h>
#define MAX 300
typedef int BigNumber[MAX];
BigNumber N, C, S;
void Attrib0(BigNumber N)
{
N[0] = 0;
}
void AttribValue(BigNumber N, unsigned long value)
{
N[0] = 0;
while (value != 0)
{
N[++N[0]] = value % 10;
value /= 10;
}
}
void AttribBigNumber(BigNumber N, BigNumber X)
{
int i;
for (i = 0; i <= X[0]; i++) N[i] = X[i];
}
/* -1 if N < X
/
compare returns - 0 if N = X
\
1 if N > X
*/
int compare(BigNumber N, BigNumber X)
{
int i;
/*
The numbers may include insignificant zeros so we must cut these down
*/
while (N[N[0]] == 0) N[0]--;
while (X[X[0]] == 0) X[0]--;
if (N[0]<X[0]) return -1; /* if X has more digits than N then it is bigger
than N */
else
if (N[0]>X[0]) return 1;
else
{
for (i = X[0]; i >= 1; i--)
if (X[i]>N[i]) return -1;
else if (X[i]<N[i]) return 1;
return 0;
}
}
void readbignumber(BigNumber N)
{
int chrtoint(char a)
{
int i;
for (i = 48; i<=57; i++)
if (toascii(i)==a) return i-48;
}
char str[MAX];
int i;
scanf("%s", &str);
N[0] = strlen(str);
for (i = strlen(str)-1; i>=0; i--)
N[N[0]-i] = chrtoint(str[i]);
}
void printbignumber(BigNumber N)
{
int i;
if (N[0] == 0)
printf("0");
else
for (i = N[0]; i>=1; i--)
printf("%d", N[i]);
printf("\n");
}
void AddBigNumbers(BigNumber N, BigNumber X, BigNumber result)
{
int a = N[0] > X[0] ? N[0] : X[0];
int i, R = 0;
for (i = 1; i<=a; i++)
{
result[i] = N[i] + X[i] + R;
if (result[i]>9) R = 1; /* We keep the surplus in mind :)*/
result[i] %= 10; /* if the number is bigger than 10 we keep only the
last digit */
}
result[0] = a;
if (R != 0) result[++result[0]] = R;
}
void SubBigNumbers(BigNumber N, BigNumber X, BigNumber result)
{
void Sub(BigNumber N, BigNumber X)
{
/* We assume that N is bigger than X */
int i, j;
for (i=1; i<=X[0]; i++) /* We substract the numbers digit by digit */
if (X[i]>N[i])
{
j = i;
while (N[++j] == 0);
N[j]--; j--;
while (j>i)
{
N[j] = 9;
j--;
}
N[i] += 10;
N[i] -= X[i];
}
else
{
N[i] -= X[i];
}
while ((N[N[0]] == 0) && (N[0]>0)) N[0]--;
}
int a = compare(N, X);
if ((a == 1) || (a == 0))
{
AttribBigNumber(result, N);
Sub(result, X);
}
else
{
AttribBigNumber(result, X);
Sub(result, N);
}
}
int main(void)
{
int i;
printf("Input a big number (A): ");
readbignumber(N);
printf("Input a big number (B): ");
readbignumber(C);
AddBigNumbers(N,C,S);
printf("\nA+B = ");
printbignumber(S);
SubBigNumbers(N,C,S);
printf("\nA-B = ");
printbignumber(S);
return 0;
}
---------------------------------
Do you Yahoo!?
Yahoo! Mail Plus - Powerful. Affordable. Sign up now-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://linuxchix.org/pipermail/courses/attachments/20021126/93bab828/attachment.xhtml
More information about the Courses
mailing list