Swap

In many programming languages, writing the program that swaps the contents of two variables is a little complicated since we need a temporary variable in which to store the intermediate value. For example, in C:

{
    temp = a;
    a    = b;
    b    = temp;
}

Of course, if the variables happen to be of different types then life is even more complicated.

However, in Python (and hence Sage), when we use a variable:

• on the right hand side of an equality sign
• as an argument in a function call

It is the value of the variable that is used. (Note that for lists and other more complex variables, the "value" is to be understood properly and is distinct from the printed value!) As a result, we can do a swap more simply as follows:

a, b = b, a
# now a and b values are interchanged

It is worth noting that the above Python code, is more expensive in terms of time and space than the corresponding C code, but it is easier to read and understand!

Max and Min

One of the common tasks is running through a list and finding the "largest" element of the list. Here the measure of large-ness could be some function other than the standard greater-than or less-than. The sample code is:

cmin = -Infinity
index = 0
for i in range(len(mylist)):
    if mlyist[i] < cmin:
        cmin = mlylist[i]
        index = i
# now cmin is the minimum element of mylist and index is the
# position of that minimum

A convenient function called reduce can be used to make this calculation much simpler:

def mymin(x,y):
    if x < y:
        return x
    else:
        return y
cmin = reduce(mymin, mylist)

The function reduce applies the function (its first argument) to the first pair of elements of mylist and then successively to the result of this function and the next element of the list. For example, the following one-liner gives the sum of the elements in mylist:

reduce(lambda x,y: x+y, mylist)

The built-in Sage functions min and sum are written like this.

The maximum of a list can be found in exactly the same way.

Divide and Conquer

This does not refer the paradigm of the colonial powers who used it to subjugate nations! The idea is that we divide the problem into two smaller problems. An easy application is taking non-negative integer powers of a number:

k=1
while n>0:
    if n%2 == 1:
        k *= x
    n //= 2
    x *= x
# After this k contains the n-th power of x

If you prefer to define a recursive function, you can do it as follows:

def mypow(x,n,k=1):
    if n == 0:
        return k
    else:
        return mypow(x^2, n//2, (x if (n%2==1) else 1)*k )

Note that this takes at most $4\log_2(n)$ calculations to calculate the power as opposed to $n$ steps used by repeated multiplication.

Karatsuba Multiplication

A multiprecision (natural) number can be thought of as a list $[a_0,a_1,\dots,a_n]$ which represents the number $\sum_{k=0}^n a_{k} M^k$ where $M$ is the "base" (the largest possible value of $a_i$). In the simplest case, for example, $[a_0,a_1]$ represents $a_0 + a_1 M$. Naively, one might calculate the product of $[a_0,a_1]$ and $[b_0,b_1]$ as $[a_0*b_0,a_1*b_0+a_0*b_1,a_1*b_1]$. This involves four multiplications and one addition.

It is known that addition can be implemented much faster than multiplication. Hence, it is useful to reduce the number of multiplications. The method is to calculate $c_0=a_0*b_0$ as well as $c_1=(a_0+a_1)*(b_0+b_1)$ as well as $c_2=a_1*b_1$. We then see that the product is also given by $[c_0,c_1-c_0-c_2,c_2]$. In other words, we managed with three multiplications and two additions (subtractions).

This may seem like a small saving $(3/4)$ in such a simple calculation. However, one can iterate this to get a saving of $(3/4)^k$ for multi-precision calculations and thereby get substantial savings of time.

Polynomial Evaluation

A polynomial can be thought of as a list $[a_0,\dots,a_n]$ representing the polynomial $P(T)=\sum_{k=0}^n a_n T^n$. The above Karatsuba technique can also be used for polynomial multiplication. A slightly different optimisation is possible for evaluating polynomials.

dev poleval(coefflist,x,t=0):
    if len(ceofflist) == 0:
        return t
    else:
        return poleval(coefflist[:-1],x,t*x+coefflist[-1])

We have used a number of "tricks" here:

• the index (-1) of a list indicates it's last element
• the range selecter code:[a:b] applied to a list selects the sublist of elements starting from the a-th one to the (b-1)-th one.
• when the range indicater is code:[:-1] it indicates all but the last element.

It is worth calculating the above function by hand on small degree polynomials to see how it works.

Constant Use and Mis-Use

A number of constants are used and hence it is best to store them so as to simplify their use. An example is pi which is stored in Sage. However, it would be strange to do something like the following:

two = 2
def square(x):
    return pow(x,two)

Since 2 is a immediately recognisable constant that is usable without confusion, there is no need to store it!

Similarly, there are many functions which are used so often that we have special notation for them. For example a*b is actually the result of evaluating a function mult(a,b) on the two values. (The reality is substantially more complicated as a result of operator overloading!) It would be odd to keep using the mult function in place of the simpler * notation.

Similarly, there are a number of places were we do not need to define a simple function which is only going to be used in that one place. The functional construct lambda is useful for this. For example, to construct a list of powers of two:

map(lambda n: 2^n, range(10))

All of the re-use ideas are based on two principles to save programmer time:

• do not force a programmer to interrupt herself in mid-thought.
• do not force a programmer to scratch her head or look through fat manuals while trying to read code.

As often, these two principles do come in conflict with each other. The quick-fix solution which is written down without explanation can often lead to months of head-scratching years later!