Code:
// Wes Kendrick
// BIGINT.C
// THIS PROGRAMS ALLOWS FOR SIMPLE MANIPULATION OF LARGE INTEGERS.
// THE USER CAN ADD, OR SUBTRACT TWO LARGE INTEGERS INPUT FROM THE KEYBOARD
// THIS PROGRAM DOES NOT ALLOW FOR A NEGATIVE RESULT. THE SMALLER NUMBER WILL
// ALWAYS BE SUBTRACTED FROM THE LARGER NUMBER WHEN SUBTRACTION IS THE OPERATION
// DESIRED
// This program was written in Dev-C++ 4.9.9.2, and is written strictly for use
// on a PC. Not all functions used are assumed to be ANSI C
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define ADD 1
#define SUBTRACT 2
#define QUIT 3
#define MAX 200
//Preconditions: the first parameter is string that stores
// only contains digits, doesn't start with
// 0, and is 200 or fewer characters long.
//Postconditions: The function will read the digits of the
// large integer character by character,
// convert them into integers and place them in
// nodes of a linked list. The pointer to the
// head of the list is returned.
struct integer* read_integer();
//Preconditions: p is a pointer to a big integer, stored in
// reverse order, least to most significant
// digit, with no leading zeros.
//Postconditions: The big integer pointed to by p is
// printed out.
void print_bigint(struct integer *p);
//Preconditions: p and q are pointers to big integers,
// stored in reverse order, least to most
// significant digit, with no leading zeros.
//Postconditions: A new big integer is created that stores
// the sum of the integers pointed to by p
// and q and a pointer to it is returned.
struct integer* add(struct integer *p, struct integer *q);
//Preconditions: p and q are pointers to big integers,
// stored in reverse order, least to most
// significant digit, with no leading zeros.
//Postconditions: A new big integer is created that stores
// the absolute value of the difference
// between the two and a pointer to this is
// returned.
struct integer* subtract(struct integer *p, struct integer *q);
//Preconditions: Both parameters of the function are
// pointers to struct integer.
//Postconditions: The function compares the digits of two
// numbers recursively and returns:
// -1 if the first number is smaller than the second,
// 0 if the first number is equal to the second number,
// 1 if the first number is greater than the second.
int compare(struct integer *p, struct integer *q);
//Preconditions: Both parameters point to struct integer
//Postconditions: Prints spaces so that the numbers are
// aligned to the right
//Preconditions: p, q, and answer point to struct integer, operation is
// the operation to be performed
//Postconditions: Formats the output
void format_output(struct integer *p, struct integer *q, struct integer *answer, int operation);
//Preconditions: choice, low, and high are all int...low is low bound of
// acceptable input, high is high bound
//Postconditions: Returns TRUE if input is valid, otherwise returns FALSE
int valid_choice(int choice, int low, int high);
//Preconditions: None
//Postconditions: Retrieves the user choice from the keyboard and returns it
int get_user_choice();
//Preconditions: how_many is an int, character is a char
//Postconditions: prints out character how_many times
void print_characters(int how_many, char character);
//Preconditions: answer is of type struct integer, it has at least one
// leading zero (because method of complements is used for
// subtraction.)
//Postconditions: All leading zeroes are removed, and the size
// of answer is adjusted accordingly
void remove_zeroes(struct integer *answer);
struct integer
{
int *digits;
int size;
};
int main()
{
int choice, operation;
struct integer *bigint1,*bigint2,*answer;
// Run until user chooses to quit
do
{
choice=get_user_choice();
if(choice !=QUIT)
{
system("CLS");
printf("Please enter the first number: ");
bigint1=read_integer();
printf("\nPlease enter the second number: ");
bigint2=read_integer();
// Executes users choice
switch(choice)
{
case ADD:
answer = add(bigint1,bigint2);
operation=ADD;
break;
case SUBTRACT:
answer = subtract(bigint1,bigint2);
operation=SUBTRACT;
break;
} // End switch
format_output(bigint1,bigint2,answer,operation);
system("PAUSE");
// Frees memory
free(bigint1);
free(bigint2);
free(answer);
}
}
while(choice!=QUIT);
// End program
printf("\n\nThank you for using the Big Int calculator!\n\n\n");
system("PAUSE");
return 0;
}
int get_user_choice()
{
int choice;
system("CLS");
do
{
printf("1. Add two large integers\n2. Subtract two large integers\n3. Quit\n");
printf("\n\nEnter the number corresponding to your choice: ");
scanf("%d",&choice);
}
// Checks for valid input in the while loop
while(valid_choice(choice,1,3)==FALSE);
return choice;
}
int valid_choice(int choice, int low, int high)
{
// Checks entry against bounds
if(choice<low || choice > high)
{
printf("\n\nThat is invalid input.\n\n\n");
return FALSE;
}
else
return TRUE;
}
struct integer* read_integer()
{
// Temporary string is created to read in the number from the user
char string_num[MAX];
// Allocates memory for the struct integer, the address of this will be returned
struct integer *temp= (struct integer *)malloc(sizeof(struct integer));
int counter;
// Reads string
scanf("%s",string_num);
// Sets the size of the "integer"
temp->size=strlen(string_num);
// Dynamically allocates memory for the array of int
temp->digits=(int *)(malloc((temp->size*sizeof(int))));
// Subtracts '0' from the character to get the digit...numbers are stored
// with the least signifigant digit in index 0...this makes the code
// slightly simpler
for(counter=temp->size-1;counter>=0;counter--)
temp->digits[temp->size-1-counter]=string_num[counter]-'0';
return temp;
}
struct integer* add(struct integer *p, struct integer *q)
{
// Allocates integer
struct integer *answer=malloc(sizeof(struct integer));
int counter, carry=0;
// If p is bigger than q, size the array in answer to the size of p
if(compare(p,q)==1)
{
answer->size=p->size;
// To simplify the code, we reallocate memory to the smaller number and set its
// size to the size of the bigger one (if they are the same number of digits, nothing
// happens
q->digits=realloc(q->digits,p->size*sizeof(int));
for(counter=q->size; counter < p-> size; counter++)
{
q->digits[counter]=0;
}
}
// Q is bigger, repeat process as above, but switch p and q
else
{
answer->size=q->size;
if(q->size != p->size)
{
p->digits=realloc(p->digits,q->size*sizeof(int));
for(counter=p->size;counter< q->size;counter++)
p->digits[counter]=0;
}
}
// Allocates enough memory for the array of int inside answer
answer->digits=(int *) malloc(answer->size*sizeof(int));
// Runs counter for entire length of answer
for(counter=0;counter< (answer->size);counter++)
{
// Sets answer->digits[counter] to the sum of the digit in the same index position
// of q and p, as well as "carry" which is initialized to zero
answer->digits[counter]=p->digits[counter]+q->digits[counter] + carry;
// Number is greater than 9...must be reduced and reset carry
if(answer->digits[counter]>9)
{
answer->digits[counter]%=10;
carry=1;
}
else
// Carry is zero, answer->digits[counter] is less than 10
carry=0;
}
// End of the for-loop, if carry is still 1, reallocate the size of answer->digits
// to answer->size+1, and increment answer->size
if(carry==1)
{
// turns digit from > 10
answer->size++;
answer->digits=realloc(answer->digits,answer->size*sizeof(int));
// Will never be greater than one...(worst case example: 999+999 = 1998 (4 digits, leading 1)
answer->digits[(answer->size-1)]=1;
}
// Reallocate p and q to their original sizes, only the added zeroes will be removed
p->digits=realloc(p->digits,p->size*sizeof(int));
q->digits=realloc(q->digits,q->size*sizeof(int));
// address of answre is returned
return answer;
}
struct integer* subtract(struct integer *p, struct integer *q)
{
// COMPLEMENTS stores the nines complement of a digit 0-9
int COMPLEMENTS[10], counter, difference;//, not_a_leading_zero, how_big_answer;
// Required for complement method of subtraction, to add one to the result
// This segment sets the attributes of one
struct integer *one= (struct integer *)(malloc(sizeof(struct integer)));
one->size=1;
one->digits=(int *)(malloc(one->size*sizeof(int)));
one->digits[0]=1;
// Nines complement will hold the nines complement of the smaller number
struct integer *nines_complement=(struct integer *)(malloc(sizeof(struct integer)));
struct integer *answer;
// Initializes the nines complement of digits 0-9
for(counter=0;counter<10;counter++)
{
COMPLEMENTS[counter]=9-counter;
}
// If p > q
if(compare(p,q)==1)
{
// Difference will represent the number of additional digits that must
// be added to make both numbers the same size
difference=p->size - q->size;
// sets nines_complement->size to the bigger numbers size
nines_complement->size=p->size;
// Allocates memory for the int array inside nines_complement
nines_complement->digits=(int *)(malloc(nines_complement->size*sizeof(int)));
// Sets all "unaccounted for digits" to 9...counter stops when it equals the difference in
// size between nines_complement and the smaller number
for(counter=nines_complement->size-1;counter>=(nines_complement->size-difference);counter--)
{
nines_complement->digits[counter]=9;
}
// sets the rest of the "accounted for digits" to the respective digit in the smaller of
// the two numbers (in this case q)
for(counter=nines_complement->size-difference-1;counter>=0;counter--)
{
nines_complement->digits[counter]=COMPLEMENTS[q->digits[counter]];
}
// This is the method of complements, the intermediate step answer is set to
// the sum of the larger number and the nines complement of the smaller number
answer=add(nines_complement,p);
}
// In this case, p is smaller (or equal to) q...same logic as above except the
// p's and q's have been switched
else
{
difference=q->size - p->size;
nines_complement->size=q->size;
nines_complement->digits=(int *)(malloc(nines_complement->size*sizeof(int)));
for(counter=nines_complement->size-1;counter>=(nines_complement->size-difference);counter--)
{
nines_complement->digits[counter]=9;
}
for(counter=nines_complement->size-difference-1;counter>=0;counter--)
{
nines_complement->digits[counter]=COMPLEMENTS[p->digits[counter]];
}
answer=add(nines_complement,q);
}
// Second to last step of complements method, one is added to answer
answer=add(answer,one);
// Finished with nines_complement and one
free(nines_complement);
free(one);
// We know that the size of answer has been incremented by one, and this new
// digit holds a 1...final step of this algorithm is to remove the one.
answer->digits[(answer->size-1)]=0;
// Removes leading zeroes from answer
remove_zeroes(answer);
return answer;
}
void remove_zeroes(struct integer *answer)
{
// First digit will be a zero
int not_a_leading_zero=0, counter;
// Runs until counter > 0 because if answer is 0 we want it left that way
for(counter=answer->size-1;counter>0;counter--)
{
if(answer->digits[counter]==0 && not_a_leading_zero==0)
// Size of answer is smaller
answer->size--;
else
not_a_leading_zero=1;
}
// Reallocate memory for answer, only the leading zeroes will be removed
answer->digits=realloc(answer->digits,answer->size*sizeof(int));
}
void print_bigint(struct integer *p)
{
int counter;
// Since the number is stored in reverse order, we print it out in reverse order
// to get the number as it should appear
for(counter=p->size-1;counter>=0;counter--)
{
printf("%d",p->digits[counter]);
}
}
int compare(struct integer *p, struct integer *q)
{
int counter;
// If p has more digits then it is larger
if(p->size>q->size)
return 1;
// if p has fewer digits then p is smaller
if(p->size<q->size)
return -1;
for(counter=q->size-1;counter>=0;counter--)
{
// If any digit from p is greater than the digit in the same place of q
// is larger, then p is larger
if(p->digits[counter]>q->digits[counter])
return 1;
// If any digit from q is greater than the digit in the same place of p
// then q is larger
if(q->digits[counter]>p->digits[counter])
return -1;
}
// Digits are equal
return 0;
}
void format_output(struct integer *p, struct integer *q, struct integer *answer,
int operation)
{
int counter, difference=0;
printf("\n");
switch(operation)
{
case ADD:
// If p is greater than q, then print p and print spaces equal to the
// difference in size of p and q...this is strictly aesthetic
if(compare(p,q)==1)
{
print_bigint(p);
printf("\n+\n");
print_characters(p->size-q->size,' ');
print_bigint(q);
}
else
{
// If q is larger, then we print spaces, then print p, then print q
print_characters(q->size-p->size, ' ');
print_bigint(p);
printf("\n+\n");
print_bigint(q);
}
printf("\n");
print_characters(answer->size,'-');
break;
// The specs for the program do not allow for negative numbers...this uses
// the same logic as above, only prints the larger number on top of the smaller
// number. Since the result of subtraction can have a variety of sizes, we set
// difference to the larger numbers size minus the size of the answer
case SUBTRACT:
if(compare(p,q)==1)
{
print_bigint(p);
printf("\n-\n");
print_characters(p->size-q->size,' ');
print_bigint(q);
printf("\n");
print_characters(p->size,'-');
difference=p->size-answer->size;
}
else
{
print_bigint(q);
printf("\n-\n");
print_characters(q->size-p->size, ' ');
print_bigint(p);
printf("\n");
print_characters(q->size,'-');
difference=q->size-answer->size;
}
break;
} // End Switch
printf("\n");
// Prints spaces to format the answer, this will always be zero
// in the case of addition
print_characters(difference,' ');
print_bigint(answer);
printf("\n\n");
}
void print_characters(int how_many, char character)
{
int counter;
// Prints character n times
for(counter=0;counter<how_many;counter++)
printf("%c",character);
}
