hardest homework so far substantial margin think it practice facebook or google

This is the hardest homework so far, by a substantial margin. Think of it as a practice Facebook or Google internship interview coding problem! 

The most elegant solution among the first few submitted will get a special prize, and an invitation to work in our lab. TBA. Focus on elegance & simplicity, for now, rather than efficiency. 

First part is simpler, involving addition of arbitrary long numbers, & multiplication with single-digit multipliers. 

The second part will simply adding a few lines (I expect 10-15) to the first part, to produce multiplication of arbitrary-long
numbers. 

 

PART1: longpart1.c

 

The parts of this assignment are: 

0) Checking if a long positive decimal number is valid (i.e., has no non-numerical, non-decimal digits)
1) Addition of two long positive numbers. 
2) Multiplication of the first long positive number by  numbers between 2 and 9

You’ll do this by implementing one non-recursive main function, to do each of the operations. This main function will set up initial conditions and call a recursive helper function to actually do the operation in a recursive manner. 

All above have to be implemented using a recursive helper function for each of the above. ALL HELPER FUNCTIONS HAVE to be recursive.  There should be one recursive helper function for the checking, one for the addition, and one for the single digit mutiplication. If it isn’t, we will consider it cheating, and award negative points that will be carried into your total score. See below. 

You will store them as char * strings, and implement these subroutines that call the recursive helper functions:

int digcheck(char *theno) is “theno” a string that is a valid decimal number? 
char *add2(char *n1, char *n2)  add 2 numbers n1 and n2 and return the result 
char *smult(char *n1, char d) multiply long number n1 by a single digit number d and return the result.

 

The add2 and smult are non-recursive functions will allocate memory for the result, on the heap,  (to be discussed), and perhaps do some copying and then call helper functions which MUST BE recursive. Hint: These helper functions will require an extra argument, the carry digit. Think about it. They both return a pointer to the result, which is a string that they allocate on the heap. The helper recursive function will be essentially marching along from lower significant digits to upper significant digits. Think recursively: can you add single decimal digits stored in character form? OK. Now, then. If you have
successfully added the succeeding two streams of digits, and have a carry digit, how do produce the next digit, and move on? 

The design of these helper functions is up to you, but they MUST BE RECURSIVE. Please ask for help if you don’t know how; don’t submit a non-recursive solution, because you WILL get negative points for that. We will spot check a number of homeworks by hand, if the solutions are not recursive, you WILL get -10 points for homework, which will be deducted from your over all  homework score. If you don’t know how to do it recursively, ask us for help. Don’t submit a non-recursive solution. Next week’s tutorials will be talking about this homework, and I will have extra office hours next week. We want you to succeed! 

PART2 (longpart2.c)   Multiplication of two long positive numbers; also implemented recursively. My implementation of the long multiplication is a seven-line recursive routine, that calls add2, and another little helper function. The signature of the recursive routine is: 

char *longmult(char *num1, char  *num2, /*HINT: note the third argument*/ char *accum). 

Again, it must be recursive. Non-recursive solutions WILL receive negative points. Don’t submit a non-recursive solution. 

Example below including all parts (full details will be out tomorrow):