8 Replies - 280 Views - Last Post: 26 September 2018 - 06:47 AM Rate Topic: -----

#1 Metal488   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 8
  • Joined: 15-September 18

How to add/multiply long integers recursively with lists

Posted 15 September 2018 - 07:19 AM

I am trying to figure out how to add and multiply large integers using lists. I know you can just do val1+val2 or val1*val2, but I am having to figure out how to do it after splitting the numbers into lists.
I'll be given lines like 12345678*987654321 and then I will be given a number of nodes per digit, so if that number was 3 the numbers would be ["012", "345", "678"] and ["987", "654", "321"] (I add zeroes at beginning to get correct number of digits).
I then have to add/multiply them together. I have everything done up to that point, I'm just having trouble with the add/mult.
For the multiplication I am allowed to recombine the nodes into one number again, but then I have to multiply recursively.
I have this function:
def mult(x,y):
    if(y == 0):
        return 0
    return x + mult(x, y-1)


but it doesn't work with large functions (reaches maximum recursion depth)

I have this for add:
def recursive_sum(l1, l2, idx = 0):
    if idx < min(len(l1), len(l2)):
        return [int(l1[idx]) + int(l2[idx])] + recursive_sum(l1, l2, idx + 1)
    else:
        return []


This works somewhat, but it turns ['001', '234', '567'], '+', ['007', '894', '561'] into [8,1128,1128], the answer is 9128128 so it works but it doesn't deal with carryout. It also doesn't work if the two lists don't have the same number of elements.

Is This A Good Question/Topic? 0
  • +

Replies To: How to add/multiply long integers recursively with lists

#2 Metal488   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 8
  • Joined: 15-September 18

Re: How to add/multiply long integers recursively with lists

Posted 15 September 2018 - 07:36 AM

The integers can also be much longer than my example. They could be around 15 digits long or maybe even more.
Was This Post Helpful? 0
  • +
  • -

#3 DK3250   User is offline

  • Pythonian
  • member icon

Reputation: 463
  • View blog
  • Posts: 1,468
  • Joined: 27-December 13

Re: How to add/multiply long integers recursively with lists

Posted 15 September 2018 - 08:15 AM

Hello Metal488, welcome to Dream-In-Code; I hope you will find it helpful.

The rules here is not just to hand out code, but rather push(hint you to find the answer yourself.

I only looked into the addition question.
Apparently you add from the front: First digit group, then second digit group and so on.
If you add by hand you always start from the back, I suggest your code should do the same.
Also you need to handle the carry in the recursive call.

See if this hint brings you forward - and feel free to come back here if you get stuck.
Was This Post Helpful? 0
  • +
  • -

#4 Metal488   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 8
  • Joined: 15-September 18

Re: How to add/multiply long integers recursively with lists

Posted 16 September 2018 - 12:57 PM

I think I see what you're saying DK3250. I tried adjusting my function to do that, but I don't think I really changed anything. However, I have been working on it a different way and I think it's working. The only problem is that I think I may have made it way more complicated than I needed to. But I mean if it works....
Here's my new code:
#Makes a list the same size as another longer list by taking in the short list and the length of the longer list and adding zeroes to the #beginning
def eqSize(sList, mx):
    if (len(sList) < mx):
        sList.insert(0, "0")
        eqSize(sList, mx)
    
    return sList

#This is how I tried to make it go the other way, but it ends up doing it in the same order
def Brecursive_sum(l1, l2, idx):
    if idx >= 0:
        print(int(l1[idx]) + int(l2[idx]))
        return Brecursive_sum(l1, l2, idx - 1) + [int(l1[idx]) + int(l2[idx])]
    else:
        return []

#This get's the result from the sum function and deals with carryout
def carryout(myList, ND, pos, Res = []):
    strly = str(myList[pos])
    
    if(pos < 0):
        return []
    else:
        if(len(strly) > ND):
            myList[pos-1] = myList[pos-1] + int(strly[0])
            strly = strly[1:]
            myList[pos] = int(strly)
            carryout(myList, ND, pos-1)
    return myList

#This checks each element of the list and adds zeroes where previous functions removed them to make sure every element has the same number #of digits
def AZlist(lst, ND, index = 0):
    if(len(lst) == 0):
        return []
    elif(index < len(lst)):
        lst[index] = str(lst[index]).zfill(ND)
        AZlist(lst, ND, index+1)
    return lst  


list1 = ["001", "234", "567"]
list2 = ["123", "007", "894", "561"]    

if(len(list1) > len(list2)):
    list2 = eqSize(list2, len(list1))
elif(len(list1) < len(list2)):
    list1 = eqSize(list1, len(list2))

length = len(list1)-1 

Result = Brecursive_sum(list1, list2, length)   
Result = carryout(Result, 3, length)

Result = AZlist(Result, 3)        
print(Result) 



This gave me the result I was hoping for from adding 1234567 and 123007894561, but I feel like I made it may more complicated than it needs to be. Is there a simple way for me to condense all this?
Was This Post Helpful? 0
  • +
  • -

#5 DK3250   User is offline

  • Pythonian
  • member icon

Reputation: 463
  • View blog
  • Posts: 1,468
  • Joined: 27-December 13

Re: How to add/multiply long integers recursively with lists

Posted 16 September 2018 - 01:26 PM

Programming is not an exact science; your code, however, seems overly complicated.

I'll focus on the Brecursive_sum() function (why 'B' ?).
You now start with the highest index and proceed to zero - good!
You also reversed the two segments in the sum - also good!

Let me hint you:
You can include the carry as argument to the function; in this way you can handle it immediately and avoid the extra function.
In my solution also the group size (here: 3) is included in the function call.

To pad with zeros you can do:
str(x).rjust(3, '0')  # here x is an integer < 1000

# example:
>>> str(4).rjust(3, '0')
'004'


Was This Post Helpful? 0
  • +
  • -

#6 Metal488   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 8
  • Joined: 15-September 18

Re: How to add/multiply long integers recursively with lists

Posted 16 September 2018 - 01:42 PM

I named it with a B for backwards because I thought the other add function I posted was going forwards, but when I added some print statements to see what order they were going in I got the same results for both Frecursive_sum and Brecursive_sum

I did manage to combine the add function and the carryout function though:
def Brecursive_sum(l1, l2, idx, ND, carryout = 0):
    if idx >= 0:
        #print(int(l1[idx]) + int(l2[idx]))
        n = int(l1[idx]) + int(l2[idx]) + carryout
        nStr = str(n)
        
        if(len(nStr) > ND):
            carryout = int(nStr[0])
            n = int(nStr[1:])
        else:
            carryout=0
        
        return Brecursive_sum(l1, l2, idx - 1, ND, carryout) + [n]
    else:
        return []



This gives me the results I expected. This function seems to work as long as I run the lists through eqSize first (if they are different sizes), then AZlist afterwards
Was This Post Helpful? 1
  • +
  • -

#7 DK3250   User is offline

  • Pythonian
  • member icon

Reputation: 463
  • View blog
  • Posts: 1,468
  • Joined: 27-December 13

Re: How to add/multiply long integers recursively with lists

Posted 16 September 2018 - 01:58 PM

Remarkable, - really good! :bigsmile:

The two helper functions 'eqSize' and 'AZlist' are both recursive, this add to the complexity.

You may not be familiar with list comprehensions, but they are not too difficult.
You might benefit from this:
[str(x).rjust(grp, '0') for x in recursive_sum(l1, l2)]  # grp is a variable, you use '3'

I think this code is equivalent to your AZlist function.

In my version all other arguments to 'recursive_sum()' has default values, thus this short call.

Oh, - upvotes accepted..
Was This Post Helpful? 1
  • +
  • -

#8 DK3250   User is offline

  • Pythonian
  • member icon

Reputation: 463
  • View blog
  • Posts: 1,468
  • Joined: 27-December 13

Re: How to add/multiply long integers recursively with lists

Posted 16 September 2018 - 02:09 PM

What about this:
def Brecursive_sum(l1, l2, idx, ND, carryout = 0):
    if idx >= 0:
        n = int(l1[idx]) + int(l2[idx]) + carryout
        nStr = str(n)
        
        if(len(nStr) > ND):
            carryout = int(nStr[0])
            n = int(nStr[1:])
        else:
            carryout=0
        
        return Brecursive_sum(l1, l2, idx - 1, ND, carryout) + [str(n).rjust(ND, '0')]
    else:
        return []

This will make the AZlist (and my list comprehension) obsolete..

This post has been edited by DK3250: 16 September 2018 - 02:13 PM

Was This Post Helpful? 1
  • +
  • -

#9 Metal488   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 8
  • Joined: 15-September 18

Re: How to add/multiply long integers recursively with lists

Posted 26 September 2018 - 06:47 AM

It worked great. Thank you so much for all your help.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1