0

I am supposed to write a function that multiplies two big numbers which are in two linked lists. I need help figuring out an algorithm that does that the same way you would solve it on pen and paper. here is what i'm thinking of:

I would use a nested for loop to iterate through both lists while multiplying each of the elements but i'm not sure how to handle the carrying situation. I've already implemented a function that adds two linked lists of integers. any input would be appreciated.

Texasy04
  • 3
  • 2
  • Is recursion an option? – Ole V.V. Jul 06 '20 at 02:38
  • Can you show the code you have written? It will be easier to explain things in terms of something you already understand, than to come up with something new which may confuse you even more – Joni Jul 06 '20 at 04:40
  • see [Fast bignum square computation](https://stackoverflow.com/q/18465326/2521214) so either use naive `O(n^2)` approach or Karatsuba. But beware the Karatsuba needs more carry bits ... – Spektre Jul 06 '20 at 07:16

1 Answers1

0

I would go for recursion (if you haven’t heard about recursion, you can probably ignore this answer; you will get around to learning it sooner or later).

I am taking the multiplication 152 * 463 as an example. My calculator tells me that the expected result is 70376. My idea is to split off the 2 from 152 to get 15 and 2 and then multiply 15 * 463 and 2 * 463:

 15 * 463 = 6945. Needs to be multiplied by 10 because the 15 were in the 10s’ position. 6945 * 10? Just add a zero: 69450.
 2 * 463 = 926.

 Product is 69450 + 926 = 70376.

In your code 15 * 463 is obtained through a recursive call to the multiplication method that you are writing. Multiplication by 10 is easy, just append a zero. 2 * 463 is simpler because we’re multiplying by a 1-digit number. Write a new recursive method for this subtask. The function that you already have that adds two linked lists will finish the job.

Ole V.V.
  • 81,772
  • 15
  • 137
  • 161