Lab46 Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
======Project: BIG NUM======

A project for COURSENAME by YOUR NAME during the SEMESTER YEAR.

This project was begun on DATE and is anticipated to take TIME UNIT to complete. Project was completed on MONTH DAY, YEAR.

=====Objectives=====
State the purpose of this project. What is the point of this project? What do we hope to accomplish by undertaking it?

=====Prerequisites=====
In order to successfully accomplish/perform this project, the listed resources/experiences need to be consulted/achieved:

  * successful completion of project #1 and solid understanding of pertinent topics
  * familiarity with memory allocation via **malloc(3)**
  * familiarity with memory, accessing data via pointer dereferencing, and address calculation
  * familiarity with looking up C function parameters/information in the manual
  * familiarity with functions, their parameters and return types

=====Background=====
State the idea or purpose of the project. What are you attempting to pursue?

Upon approval, you'll want to fill this section out with more detailed background information. DO NOT JUST PROVIDE A LINK.

Providing any links to original source material, such as from a project page, is a good idea.

You'll want to give a general overview of what is going to be accomplished (for example, if your project is about installing a web server, do a little write-up on web servers. What is it, why do we need one, how does it work, etc.)

=====Scope=====
This project will have you implementing code to support the storage and manipulation of numbers outside of the established data types.

In C, from our first project (Project #0), we explored the various established data types, and determined their various sizes and representational ranges.

From that, we should know the largest value we can store in a variable using the biggest data type size (**unsigned long long int**), which is: **18,446,744,073,709,551,615**

That's a 20-digit number.

But this project will have us creating the ability to store and manipulate largers much larger than that. We'll start with a target of 4 and 24 digits (if you write your code effectively, the number of digits should ultimately not matter).

Why 4? Can't we already easily store values of 4 digits?

Yes, but looking to implement the ability to store and manipulate a 4 digit number will help us to better realize the logic and code necessary to scale our solution to support any number of digits.

While there are many approaches to this problem, follow through this example to get some insight. You don't have to take this approach, but it will cover some important concepts you will need to implement in your solution, whether or not you take this approach.

Let's look at a 4 digit number not as a side-effect of being able to be stored in a quantity of appropriate size, but as 4 literal stored digits in memory. To wit:

<code c>
    unsigned char *value;
    value = (unsigned char *) malloc (sizeof(unsigned char) * 4);
    *(value+0) = *(value+1) = *(value+2) = *(value+3) = 0;
</code>

What just happened here? Make sure you understand, or ask questions and get clarification before attempting to continue.

Essentially, we have just allocated 4 bytes of memory (of type **unsigned char**), which are located consecutively in memory. To draw a picture, we'd have this:

^  0  ^  0  ^  0  ^  0  ^
|  *(value+0)  |  *(value+1)  |  *(value+2)  |  *(value+3)  |

4 bytes of memory, each containing a single digit of our 4 digit number. Let's assume we are attacking this as a decimal (base 10) value, and we'll maintain our assumption that the left-most value is the **most significant digit**, and the right-most value is the **least significant digit**.

For example, let's say we wanted to store the 4-digit number 8192 in memory using this scheme. The code and resulting "picture" would be as follows:

<code c>
    *(value+0) = 8;
    *(value+1) = 1;
    *(value+2) = 9;
    *(value+3) = 2;
</code>

^  8  ^  1  ^  9  ^  2  ^
|  *(value+0)  |  *(value+1)  |  *(value+2)  |  *(value+3)  |

Make sense?

Be aware that *(value+0), the first memory address of our sequence, is at the left side of our value... therefore it stores the **most significant digit**. You are free to do it the other way, just make sure that whatever approach you take, you maintain your logic.

Now, what if we wanted to perform an addition?

8192+4 = 8196

Pretty easy right?

4 in our memory scheme would be represented as "0004", and we'd accomplish the addition as follows:

<code c>
    *(value+0) = *(value+0) + 0;
    *(value+1) = *(value+1) + 0;
    *(value+2) = *(value+2) + 0;
    *(value+3) = *(value+3) + 4;
</code>

As you can see, the value of "4" was added only to the last (**least significant**) digit stored in our value. Displaying it should should the expected answer:

^  8  ^  1  ^  9  ^  6  ^
|  *(value+0)  |  *(value+1)  |  *(value+2)  |  *(value+3)  |

There's actually two situations that occur with adding... what we just saw was the straight "sum". In this case, the sum was the only meaningful result generated.

But there's also another situation we can have, and that is a carry. A carry is when the result is too big to be stored in a single digit (ie a 2 digit number). So we react by storing the least significant digit and **carry**ing the most significant digit to the next placevalue.

Let's take our 8196 and add 1024 to it. What do we get? **9220**

Illustrated, we have:

^Carry:  |  0  |  1  |  1  |  0  |
^Value:  |  8  |  1  |  9  |  6  |
^Addend:  |  1  |  0  |  2  |  4  |
^Sum:  ^  9  ^  2  ^  2  ^  0  ^
|  ^  *(value+0)  ^  *(value+1)  ^  *(value+2)  ^  *(value+3)  ^

So, for this project I'd like for you to write a set of functions and a test program that:

  * have a function that will allocate space to store a value of desired length (at least 4 and 24, but feel free to test it with larger numbers: 32, 40, 64, etc.) and return the address (so we can assign it to one of our pointers).
  * have a function that will **zero** your value, running through each position and setting it to 0.
  * have a function that will accept as a parameter the original number and number to **add**, perform the operation, and place the result in the original number
  * implement a function to tackle **subtraction** being mindful of the carry
  * implement a function to perform **multiplication**
  * implement a function to perform **division**
  * implement a function that accepts as two arguments two of our dynamically allocated "numbers", compares them, and returns a -1 if the left parameter is greater, 0 if they are equal, and 1 if the right parameter is greater.
  * implement a sample program that:
    * prompts the user to enter a the number length (4 digits, 24 digits, 32 digits, etc.)
    * prompts the user for actual values (you'll have to rig up a way to convert the user's input into the appropriate values to place in your managed data type
    * gives the user a choice (perhaps via a menu) that lets them select from all the available functions (even resetting and starting over with new digit-lengths).

=====Code=====

The code:

<code c>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
void printary( int, char* );
char* mkArray( int );
char* mkZero( int, char* );
char* Addition( int, char*, char* );
char* Subtraction( int, char*, char* );
char* Multiplication( int, char*, char* );
int Division( int, char*, char* );
int compare( char*, int );

int main()
{
        char *array1, *array2, *result, menuchoice;
        int size, size1, size2, i, intResult;

        fprintf(stdout, "How many digits is the first number (preferably the larger): ");
        fscanf(stdin, "%u", &size1);
        fprintf(stdout, "\nHow many digits is the second number: ");
        fscanf(stdin, "%u", &size2);

        if( size1 > size2 )
                size = size1;
        else
                size = size2;

        size = size + 1;

// Creating the arrays

        array1 = mkArray( size );
        array2 = mkArray( size );
        result = mkArray( size );

// Making the array values zero

        array1 = mkZero( size, array1 );
        array2 = mkZero( size, array2 );
        result = mkZero( size, result );

        fprintf(stdout, "Next, the program will ask you to input the numbers that you want to be stored.\n");
        fprintf(stdout, "You MUST add one zero to the beginning of the first number, or else the program will not run correctly.\n");
        fprintf(stdout, "Also, for the second number, add in enough zeros to the beginning so that the length matches that of the first number.\n\n");
        fprintf(stdout, "Please enter the number that you want to be stored: ");

        fgetc(stdin);

        for(i = 0; i <= size; i++)
        {
                *(array1 + i) = fgetc(stdin) - 48;
        }
        printary( size, array1 );

        fprintf(stdout, "\n\n");

// Next, I created a prompt to have the user input the next number.

        fprintf(stdout, "Please enter the number that you want to be stored: ");


        for(i = 0; i < size; i++)
        {
                *(array2 + i) = fgetc(stdin) - 48;
        }
        printary( size, array2 );


        fprintf(stdout, "\n\n");

// Beginning the switch block allowing the user to choose what he/she wants to do with the numbers

        fprintf(stdout, "What would you like to do with these numbers? ");
        printf("Choose:\n 1. Addition\n 2. Subtraction\n 3. Multiplication\n 4. Divison\n 5. Quit\nEnter now: ");

        fgetc(stdin);
        menuchoice = fgetc(stdin);
        switch( menuchoice )
        {
                case'1':
                        fprintf(stdout, "You have chosen Addition.\n");
                        result = Addition( size, array1, array2 );
                        fprintf(stdout, "The result is: ");
                        printary( size, result );
                        fprintf(stdout, "\n");
                        break;
                case'2':
                        fprintf(stdout, "You have chosen Subtraction.\n");
                        result = Subtraction( size, array1, array2 );
                        fprintf(stdout, "The result is: ");
                        printary( size, result );
                        fprintf(stdout, "\n");
                        break;
                case'3':
                        fprintf(stdout, "You have chosen Multiplication.\n");
                        result = Multiplication( size, array1, array2 );
                        fprintf(stdout, "The result is: ");
                        printary( size + size, result );
                        fprintf(stdout, "\n");
                        break;

                case'4':
                        fprintf(stdout, "You have chosen Division.\n");
                        intResult = Division( size, array1, array2 );
                        fprintf(stdout, "The result is: %d\n", intResult );
                        break;
                case'5':
                        fprintf(stdout, "Have a great day!\n");
                        break;
                default:
                        fprintf(stdout, "You haven't chosen a correct option.\n");
                        break;
        }
        return(0);
}

void printary( int size, char *array )
{
        char count;
        for( count = 0; count < size; count++ )
        {
                printf("%hhu", *(array + count));
        }
        printf("\n");
}

char * mkArray( int size )
{
        char *array;
        array = (char *) malloc (sizeof(char) * size);
        return array;
}

char * mkZero( int size, char *array )
{
        char count;
        for( count = 0; count <= size; count++ )
        {
                *( array + count ) = 0;
        }
        return array;
}

char * Addition( int size, char *array1, char *array2 )
{
        int count;

        int answer = 0;
        char *addition, *carry;

// Allocating memory for the return array and the carry array

        addition = mkArray( size );
        carry = mkArray( size );

// Setting the array elements equal to zero

        mkZero( size, addition );
        mkZero( size, carry );

// For loop to perform the addition

        for( count = size; count >= 0; count-- )
        {
                answer = (*(array1 + count) + *(array2 + count) + *(carry + count));
                if(answer > 9)
                {
                        answer = answer - 10;
                        *(carry + (count - 1)) = 1;
                }
                *(addition + count) = answer;
        }
        return addition;
}

char * Subtraction( int size, char *array1, char *array2 )
{
        int count;
        int answer = 0;
        char *subtraction, *carry;

// Allocating memory for the arrays

        subtraction = mkArray( size );
        carry = mkArray( size );

// Making the values of the elements of each array zero

        mkZero( size, subtraction );
        mkZero( size, carry );

// For loop to perform subtraction

        for( count = (size - 1); count >= 0; count-- )
        {
                answer = (*(array1 + count) - *(array2 + count) - *(carry + count));
                if( answer < 0 )
                {
                        answer = answer + 10;
                        *(carry + (count - 1)) = 1;
                }
                *(subtraction + count) = answer;
        }
        return subtraction;
}

char * Multiplication( int size, char *array1, char *array2 )
{
        char *multiplication, *one, *holder, *appended1, *appended2;

// Creating a new size variable to account for the larger numbered results, as well as an offset to allow
// the program to print out the result correctly

        int size2, offset;
        offset = sizeof(char) * size ;
        size2 = size + size;

// Allocating the memory for the new appended arrays

        appended1 = mkArray( size2 );
        appended2 = mkArray( size2 );


// Setting each element equal to zero

        mkZero( size2, appended1 );
        mkZero( size2, appended2 );

// Copying the memory of the arrays into the new appended arrays, and including the offset
// to make sure that the values are at the end of the memory, instead of in the middle

        memcpy( appended1 + offset, array1, offset );
        memcpy( appended2 + offset, array2, offset );

// Allocating memory in the multiplication array and setting the elements equal to zero

        multiplication = mkArray( size2 );
        multiplication = mkZero( size2, multiplication );

// The same thing as the multiplication array, except this array only holds the number one
// to decrement the second array

        one = mkArray( size2 );
        one = mkZero( size2, one );
        *( one + ( size2 - 1 ) ) = 1;


// A holder array to keep the results in check

        holder = mkArray( size2 );
        mkZero( size2, holder );

        int x;

// The while loop has the second appended array check with the number zero, and if all numbers are zero in the array, then the compare
// function returns a 1, which then quits

        while( compare( appended2, size2 ) == 0 )
        {
                x = compare( appended2, size2 );
                holder = Addition( size2, holder, appended1 );
                appended2 = Subtraction( size2, appended2, one );
        }
        multiplication = holder;
        return multiplication;
}


int Division( int size, char *array1, char *array2 )
{
        int count = 0;
        int result = 0;

        int x;
        x = compare( array1, size );

        while( compare( array1, size ) == 0 )
        {
                x = compare( array1, size );
                result++;
                array1 = Subtraction( size, array1, array2 );
        }
        return result;
}

int compare( char *array2, int size )
{
        int count;
        for( count = 0; count < size; count++ )
        {
                if( array2[count] != 0 && array2[count] != '0' )
                {
                        return 0;
                }
        }
        return 1;
}

</code>

=====Execution=====

This should cover all of the program execution:

<cli>
lab46:~/src/cprog/Projects/project2$ gcc -o bignum3 bignum3.c
lab46:~/src/cprog/Projects/project2$ ./bignum3
How many digits is the first number (preferably the larger): 24

How many digits is the second number: 18
Next, the program will ask you to input the numbers that you want to be stored.
You MUST add one zero to the beginning of the first number, or else the program will not run correctly.
Also, for the second number, add in enough zeros to the beginning so that the length matches that of the first number.

Please enter the number that you want to be stored: 0983471234567898757634287
0983471234567898757634287


Please enter the number that you want to be stored: 0000000128765439871345634
0000000128765439871345634


What would you like to do with these numbers? Choose:
 1. Addition
 2. Subtraction
 3. Multiplication
 4. Divison
 5. Quit
Enter now: 1
You have chosen Addition.
The result is: 0983471363333338628979921

lab46:~/src/cprog/Projects/project2$ ./bignum3
How many digits is the first number (preferably the larger): 12

How many digits is the second number: 10
Next, the program will ask you to input the numbers that you want to be stored.
You MUST add one zero to the beginning of the first number, or else the program will not run correctly.
Also, for the second number, add in enough zeros to the beginning so that the length matches that of the first number.

Please enter the number that you want to be stored: 0999933482716
0999933482716


Please enter the number that you want to be stored: 0009389287642
0009389287642


What would you like to do with these numbers? Choose:
 1. Addition
 2. Subtraction
 3. Multiplication
 4. Divison
 5. Quit
Enter now: 2
You have chosen Subtraction.
The result is: 0990544195074

lab46:~/src/cprog/Projects/project2$ ./bignum3
How many digits is the first number (preferably the larger): 3

How many digits is the second number: 3
Next, the program will ask you to input the numbers that you want to be stored.
You MUST add one zero to the beginning of the first number, or else the program will not run correctly.
Also, for the second number, add in enough zeros to the beginning so that the length matches that of the first number.

Please enter the number that you want to be stored: 0999
0999


Please enter the number that you want to be stored: 0999
0999


What would you like to do with these numbers? Choose:
 1. Addition
 2. Subtraction
 3. Multiplication
 4. Divison
 5. Quit
Enter now: 3
You have chosen Multiplication.
The result is: 00998001

lab46:~/src/cprog/Projects/project2$ ./bignum3
How many digits is the first number (preferably the larger): 6

How many digits is the second number: 2
Next, the program will ask you to input the numbers that you want to be stored.
You MUST add one zero to the beginning of the first number, or else the program will not run correctly.
Also, for the second number, add in enough zeros to the beginning so that the length matches that of the first number.

Please enter the number that you want to be stored: 0390625
0390625


Please enter the number that you want to be stored: 0000025
0000025


What would you like to do with these numbers? Choose:
 1. Addition
 2. Subtraction
 3. Multiplication
 4. Divison
 5. Quit
Enter now: 4
You have chosen Division.
The result is: 15625
lab46:~/src/cprog/Projects/project2$ ./bignum3
How many digits is the first number (preferably the larger): 1

How many digits is the second number: 1
Next, the program will ask you to input the numbers that you want to be stored.
You MUST add one zero to the beginning of the first number, or else the program will not run correctly.
Also, for the second number, add in enough zeros to the beginning so that the length matches that of the first number.

Please enter the number that you want to be stored: 01
01


Please enter the number that you want to be stored: 01
01


What would you like to do with these numbers? Choose:
 1. Addition
 2. Subtraction
 3. Multiplication
 4. Divison
 5. Quit
Enter now: 5
Have a great day!
lab46:~/src/cprog/Projects/project2$ ./bignum3
How many digits is the first number (preferably the larger): 5

How many digits is the second number: 2
Next, the program will ask you to input the numbers that you want to be stored.
You MUST add one zero to the beginning of the first number, or else the program will not run correctly.
Also, for the second number, add in enough zeros to the beginning so that the length matches that of the first number.

Please enter the number that you want to be stored: 023456
023456


Please enter the number that you want to be stored: 000012
000012


What would you like to do with these numbers? Choose:
 1. Addition
 2. Subtraction
 3. Multiplication
 4. Divison
 5. Quit
Enter now: 87
You haven't chosen a correct option.
lab46:~/src/cprog/Projects/project2$ 

</cli>

=====Reflection=====
The project was stressful, but fun to do. It taught me how to properly create separate functions and call them effectively. Also, it showed me how to use functions that store values as pointers, and how to pass those arrays back and forth.

=====References=====
In performing this project, the following resources were referenced:

  * http://cslibrary.stanford.edu/106/
  * The books used in the course.
Lab46 Wiki

User Tools

Site Tools

Page Tools
