The only way to make sure you really understand a mathematical operation is to devise and implement an algorithm that carries it out for all cases.

This Easter (2007) I wrote in python an unlimited precision integer arithmetic engine that would do addition, subtraction, multiplication and division. The first three were easy. The last one was a nightmare.

I broke each number into a number of blocks of digits (groups of three as it happens, since I knew python's built in limited precision arithmetic would happily handle numbers up to a million), and defined the 'size' of a number as being how many blocks it took. (So 1,001 is size 2 while 0 is size 1 and 999,999,999 is size 3). So we could say that number, N has a size of Z. And that T is the average time taken to calculate an operation for two numbers of size Z.

Addition: T = O(Z)

Subtraction: T = O(Z)
While, potentially, a carry operation could travel the length of a number, eg 1000000 - 1, this does not repeatedly happen, so 100000000 - 1001 would not need to do a long carry for the second one.

Multiplication: T = O(Z^2)

Division: Dividing two numbers of size Z requires Z steps. The Yth step requires: a size 2 division, a size 2 addition, a size Y addition (x2), a size Y*Z multiplication (x2), a size Z subtraction. Therefore for Division, T = O(Z^3)

To keep everything precise and still accurate, a 5th operation is needed, to complete division, which is Remainder. This is discovered as a by product of Division.

I've looked at the Wikipedia entry for Arbitary Precision Arithmetic and the computational complexity of mathematical operations. It considers division to be O(Z^2). I don't know whether this is influenced by the fact that there exist alternative algorithms for multiplication that are O(n (log n) (log log n)), rather O(Z^2). When I get time, I'd love to pick through the source code of GMP and see what they are actually doing. (Note: while google offers a free calculator, the GMP free calculator is better.)

I was pleased to finally get working code that could divide arbitrarily long positive integers correctly. I believe that negative numbers, fractions, finite decimals and complex numbers could all be built up on top of this base engine, but that's a project for another vacation.

Here is the result of one test I carried out. If you define S(N) as the square of S(N-1), and S(0) as 2, here is the value of S(19)