# Thread: Can someone try to explain what my professor is talking about...

1. ## Can someone try to explain what my professor is talking about...

Hi friends!

I have a problem set which we have to read in large integers from a file and multiply them, but the numbers can't be int because they are too big so we have to read them in character by character and create a convert function and multiply function.

Anyways, he writes here:

Each integer is represented as an array of digits, where the least significant digit is storedin index 0, and the last index stores a non-zero number. (The only exception to this is 0,
which is stored in an array of size 1 that has a single element storing 0.) For instance, the
value 1234567890 would be stored as:

index 0- 0
index 1- 9
index 2- 8
index 3- 7
index 4- 6
index 5- 5
index 6- 4
index 7- 3
index 8- 2
index 9- 1

Note: Although this seems counter-intuitive, it makes the code slightly easier, because in
all standard mathematical operations, we start with the least significant digit. It also
makes sense that the digit at the place 10i is stored in index i.

Can someone explain what he means here?
Also, I hate to ask but can someone explain to me what steps it takes to do this problem, I attached the problem if you are interested. The professor didn't teach the way to solve a problem like this. Please note, I am not looking for the answer, just someone with more experience to explain to me.Thanks

2. Copied from PDF by hand; might have mistakes.
Which part do you not understand?

I suggest writing the print function first.
Second, I would do the convert_integer function.
Third, I would write the suggested addition function.
Fourth, I would write the multiply function.
Last, I would do the full program reading the data file.

Edit: The solution to this problem would be more elegant with the use of dynamic memory via the malloc and related functions.
I would write it using dynamic memory; but, you might not yet have learned that.

Tim S.

Code:
```struct integer {
int* digits;
int size;
}

struct integer* convert_integer(char* stringInt);

void print(struct integer *p);

struct integer* multiply(struct integer *p, struct integer *q);```
The code I used to test the print function I wrote.
Code:
```#include <stdio.h>

struct integer {
int* digits;
int size;
};

void print(struct integer *p);

int main()
{
struct integer testValue;
int testDigits[] = {0,9,8,7,6,5,4,3,2,1};
testValue.digits = testDigits;
testValue.size = sizeof(testDigits)/sizeof(testDigits[0]);

printf("testValue.size:= %d\n", testValue.size);

print(&testValue);

return 0;
}```

3. I did something similar to solve a projecteuler question a few months ago.

The best place to start is to get a pen and paper and start multiplying 2 numbers together - I assume that you remember multiplication.

Think of the carry as a variable and the answer as a third array.

Once you do a few different numbers by hand, the algorithm is very quick to work out

4. The description of the problem is perfectly clear. I wouldn't know what to do differently than copy and paste the same description back to you. You just store the numbers as reversed strings, and then do the maths on those strings yourself with a couple of nested loops. It's no different to how you do it on paper. Just make a start and post the code for more help.

I have already written code that solves this exact problem in C++, except I didn't store the strings reversed because I found it to have negligible performance benefit in my case. (std::strings have a constant time length() function.)

5. I did it almost exactly as Click_here described above. I used three int arrays:
Code:
```  car[]
x num[]
=========
ans[]```
and followed exactly the same method as multiplying by hand. For the last bit of speed, you'd want a faster bit hack, but this is fast enough.

I didn't reverse any numbers. Working from the larger index to the smallest one seemed quite natural.

The technique of starting your program modeled after how you do something on paper, is a good place to start, imo. So many times you'll start with that, and think "wait! This would be a more efficient way ...".

6. Code:
```int main()
{
// File pointer and file opening code. Test to see if the file is able to read is also included.
FILE *ifp = fopen("bigint.txt", "r");
if (!ifp)
{
printf("The file is unable to open!\n");
return -1;
}

int num_operations, i;

fscanf(ifp, "%d", &num_operations);

for (i=0; i < num_operations; i++)
{

char *stringInt = malloc(sizeof(char));

int k;
char fullString[SIZE], temp1[SIZE], temp2[SIZE];

for (k=0; k != '\0'; k++)
{
stringInt[i] = malloc(sizeof(char));
fscanf(ifp, "%s", fullString[SIZE]);
}

int j = 0;
fscanf(ifp, "%s", fullString[j]);

while (fullString[j] != ' ')
{
fullString[j] = temp1[j];
j++;
}

while (fullString[j] != '\0')
{
fullString[j] = temp2[j];
j++;
}

// Assigns the line 1 of the text file to num_operations. TESTED AND WORKS!
//fscanf(ifp, "%d", &num_operations);

}

// Close the file.
fclose(ifp);

return 0;

}```
This is what I have so far.

The test case is:
Code:
```3
4 5
27 10
1111111111111111111 4```
In my main function, I am reading the
Code:
`3`
into num_operations and then trying to move to the second line and store
Code:
`4 5`
into one array, I don't think I am doing this right though. After doing that, I want to store them into individual arrays using the two while loops. Is this the right approach to solve the conversion of integers to individual characters?

I truly feel so lost with this problem it is very discouraging. My plan is to read in the single character array, pass it into a function that will then split it into two character arrays, and then converting them into integers. After that I have to follow through with the multiplication.

7. Why work with chars, at all? Read the digits in as ints, put them into int arrays, and multiply and add any carry to the correct column. There's no need for a char "middle man".

8. I see what you are saying, however we have no choice but to convert them into characters.

9. I would give you advice; but, I have no idea where to start.
Your code has only slight resemblance to the problem.

I would do a bottom-up design; but, you look like you are trying a top-down design.
If you understand the big picture better than the details top-down design is a good choice.

I use bottom-up design most often because I often have no grasp of the big picture; till after I solve small details.

Both ways work; but, you seem to be writing code I can not easily follow how it relates to the problem.

Top-down and bottom-up design - Wikipedia, the free encyclopedia

Tim S.

10. I never really learned this strategy. In top down approach always seemed natural because for example how am I going to test the numbers the prof gave us and match the exact output without the problem working. I am a noob programmer and this project is very difficult for me. I don't understand why we are using all these pointers and structs. I am a cs major and I am feeling very discouraged right now. I should try the bottom up approach but I don't know what to test for if the problem itself isn't solved. I suck at this but it's the only thing I picture studying

11. I am having trouble sleeping so I did a little work on this.

Here's the code I am testing with.

I have decided after getting the addition function to work to not use it. But, it was useful as a re-learning experience. I tend to get a little confused around this time of being up for about 20 hours.

Tim S.

Code:
```struct integer* addition(struct integer *p, struct integer *q);

void print(struct integer *p);
struct integer* convert_integer(char* stringInt);
struct integer* multiply(struct integer *p, struct integer *q);

int main()
{
struct integer testValue;
int testDigits[] = {0,9,8,7,6,5,4,3,2,1};
testValue.digits = testDigits;
testValue.size = sizeof(testDigits)/sizeof(testDigits[0]);

printf("testValue.size:= %d\n", testValue.size);

print(&testValue);

print(convert_integer("12345678910"));

return 0;
}```

12. My test results and test code.

Code:
```testValue.size:= 10
1234567890
12345678910
0
0
99
9000000000
99999999910
Error: NULL pointer passed to print function
10000000000
0
999990000
1000000
999998000001```
Code:
```#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct integer {
int* digits;
int size;
};

/* Make all the digits 9 or less by carrying the value to next higher digit */
/* WARNING returns NULL pointer if size is too small */
struct integer* normalize_digits(struct integer *p);
/* Reduce the size by how many leading digits are zero; min size is 1 */
struct integer* normalize_size(struct integer *p);

void print(struct integer *p);
struct integer* convert_integer(char* stringInt);
struct integer* multiply(struct integer *p, struct integer *q);

int main()
{
struct integer testValue3;
int testDigits3[] = {10,9,9,9,9,9,9,9,9,9};
testValue3.digits = testDigits3;
testValue3.size = sizeof(testDigits3)/sizeof(testDigits3[0]);

struct integer testValue2;
int testDigits2[] = {10,9,9,9,9,9,9,9,9,8};
testValue2.digits = testDigits2;
testValue2.size = sizeof(testDigits2)/sizeof(testDigits2[0]);

struct integer testValue;
int testDigits[] = {0,9,8,7,6,5,4,3,2,1};
testValue.digits = testDigits;
testValue.size = sizeof(testDigits)/sizeof(testDigits[0]);

printf("testValue.size:= %d\n", testValue.size);

print(&testValue);

print(convert_integer("12345678910"));

#if 1 /* change 1 to 0 to disable this code section */
print(normalize_size(convert_integer("0000000"))); /* 0 */
print(normalize_size(convert_integer("0")));       /* 0 */
print(normalize_size(convert_integer("99")));      /* 99 */

print(normalize_digits(&testValue2));              /* 9000000000   */
print(&testValue3);                                /* 99999999910  */
print(normalize_digits(&testValue3));              /* NULL POINTER */
print(&testValue3);                                /* 10000000000  */
#endif

print(multiply(convert_integer("1000"), convert_integer("0"))); /* 0 */

print(multiply(convert_integer("99999"), convert_integer("10000"))); /* 999990000 */

print(multiply(convert_integer("1000"), convert_integer("1000"))); /* 1000000 */

print(multiply(convert_integer("999999"), convert_integer("999999"))); /* 999998000001 */

return 0;
}```
No plans to work on this anymore; the major thinking for me is solving the lower level functions. The read and process of the data file holds no interest. Nothing for me to learn doing it. And if I did it, I might be temped to post it; that much help is against the idea of this site.

Edit: Both my normalize_ functions returns the pointer passed to it; except in errors where NULL pointer is returned.
This allows easier testing.

Tim S.

I did it almost exactly as Click_here described above. I used three int arrays:
Code:
```  car[]
x num[]
=========
ans[]```
Can you explain what carry does please? Thanks for all of your guys help so far.

14. Originally Posted by Simon Pacheco
Can you explain what carry does please? Thanks for all of your guys help so far.
First, I should explain that there is no need to use int's in this algorithm - it works just as well with chars. It's just my opinion that it's easier to do this with ints - but it's certainly NOT a requirement.

The carry array holds the amount that falls into the next column up, when you add or multiply:

7 x 7 = 49, so
Code:
```char carry[3]= {0};
char num1[3]=7;
char num2[3]=7;
char answr[3]={0};```
Multiplying 7 x 7, answr[] immediately gets the 9 in one slot of the answr[] array (hi or low index position depends on your logic, but either way it gets ONE index in the answr[] array.

But the 40 part of the answer won't fit into a digit less than 10, so the zero is dropped, (essentially dividing by 10 since the next column in our base 10 requires it), and then moves from the carry[] array, down to the answr[] array.

It's clear that you're over-thinking this problem. Think of the number line, and emphasize the COLUMNS (one's, tens, hundreds, thousands, etc.) in our base 10 number system.

Each operation is done FOR THAT COLUMN on a digit less of 9 or less. Everything else must be carried (or borrowed for subtraction), to or from an adjacent column's digit.

It's been a long time since I did this, but I don't believe you need to work with integers, at all. Chars are enough, and they can be added, multiplied, subtracted, etc. They're basically just small int's (but when you display them, they show their offset value - you don't want that offset value - so subtract '0' from them, straight away, and you should be good to go.

char chr = 0; means chr equals 48 decimal. That is it's offset. You want it to be a REAL 0, so

Code:
`chr -= '0';  // chr = chr-'0'`
does the trick. That's true for all chars, btw.

chr = '1'; char chr assigned the value of '1' (49). Change is:

Code:
`chr -= '0'; //chr=chr-'0'. Now chr equals a REAL 1, not 49.`

15. Originally Posted by Simon Pacheco
I see what you are saying, however we have no choice but to convert them into characters.
au contraire...

"You must use the following struct:"
Code:
```struct integer {
int* digits;
int   size;
}```
"Here are the prototypes of the functions you must write:"
Code:
```struct integer* convert_integer( char* stringInt );
...
void print( struct integer *p );
...
struct integer* multiply( struct integer *p, struct integer *q );```
Pretty clear you're expected to convert the character string to a dynamic array of int-s.