This must be coded in the C language and it must use doubly linked lists. Demons
ID: 3791661 • Letter: T
Question
This must be coded in the C language and it must use doubly linked lists.
Demonstrating
Structures
Pointers
Linked Lists
Dynamic Allocation
Overview
Applications from scientific computation to distributed databases to physicalsimulations to image rendering all have a need to deal with incredibly large and precise information; however, hardware (like a processor) is intrinsically bounded in its capabilities – it cannot magically process an arbitrarily precise piece of data. Softwaremust help. In this lab, you will explore a means to allow mathematical operations on very large numbers.
Outline
• You will implement a program capable of “truly arbitrary precision integer arithmetic”.
• This means the user can use integers of any size
o A typical short integer (16 bits) can represent a maximum value of 65,535
o A typical long integer (32 bits) can represent a maximum value of 4,294,967,295
o A typical long long integer (64 bits) can represent a maximum value of 18,446,744,073,709,551,615
o We want to allow the user to use much, much, much bigger numbers
• The user will enter two (base 10) integers, of an arbitrary size
• The user will then select an operation:
o Add (‘+’)
o Subtract (‘-‘)
• The program will print the result, and quit
• Negative numbers are not allowed
Design
Integers will be represented as a linked list of single digits
o To grow an integer, you allocate and link new digits
integer.c
o Will contain, at a minimum, the following functions:
‘add’, which accepts two ‘immense_int_t’s, and returns a new ‘immense_int_t’
representing their sum
‘subtract’, which accepts two ‘immense_int_t’s, and returns a new‘immense_int_t’ representing their difference
A function to create a new ‘immense_int_t’
A function to destroy an ‘immense_int_t’
Constraints
Input
o All input lines are terminated with a newline character (‘ ’). There is no otherwhitespace on an input line.
o An input integer will have at least one digit.
o There is no upper bound on the size of the input integers, other than it will not be solarge that your process runs out of memory.
o There will be no commas in the input integer; the only valid input characters for an
integer are 0-9.
o The first two input lines will always be integers, the last (third) input line will alwaysbe either the character ‘+’, or ‘-‘, indicating the desired operation
o When subtraction is specified, the larger number will always be first, so that the
result remains positive.
o Input integers will have no leading 0’s.
Output
o Your output should consist of only the result, followed by a newline character (‘ ’).
Do not include any other whitespace or output.
o Your output integer should have no leading 0’so Valid characters for the result are 0-9
Implementation Hints
Simulate longhand addition and subtraction, working with a single digit at a time, as you
might while working with pencil and paper.
Sample input and output
Example input 1:
o 10984729
o 93940001
o +
Example output 1:
o 104924730
Example input 2:
o 1092337
o 342888
o -
Example output 2:
o 749449
Example view from the command line, with manual input/output
o ./integer
o 10984729
o 93940001
o +
o 104924730
o ./integer
o 1092337
o 342888
o -
o 749449
Compiling and Naming
Your source code must be named “integer.c”
Your source must compile with:
gcc –Wall integer.c –o integer
You can run your program in GDB by first compiling with symbols (-g) then invokingGDB:
gcc -g –Wall integer.c –o integer
gdb -ex run ./integer
I highly suggest running your program in the above fashion even if you have beenstubbornly resisting gdb. Diagnosing a "Segmentation Fault" when using pointers isvirtually impossible without the use of gdb. GDB will be your friend in this lab. Trust me,just do it.
You can run your program through an industry standard tool called valgrind to searchfor memory leaks. At the end of execution, valgrind will let you know if your programleaks memory. To run your program through valgrind use the following command:
valgrind ./integer
Explanation / Answer
Example output 2:
o 749449
Example view from the command line, with manual input/output
o ./integer
o 10984729
o 93940001
o +
o 104924730
o ./integer
o 1092337
o 342888
o -
o 749449
Compiling and Naming
Your source code must be named “integer.c”
Your source must compile with:
gcc –Wall integer.c –o integer
You can run your program in GDB by first compiling with symbols (-g) then invokingGDB:
gcc -g –Wall integer.c –o integer
gdb -ex run ./integer
I highly suggest running your program in the above fashion even if you have beenstubbornly resisting gdb. Diagnosing a "Segmentation Fault" when using pointers isvirtually impossible without the use of gdb. GDB will be your friend in this lab. Trust me,just do it.
You can run your program through an industry standard tool called valgrind to searchfor memory leaks. At the end of execution, valgrind will let you know if your programleaks memory. To run your program through valgrind use the following command:
valgrind ./integer
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.