In this post, I am going to demonstrate a programming technique which cannot be done without anonymous methods (or lambda expressions). I’ll throw in some generics for fun. First, though, I need to describe the problem I’m solving.
I want to solve problem three of Project Euler. Project Euler is a web site which poses a series of programming problems intended to teach you mathematical concepts. Here is problem three:
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
In order to compute prime factors, it helps to have a method to return a list of primes. A very simple algorithm to do this is called the Sieve of Eratosthenes. If you don’t already know this algorithm well enough to implement it yourself, then please read the Wikipedia article I just linked before continuing. The rest of this post will make very little sense unless you understand the Sieve.
I’m going to make a minor change to the algorithm described in the article. In that version, you begin by "writing a list of numbers from 2 to the largest number, say n, you want to test for primality." That won’t work for me, since I don’t know the largest number I need to test for primality. I could guess, but I might be wrong, and, in any event, it seems inelegant.
So I’m going to take a different approach. Whenever I have a need for a sequence of something, say, prime numbers, I think of enumerations. It’s common to see enumerations over a fixed list, like strings in a TStringList, but they work just as well for infinite lists. So I’m going to write an enumerator which returns prime numbers in ascending order.
The basic outline of the algorithm is this:
- Start with the lowest prime number.
- Increment the current prime number.
- Test it with a function which returns false if any of the previous prime numbers are factors of the number tested, true otherwise.
- Repeat steps 2 and 3 until a new prime is found.
Obviously, the heart of the algorithm is the function in step 3. To solve this problem without anonymous methods, I would need to maintain a list of the primes returned previously, and test each one in sequence. That would work fine, but I am going to demonstrate a different approach.
Since I happen to know that 2 is prime, I’m going to start with a function which returns true. So in step 1 I’ll begin with 1, not a prime number, but the "uninitialized" start of the enumeration. Note that the value 1 will never be returned by the enumeration. In step 2, I’ll increment it to 2. In step 3, I’ll test it with my function, which, at this point, returns the constant true. So far, so good, since 2 is prime.
Now I need to change the function to one which excludes products of 2, the first returned prime. That way, when we get to 4, it will be rejected by the function. In order to do this, I’m going to dynamically create a new function and substitute it for the original function which always returned true.
OK, enough chat. Let’s look at some code. First, here is the interface for the enumerator:
TPrimeNumberEnumerator = class
private
FCurrent: integer;
FIsPrime: TPredicate<integer>;
function MakeFilter(CurrentPredicate: TPredicate<integer>; CurrentPrime: integer): TPredicate<integer>;
public
constructor Create;
function GetCurrent: Integer;
function MoveNext: boolean;
procedure Reset;
property Current: integer read GetCurrent;
end;
The public portion of the interface is just an implementation of the enumerator pattern in Delphi, plus the constructor, which simply calls Reset. FCurrent will hold the last prime number returned, or 1 if no primes have been returned yet. FIsPrime is a reference to a function which returns false if any of the previously returned returned primes are even factors of the integer argument passed, and true otherwise. TPredicate<integer> means a function which returns a Boolean with a single, integer argument. GetCurrent just returns FCurrent. First, let’s look at Reset, which gets everything ready.
procedure TPrimeNumberEnumerator.Reset;
begin
FCurrent := 1;
FIsPrime := function(AValue: integer): boolean
begin
Result := True;
end;
end;
FCurrent is initialized to the value below the first value returned, as with many enumerator implementations. FIsPrime, at this point, ignores its argument, and simply returns true. I used an anonymous function here for consistency with the rest of the code, but a non-anonymous function could have been used in this part. Again, since I know that 3 is prime, this trivial function is good enough for this specific case, although we’ll need something better soon!
The heart of the enumerator is in MoveNext and MakeFilter. Here’s MoveNext:
function TPrimeNumberEnumerator.MoveNext: boolean;
begin
Inc(FCurrent);
while not FIsPrime(FCurrent) do Inc(FCurrent);
FIsPrime := MakeFilter(FIsPrime, FCurrent);
Result := true;
end;
That’s just the algorithm I described above. Increment FCurrent, then test this value for primality. Keep incrementing until we find a new prime. Return True, since there’s always another prime.
Importantly, however, when a prime is found I modify the predicate FIsPrime in such a way that it excludes products of this prime. That’s the Sieve of Eratosthenes. Let’s look at how this is done:
function TPrimeNumberEnumerator.MakeFilter(
CurrentPredicate: TPredicate<integer>;
CurrentPrime: integer): TPredicate<integer>;
begin
Result := function(AValue: integer): boolean
begin
Result := CurrentPredicate(AValue) and ((AValue mod CurrentPrime) <> 0);
end;
end;
MakeFilter takes the function it was passed plus a new prime number and returns a new function, which returns false if the passed function, CurrentPredicate, returns false or the integer argument, AValue, can be evenly divided by the prime number passed to MakeFilter. The new function returns true, otherwise. Note that the function is "capturing" both the original function, CurrentPredicate, and CurrentPrime, both of which are arguments to MakeFilter, but not to the function returned.
Since I always pass FIsPrime as the CurrentPredicate argument, each time I call MakeFilter I’m enhancing FIsPrime to exclude more non-prime numbers.
In effect, I’m creating a new function which has only one argument, AValue, but incorporates two additional arguments, CurrentPredicate and CurrentPrime. The difference is that CurrentPredicate and CurrentPrime are captured from the creating method and hence fixed at the time the function is created, whereas AValue will be specified at the time the function is executed. This is a technique called currying, and it’s quite common in functional programming. You cannot do currying in the general sense without anonymous methods or lambda expressions. So this is a new programming technique available in Delphi 2009.
Having done all this, I need to be able to get an instance of my enumerator:
TPrimes = class
public
function GetEnumerator: TPrimeNumberEnumerator;
end;
And now I can solve the original problem:
procedure TForm4.btnGoClick(Sender: TObject);
var
Current: integer;
Primes: TPrimes;
Composite: Int64;
begin
Composite := 600851475143;
lboResults.Items.Clear;
Primes := TPrimes.Create;
try
for Current in Primes do begin
if Composite mod Current = 0 then begin
Composite := Composite div Current;
lboResults.Items.Add(IntToStr(Current));
if Composite = 1 then break;
end;
end;
finally
Primes.Free;
end;
end;
Share This | Email this page to a friend