Ben Wendt's blog

A skip list is similar to a linked list, but it is always sorted and maintains multiple pointers. The multiple pointers allow fast traversal of the list so that you can quickly look for elements, essentially performing a binary search on the data.

more

Fermat’s Last Theorem States that there are no non-trivial integer solutions solutions to the equation:

x^{n} + y^{n} = z^{n}, n > 2

This theorem went unproven for centuries, and was proven to be true in 1995 by Andrew Wiles. The Treehouse of Horror VI episode of the Simpsons aired the same year. People with a keen interest in humourous background gags could have done a freeze frame and seen the following (source:

The gag here is that if you punched in

1782¹² + 1841¹²

to a pocket calculator, you would get the same answer as if you punched in:

1922¹²

So this equation would seem to be true, but it’s not. It’s just really close, and the reason you see the same number is due to floating point rounding. I.e. it’s not actually true, but it’s close enough to fool the calculators of the day. Sadly I don’t know who found this near-solution to give credit. I remember hearing a commentary by David X. Cohen, who is a mathematician and writer for The Simpsons and Futurama, mentioned some details about this.

Finding near-solutions to FLT is actually quite easy though. You just have to do a brute force search and you can output whatever numbers you find that are close enough to what you are looking for. Just define your ranges of exponents and bases and loop through, looking for solutions that match a certain threshold. Here’s an example written in C#:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {

            string lookingFor = ".00000000";
            for (double exponent = 11; exponent < 15; exponent++)
            {

                for (double doing = 701; doing < 20002; doing++)
                {

                    double result = Math.Pow(doing, exponent);

                    for (double x = Math.Floor(doing * 0.5); x < Math.Floor(doing * .95); x++)
                    {
                        double y1 = Math.Ceiling(Math.Pow(result - Math.Pow(x, exponent), 1 / exponent));
                        double y2 = Math.Floor(Math.Pow(result - Math.Pow(x, exponent), 1 / exponent));

                        // check the high number
                        double sum = Math.Pow(Math.Pow(y1, exponent) + Math.Pow(x, exponent), 1 / exponent);
                        string sumstring = sum.ToString();
                        if (sumstring.IndexOf(lookingFor) > -1)
                        {
                            Console.WriteLine(doing + "^" + exponent + " = " + x + "^" + exponent + " + " + y1 + "^" + exponent + ", actually: " + sumstring);
                        }

                        // then the low.
                        sum = Math.Pow(Math.Pow(y2, exponent) + Math.Pow(x, exponent), 1 / exponent);
                        sumstring = sum.ToString();
                        if (sumstring.IndexOf(lookingFor) > -1)
                        {
                            Console.WriteLine(doing + "^" + exponent + " = " + x + "^" + exponent + " + " + y2 + "^" + exponent + ", actually: " + sumstring);
                        }
                    }
                }
            }

            Console.ReadLine();
        }
    }
}

And doing this you can find some interesting near-solutions like:

[

19639^{11} = 15797^{11} + 19469^{11}, actually: 19639.0000000074

]

[

4472^{12} = 3987^{12} + 4365^{12}, actually: 4472.00000000706

]

[

14051^{13} = 11184^{13} + 13994^{13}, actually: 14051.0000000076

]

Memoization is a programming technique where you save expensive computations in memory to speed up function execution time. E.g. If you were writing a CMS and you wanted a getSignedInUserName() method, you wouldn’t want to make two database calls to show the user name at the top and bottom of the page, so you’d save it in memory for use later.

My canonical example of the speed increase you can get from this technique is with a Fibonacci calculator. Here is a non-optimized version:

fib = function(n)
    if n==1 or n==0 then
        return 1
    else
        return fib(n-1)+fib(n-2)
    end
end

print(fib(40))

This takes about 22 seconds to run on my development machine. Here’s a rewritten calculator that uses memoization:

results = {}
fib = function(n)
    if results[n] then
        return results[n]
    else
        if n==1 or n==0 then
            result = 1
        else
            result = fib(n-1)+fib(n-2)
        end
        results[n] = result
        return result
    end
end

print(fib(40))

This finishes in well under one second. In fact, calling the memoized function with fib(100) finishes in under a second too. The real benefit here is that you aren’t clogging up your call stack with hundreds of thousands of calls, each waiting on other calls. By having previous results on hand, the function can easily move on to the next step.