Coffee Talk: Java, News, Stories and Opinions
BLOG

Leibniz in Java and the Commodore 64: An exercise in optimization

Walker Aldridge
Walker Aldridge
Lairds Computer Services

Modern retro-computing with the C64

Recently I was writing code to examine the relative speeds of various languages (Java, Python and C#). I decided to use a “real” calculation instead of just throwaway code. For this I chose the Leibniz approximation of Pi. There were a few ways to implement it in each language, and I compared and contrasted them.

I like to play with retro computing in general, and the Commodore 64 specifically. Looking at the Python version of Leibniz I wrote, I thought it would be a fun challenge to rewrite it in Commodore BASIC, to see what an 8-bit computer running at 1Mhz could do.

I rewrote the Leibniz algorithm in Commodore BASIC and to no surprise the 40-year-old language and computer were orders-of-magnitude slower. Intriguingly, though, it worked — given a much longer runtime, it came up with the same answer.

The fun part of this was that because BASIC lacks a lot of modern features, I had to rewrite the algorithm to avoid using them. Looking at the code it occurred to me that those same changes to the algorithm would apply in the modern languages too — for example, replace a computationally expensive float operation (exponentiation) with a much cheaper int operation.

The result? A 33% speed increase in the Python version and a 500% speed increase in the Java/C# version.

Here is the original Python code:

def Leibniz(iterations):
    n = 1
    for i in range(2,iterations - 1):
        term = ((-1.0) ** (i - 1.0)) / ((2 * i) - 1.0)
        n = n + term 
    return n*4

Here is the BASIC code that I turned this into, because exponentiation in BASIC is hard:

1000 rem leibniz algo
1010 iter = 1000
1020 n = 1
1030 tt = -n
1040 for i = 2 to iter - 1
1050 term = tt / ((2 * i) - 1)
1060 n = n + term
1070 tt = -tt
1080 next i
1090 x = n
1100 return

And here are the same optimizations to avoid exponentiation added back to Python:

def LeibnizTurbo(iterations):
    n = 1
    topterm = -1.0
    for i in range(2,iterations - 1):
        bottomterm = i << 1  #Fast bitwise x2 whilst i still int
        term = topterm / (bottomterm - 1.0)
        n = n + term 
        topterm = -topterm  #Flip top between 1 and -1 without exponentiation
    return n*4

I write things for fun on the Commodore 64, mostly for just that — fun. In some ways for me, this is going back to the origin, as the Commodore 64 was my first home computer. But sometimes an exercise like this forces you to think in ways that are more resource-efficient than you might otherwise envision. In this case, it led me to devise an optimization that I used to improve the versions written in contemporary languages. So it was both fun, and enlightening.

What more could a developer want?