What's wrong with this Python implementation of an addition algorithm?

Question

I've started to follow Stanford's CS161 on Coursera, "an online course on Algorithms and Data Structures."

I've looked up to find grade-school algorithms around integer arithmetic.

I have the addition algorithm in pseudo-code and was interest in implementing it in Python 2.7 (accordingly with MIT standards).

I've analyzed my implementation and think it's almost correct but the Python interpreter provided some feedback possibly on uninitialized lists and variables.

Note that I'm not fully proficient in Python and there may be some obvious syntactic mistakes due to a lack of knowledge in basic data structures and code structuring.

I have a few questions on the code below:

def add(a,b):
    i = 0
    carry = 0
    x[i] = [None]*N
    y[i] = [None]*N
    while x[i] > 0 and y[i] > 0:
        x[i], y[i] = a%10, b%10
        a , b = a/pow(10,i+1), b/pow(10,i+1)
        N += i
    for i in range(N):
        x[i] = x[N-i]
        y[i] = y[N-i]
        r[i] = (x[i] + y[i] + carry)%10
        carry = (x[i] + y[i] + carry)/10
    r[N] = carry
    return r  

Description of the algorithm:

The add() function takes two N-digit integers a and b as input and returns an integer with N or N+1 digits corresponding to the sum of a and b.

It first breaks up a and b into lists of size N holding and storing the N digits of a (respectively b) by extracting each digit from the least powered digit to the digit with the largest power of 10.

It then replaces all x[i] with x[N-i] (resp. y[i] with y[N-i]) and then computes x[i]+y[i] by taking care of the addition's carry at each iteration.

The carry dynamically increments by value. when the for loop ends, we assign the latest digit r[N] of the sum as the value of the carry (>=0).

Questions:

1. Is it a good thing to initialize the lists x[i] and y[i] by assigning its elements' value as [None] N times ?
2. With x[i] and y[i] initialized as such, should the while loop works again as my conditions are on x[i] and y[i]?
3. How to return an entire list namely the list r[N] ? Should we type return r[N] or just return r ?

Other useful contributions and comments are welcome.

Answer 1

1. Yes, that is fine, depending on the context. You could potentially do the nicer: x = [None for _ in xrange(N)], but the performance is very similar and this is unlikely to be important - readability is what matters.
2. I would do x[i] is None to see whether the value is none, if 0 was a legitimate value. Otherwise, I'd just do x[i] which checks if i is not None nor 0 or False.
3. return r

Look at the following code. I fixed add(), including out of bound indexes, and algorithm problems. and then implemented addSimplified() which does the same without the additional helper arrays.

def add(a, b):

    N = max(len(str(a)), len(str(b)))
    carry = 0

    x = [None] * N
    y = [None] * N
    r = [None] * (N + 1)

    for i in xrange(N):
        x[i], y[i] = a % 10, b % 10
        a, b = a / 10, b / 10

    for i in xrange(N):
        r[i] = (x[i] + y[i] + carry) % 10
        carry = (x[i] + y[i] + carry) / 10
    r[N] = carry

    return r


def addSimplified(a, b):

    N = max(len(str(a)), len(str(b))) + 1
    carry = 0

    r = [0] * N

    for i in xrange(N):
        step = (a / pow(10, i) % 10)  + (b / pow(10, i) % 10) + carry
        r[i] = step % 10
        carry = step / 10

    return r

print add(100, 20), addSimplified(100, 20)
print add(166, 66), addSimplified(166, 66)
print add(1920606,  9500666), addSimplified(1920606,  9500666)