Coding Assignment: Pyramid of Numbers

Objective

Problem Description

This weeks assignment deals with an old fashioned primary school problem. Most of you will know the "Turmrechnen" as a pain of your former school days. How it works is shown in the following example:

Pyramid of Numbers

Please enter a number: 3453454359654646756757434
3453454359654646756757434 * 2 = 6906908719309293513514868
6906908719309293513514868 * 3 = 20720726157927880540544604
20720726157927880540544604 * 4 = 82882904631711522162178416
82882904631711522162178416 * 5 = 414414523158557610810892080
414414523158557610810892080 * 6 = 2486487138951345664865352480
2486487138951345664865352480 * 7 = 17405409972659419654057467360
17405409972659419654057467360 * 8 = 139243279781275357232459738880
139243279781275357232459738880 * 9 = 1253189518031478215092137649920
1253189518031478215092137649920 / 2 = 626594759015739107546068824960
626594759015739107546068824960 / 3 = 208864919671913035848689608320
208864919671913035848689608320 / 4 = 52216229917978258962172402080
52216229917978258962172402080 / 5 = 10443245983595651792434480416
10443245983595651792434480416 / 6 = 1740540997265941965405746736
1740540997265941965405746736 / 7 = 248648713895134566486535248
248648713895134566486535248 / 8 = 31081089236891820810816906
31081089236891820810816906 / 9 = 3453454359654646756757434

Since really big numbers cannot be handled by the typical number types like int, long, double, etc. we have to work around this shortcoming. The basic idea is to create a struct BigInt which handles such big integers by storing every single digit of a number as elements of an array of integers. So the struct holds a member digits storing the digits of the big number and a member digit_count which stores the number of digits.

Example of a BigInt

Consider the number n = 4 345 978 349 843 534 984 529 235 492 457 with 31 digits which is definitely longer than the largest integer type possible (long long). This number would be represented in a BigInt where every digit of n is stored as an element of digits, i.e., digits[0] == 7, digits[1] == 5, digits[2] == 4, and so forth. Note that the digits are stored starting from the least significant digit. The member digit_count holds the number of digits, in our example 31.

Overall Procedure

The procedure is then as follows:

Get the user input and store it in an array of char.
Call str_to_big_int which takes every character of the user input, converts it to an integer, and stores this into the BigInt.
Do the pyramid calculations and write the results as they come up. Since the standard multiplication and division operations will not work on BigInt you have to implement these procedures by yourself.

Things to Learn

This assignment is related to the competency 3.1. In particular you will deepen your knowledge in

Using aggregate data types (structs)
Implementing functions
Reading specifications
Repeat a bit of algorithmic thinking

Required Tasks

Implement a struct BigInt with the members
- digits (array of integers of size 160)
- digit_count (integer)
Implement the function int str_to_big_int(char* input, int len, struct BigInt* big_int), where
- input is the array of chars which holds the user input
- len is the number of digits actually entered by the user
- big_int is the address to a BigInt variable provided by the main function
- the function returns the number of digits converted
The function iterates over the content of input, checks every character whether it is a digit and if it is a digit it is converted to an int and then stored into the array of big_int. Note that if the user failed to enter only digits the conversion stops at the point where str_to_big_int runs against a non-digit.

Finally the function returns the number of digits converted from the array of char to a BigInt. This is at most len but can be less if input contains non-digits.
Implement the function void print_big_int(const struct BigInt* big_int), where
- big_int is the big integer to be printed.
The function prints the number big_int into the console.

Furthermore, test the functions implemented so far by implementing the user input in the main function and by calling str_to_big_int and print_big_int. Try different scenarios (small numbers and really large numbers, erroneous input) and check whether your program behaves correctly.
Implement the function void multiply(const struct BigInt* big_int, int factor, struct BigInt* big_result), where
- big_int is the number to be multiplied
- factor is the factor by which big_int shall be multiplied
- big_result is the number getting the result of the multiplication.
Again test your function throughly. In the meanwhile you should be able to show the increasing side of the pyramid.
Implement the function void divide(const struct BigInt* big_int, int divisor, struct BigInt* big_result), where

big_int is the number to be divided
divisor is the divisor by which big_int shall be divided
big_result is the number getting the result of the division.

Again test your function throughly. Your pyramid should be now complete.

Hints

Use a symbolic constant to define the maximum size of a BigInt
Use the function strlen of string.h to get the number of actual characters in a string. The sequence is basically shown below.

   #include <string.h>
   ...
   char user_input[MAX_DIGITS];
   ...
   int len = strlen(user_input);
   ...

Conversion from char to int: int x = '5' - '0' // x == 5
Store the digits in reverse order to make the multiplication and division algorithm better understandable.
To get a feeling how to implement the multiplication and division, recall the procedures you learned in primary school for dividing and multiplying large numbers.
It might be of use to implement a function which copies a BigInt from one variable to another.

Evaluation

All coding assignments will get checked. Most common reasons that your assignment is marked down are:

Program does not build or builds with warnings
One or more items in the Required Tasks section are not satisfied
Submitted code is visually sloppy and hard to read

Extra Credits

Enhance the implementation of the function print_big_int by doing a pretty print, i.e., that the number shall be separated by a blank at every third place.
The required pyramid calculator can only multiply with numbers being a unary digit integer. Make the pyramid calculator ready to deal with pyramids being wider than 16, i.e., it shall be able to multiply not only by numbers 2 to 9 but 2 to any arbitrary big integer.

6.7 KiB Raw Permalink Blame History