Lab46 Wiki

User Tools

Site Tools

You are here: start » user » brobbin4 » portfolio » cprogproject2
user:brobbin4:portfolio:cprogproject2

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
user:brobbin4:portfolio:cprogproject2 [2012/04/24 17:00] – [Reflection] brobbin4user:brobbin4:portfolio:cprogproject2 [2012/04/24 17:16] (current) – [Objectives] brobbin4
Line 1: Line 1:
 +======Project: BIG NUM======
  
 +A project for CSCS1320 by Brian Robbins during the Spring 2012 Semester.
 +
 +This project was begun on DATE and is anticipated to take TIME UNIT to complete. Project was completed on MONTH DAY, YEAR.
 +
 +
 +
 +=====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=====
 +The idea of this project is to create program that will perform mathmatical functions on numbers greater then 24 digits in length. This will test my knowledge C function calls and the use of multiple arrays. I will create the program so it has for computational functions which are addition, subtraction, multiplication, and division.
 +
 +
 +=====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 bignum code:
 +
 +<code c>
 +/*
 + * bignum.c - program that performs basic computations
 + *
 + *
 + * Compile with: gcc -o bignum bignum.c
 + *
 + * Execute with: ./bignum
 + *
 + */
 + 
 +#include <stdio.h>
 +#include <stdlib.h>
 +#include <math.h>
 +
 +void add(char* , char*, char);
 +void subtract(char*, char*, char);
 +void multiply(char*, char*, char*, char*, char);
 +void divide(char*, char*, char*, char*, char);
 +char compare(char*, char*, char);
 +
 +int main()
 +{
 +        char* num1;
 +        char* num2;
 +        char* num3;
 +        char* num4;
 +        char a=0, y=0;
 +        int z, x;
 +
 +        printf("\n");
 +
 +        do
 +        {
 +
 +        printf("\nWhat would you like to do: ");
 +        printf("\nEnter '1' for addition. ");
 +        printf("\nEnter '2' for substraction. ");
 +        printf("\nEnter '3' for multiplication. ");
 +        printf("\nEnter '4' for division. ");
 +        printf("\nEnter '6' to quit. ");
 +        printf("\n");
 +        printf("\nPlease enter an option: ");
 +        scanf("%d", &x);
 +        if( x == 6 )
 +        {
 +                printf("\n");
 +                return(0);
 +        }
 +
 +        printf("\nPlease enter the number of digits of your largest number: ");
 +        fscanf(stdin, "%hhd", &a);
 +
 +        num1 = (char*) malloc(sizeof(char) * a);
 +        num2 = (char*) malloc(sizeof(char) * a);
 +        num3 = (char*) malloc(sizeof(char) * a);
 +        num4 = (char*) malloc(sizeof(char) * a);
 +
 +        for(z=0; z<a; z++)
 +        {
 +                *(num1+z)=0;
 +                *(num2+z)=0;
 +                *(num3+z)=0;
 +                *(num4+z)=0;
 +        }
 +
 +        *(num3+a-1)=1;
 +
 +        fgetc(stdin);
 +
 +        y=0;
 +
 +        printf("\n");
 +
 +        printf("Please enter your first number.");
 +        printf("\nNote, If this number is the smaller of the two numbers be sure to pad the number with zeros): ");
 +        z=fgetc(stdin);
 +        while (z !='\n')
 +        {
 +                *(num1+y)=z -48;
 +                y++;
 +                z = fgetc(stdin);
 +        }
 +
 +        y=0;
 +
 +        printf("\nPlease enter your second number.");
 +        printf("\nNote, if this number is the smaller of the two numbers be sure to pad the number with zeros): ");
 +        z=fgetc(stdin);
 +        while (z !='\n')
 +        {
 +                *(num2+y)=z -48;
 +                y++;
 +                z = fgetc(stdin);
 +        }
 +
 +        y=0;
 +
 +        z=0;
 +
 +                switch(x)
 +                {
 +                        case 1:
 +                                        add(num1, num2, a);
 +
 +                                        y=0;
 +
 +                                        printf("\nThe sum of the two numbers is: ");
 +                                        for(y=0; y<a; y++)
 +                                        {
 +                                                printf("%hhd", *(num1+y));
 +                                        }
 +                                        printf("\n");
 +                                        break;
 +
 +                        case 2:
 +                                        subtract(num1, num2, a);
 +
 +                                        y=0;
 +
 +                                        printf("\nThe remainder of the two numbers is: ");
 +                                        for(y=0; y<a; y++)
 +                                        {
 +                                                printf("%hhd", *(num1+y));
 +                                        }
 +                                        printf("\n");
 +                                        break;
 +
 +                        case 3:
 +                                        multiply(num1, num2, num3, num4, a);
 +
 +                                        y=0;
 +
 +                                        printf("\nThe product of the two numbers is: ");
 +                                        for(y=0; y<a; y++)
 +                                        {
 +                                                printf("%hhd", *(num1+y));
 +                                        }
 +                                        printf("\n");
 +                                        break;
 +
 +                        case 4:
 +                                        divide(num1, num2, num3, num4, a);
 +
 +                                        y=0;
 +
 +                                        printf("\nThe quotient of the two numbers is: ");
 +                                        for(y=0; y<a; y++)
 +                                        {
 +                                                printf("%hhd", *(num4+y));
 +                                        }
 +                                        printf("\n");
 +                                        break;
 +
 +                        }
 +
 +        }
 +
 +        while (x != 6);
 +
 +        printf("\n");
 +        printf("\n");
 +
 +        return(0);
 +}
 +
 +void add(char *num1, char *num2, char a)
 +{
 +        char y, c = 0;
 +
 +        for(y=a-1; y>=0; y--)
 +        {
 +                c=*(num1+y)+*(num2+y);
 +
 +                if(c >= 10)
 +                {
 +                        *(num1+y)=c-10;
 +                        if (y != 0)
 +                        {
 +                                *(num1+y-1)=*(num1+y-1)+1;
 +                        }
 +                }
 +                else
 +                {
 +                        *(num1+y)=c;
 +                }
 +        }
 +
 +        return;
 +}
 +
 +void subtract(char *num1, char *num2, char a)
 +{
 +        char y, c = 0;
 +        for (y=a-1; y>=0; y--)
 +        {
 +                c=*(num1+y)-*(num2+y);
 +
 +                if(c < 0)
 +
 +                {
 +                        *(num1+y)=c+10;
 +                        if(y != 0)
 +                        {
 +                                *(num1+y-1)=*(num1+y-1)-1;
 +                        }
 +                }
 +                else
 +                {
 +                        *(num1+y)=c;
 +                }
 +
 +        }
 +
 +        return;
 +}
 +
 +void multiply(char *num1, char *num2, char *num3, char *num4, char a)
 +{
 +        char y;
 +
 +        char *numLocal=(char*)malloc(sizeof(char)*a);
 +
 +        for(y=0; y<a; y++)
 +        {
 +                *(numLocal+y)=*(num1+y);
 +                *(num1+y)=0;
 +        }
 +
 +        while(compare(num2, num4, a) !=0)
 +        {
 +                add(num1, numLocal, a);
 +                subtract(num2, num3, a);
 +        }
 +
 +        return;
 +
 +}
 +
 +void divide(char *num1, char *num2, char *num3, char *num4, char a)
 +{
 +        char y;
 +
 +        char *numLocal=(char*)malloc(sizeof(char)*a);
 +
 +        for(y=0; y<a; y++)
 +        {
 +                *(numLocal+y)=*(num2+y);
 +        }
 +
 +        while(compare(num1, numLocal, a) !=-1)
 +        {
 +                subtract(num1, numLocal, a);
 +                add(num4, num3, a);
 +        }
 +
 +        return;
 +}
 +
 +char compare(char *num1, char *num2, char a)
 +{
 +        char y, flag=1;
 +
 +        for(y=0; y<a; y++)
 +        {
 +                if(*(num1+y)==*(num2+y))
 +                {
 +                        flag=0;
 +                }
 +                else
 +                {
 +                        if(*(num1+y)>*(num2+y))
 +                        {
 +                                flag=1;
 +                        }
 +                        else
 +                        {
 +                                flag=-1;
 +                        }
 +                        break;
 +                }
 +        }
 +        return(flag);
 +}
 +</code>
 +=====Execution=====
 +
 +An example run of the bignum addition process:
 +
 +<cli>
 +lab46:~/src/cprog/project2$ ./bignum
 +
 +
 +What would you like to do:
 +Enter '1' for addition.
 +Enter '2' for substraction.
 +Enter '3' for multiplication.
 +Enter '4' for division.
 +Enter '6' to quit.
 +
 +Please enter an option: 1
 +
 +Please enter the number of digits of your largest number: 3
 +
 +Please enter your first number.
 +Note, If this number is the smaller of the two numbers be sure to pad the number with zeros): 025
 +
 +Please enter your second number.
 +Note, if this number is the smaller of the two numbers be sure to pad the number with zeros): 025
 +
 +The sum of the two numbers is: 050
 +
 +What would you like to do:
 +Enter '1' for addition.
 +Enter '2' for substraction.
 +Enter '3' for multiplication.
 +Enter '4' for division.
 +Enter '6' to quit.
 +
 +Please enter an option: 6
 +
 +lab46:~/src/cprog/project2$
 +
 +</cli>
 +
 +An example run of the bignum substraction process:
 +
 +<cli>
 +lab46:~/src/cprog/project2$ ./bignum
 +
 +
 +What would you like to do:
 +Enter '1' for addition.
 +Enter '2' for substraction.
 +Enter '3' for multiplication.
 +Enter '4' for division.
 +Enter '6' to quit.
 +
 +Please enter an option: 2
 +
 +Please enter the number of digits of your largest number: 3
 +
 +Please enter your first number.
 +Note, If this number is the smaller of the two numbers be sure to pad the number with zeros): 025
 +
 +Please enter your second number.
 +Note, if this number is the smaller of the two numbers be sure to pad the number with zeros): 005
 +
 +The remainder of the two numbers is: 020
 +
 +What would you like to do:
 +Enter '1' for addition.
 +Enter '2' for substraction.
 +Enter '3' for multiplication.
 +Enter '4' for division.
 +Enter '6' to quit.
 +
 +Please enter an option: 6
 +
 +lab46:~/src/cprog/project2$
 +</cli>
 +
 +An example run of the bignum multiplication process:
 +
 +<cli>
 +lab46:~/src/cprog/project2$ ./bignum
 +
 +
 +What would you like to do:
 +Enter '1' for addition.
 +Enter '2' for substraction.
 +Enter '3' for multiplication.
 +Enter '4' for division.
 +Enter '6' to quit.
 +
 +Please enter an option: 3
 +
 +Please enter the number of digits of your largest number: 3
 +
 +Please enter your first number.
 +Note, If this number is the smaller of the two numbers be sure to pad the number with zeros): 025
 +
 +Please enter your second number.
 +Note, if this number is the smaller of the two numbers be sure to pad the number with zeros): 005
 +
 +The product of the two numbers is: 125
 +
 +What would you like to do:
 +Enter '1' for addition.
 +Enter '2' for substraction.
 +Enter '3' for multiplication.
 +Enter '4' for division.
 +Enter '6' to quit.
 +
 +Please enter an option: 6
 +
 +lab46:~/src/cprog/project2$
 +</cli>
 +
 +An example run of the bignum division process:
 +
 +<cli>
 +lab46:~/src/cprog/project2$ ./bignum
 +
 +
 +What would you like to do:
 +Enter '1' for addition.
 +Enter '2' for substraction.
 +Enter '3' for multiplication.
 +Enter '4' for division.
 +Enter '6' to quit.
 +
 +Please enter an option: 4
 +
 +Please enter the number of digits of your largest number: 3
 +
 +Please enter your first number.
 +Note, If this number is the smaller of the two numbers be sure to pad the number with zeros): 025
 +
 +Please enter your second number.
 +Note, if this number is the smaller of the two numbers be sure to pad the number with zeros): 005
 +
 +The quotient of the two numbers is: 005
 +
 +What would you like to do:
 +Enter '1' for addition.
 +Enter '2' for substraction.
 +Enter '3' for multiplication.
 +Enter '4' for division.
 +Enter '6' to quit.
 +
 +Please enter an option: 6
 +
 +lab46:~/src/cprog/project2$
 +</cli>
 +
 +
 +=====Reflection=====
 +This project turned out to be much tougher than I originally hypothesized. Several arrays were required to make the multiplication and division work correctly. While very challenging to me as a person new to the C programming language I found the project both challenging and fun.
 +
 +=====References=====
 +In performing this project, the following resources were referenced:
 +
 +  * C Pocket Reference
 +  * Class IRC
 +  * Wedge

Page Tools

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki