Exercise: long integer multiplication

Here’s a little exercise spotted in the magnificent “Coders at Work” book:

Seibel: Do you have favorite interview questions?

Fitzpatrick: One of the ones I’ve given a few times because it was on my AP programming test is given two decimal numbers as a strings of arbitrary length, multiply them. There are a lot of different ways that they could do it. If they’re really good at math—like I’m not—they can find some clever ways to do it really efficiently. Worst case, they can make a class that does just addition repeatedly.

It’s a fun little exercise to try to solve. I’ve done this years ago in Pascal, and was now thinking, how long would it take to do this now, in Python? Of course in Python it’s much easier, like, for example, in Pascal I was fiddling with dynamic memory allocation to store numbers of any length efficiently, in Python I just use strings and lists that can have almost-infinite length. For this exercise to make any sense, I also obviously have to refrain from using long integers.

In a hour or so I had implemented a few variants, one faster, one more readable and one in-between. I won’t get into details, it’s so much more fun to do it yourself!

Advertisements