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;
{ 19 } Comments
A great example of an interesting technique.
The question that pops up, however, is - how slow will this run? After all, Filter will get longer with each found prime.
Great example, really interesting.
Your project Euler link is bad.
Primoz,
Slower performance with increasing prime values is a characteristic of the Sieve of Eratosthenes. Indeed, it’s characteristic of every algorithm for finding primes I’ve ever seen, although the Sieve is one of the slowest. I chose it because it’s very simple to explain and plenty fast enough for the job at hand. I do not think this implementation will be significantly different in speed than other implementations of the same algorithm, though.
Leonel,
Thanks; fixed.
Very interesting example:-)
One, maybe stupid, question: how is the "TPredicate" generic class defined?
Pawel,
TPredicate is part of the RTL. The definition is:
TPredicate<T> = reference to function (Arg1: T): Boolean;
Interesting, although (yet again) outside of a classroom environment I’m not sure I see the value of using this approach over the alternatives other than as an intellectual curiosity.
And I might cheekily point out that you didn’t "solve the problem". You are only required to identify the largest prime factor, not ALL prime factors.
In the classroom you’d be down marked for not having read/answered the question properly.
I think you’d probably also be marked down for enumerating all the primes up to to your Composite, when you need only consider primes to/including the square root - there can’t be any higher factors than that, surely?
PS - A performance comparison /would/ be interesting.
My quick and crude effort (D7, so no anon methods or currying) arrives at the correct answer in 22 seconds on a 2.2GHz E4500 Core Duo)
Doh! Stupid error - right answer, but via a *very* scenic route. Now getting there in under 300 msecs!
Jolyon, don’t mistake showing my work for answering the question incorrectly.
Also, you misread the code; I don’t evaluate all primes up to the composite, or even the square root. I only evaluate primes up to and including the correct answer.
I didn’t time the execution, but it’s certainly less than 1/2 sec. on a similar machine. I suspect the compiled code is pretty similar, with some overhead for the method call.
Assuming I read the code correctly, MakeFilter() essentially creates an expanding recursive(nested) series of calls of the FIsPrime anon method, essentially writing an extended longhand version of the code if then else if then … ad inifinitum within the anon method.
Obviously, for larger starting values this means the anon method will become large. What are the practical limits for htis type of usage of anon methods?
Cheers,
Raymond.
@Craig: And what if the composite is a prime number? You should still stop at the square root.
Raymond, I doubt there’s any limit beyond the stack size. That said, for 1/2 of the numbers tested (the evens) the method exits immediately, and so on, so you rarely get very deep. Most functional languages will do an optimization called tail recursion which will allow calls on the last line of a method without blowing up the stack, removing this limitation.
Primoz, I know that the composite is non-prime per the problem statement. In the general sense, I’d agree, but I wasn’t trying to solve a general problem (and, hence, the hard-coded value). Rather, I was trying to solve problem 3 of Project Euler.
Thanks Craig.
You know, with all the confusion of generics, and the examples being posted of how to use them being somewhat artificial, what we really need is an implementation of something a little more concrete/real world for us all to sink our teeth into and appreciate generics with.
Something like a MapReduce would be cool!
Raymond.
Oops, quite right Craig - I didn’t spot the mutation of Composite. I guess I find it easier to read code whose expression more closely resembles it’s purpose:
function LargestPrimeFactor(const aComposite: Int64): Int64;
var
i: Integer;
primes: TEratosthenesSieve;
begin
primes := TEratosthenesSieve.CreatePrimesTo(Round(Sqrt(aComposite + 0.0)));
try
for i := Pred(primes.Count) downto 0 do
if (aComposite mod primes[i]) = 0 then
begin
result := primes[i];
BREAK;
end;
finally
primes.Free;
end;
end;
(apologies for the literals-gymnastics required to co-erce an Extended value from an Int64 param - is that fixed in Delphi 2009 I wonder?)
i.e. the algorithm is - get the primes that the answer could possibly be, then find the largest one that is the answer. The code describes the algorithm, I don’t have to deduce it.
Funny thing - I thought these new language features were supposed to enable us to more clearly express intent, not unwittingly obfuscate it.
Isn’t there also a hidden cost in an enumerator based approach?
With my TEratosthenesSieve, if I have a number of operations that involve a certain sequence of primes, I only need to calculate that sequence once. With an enumerator, won’t I be re-calculating the primes over and over again (every separate time that I enumerate)?
An enumerator approach would perhaps be useful when you don’t know in advance how many primes you are going to need, but even then, a non-enumerating sieve implementation could easily be extended to calculate primes on demand.
Which rather begs the question, what benefit does an enumerating approach really deliver?
Apart from providing a hook off of which to hang some new language features, I mean.
And if such questionable uses are what the language features are useful for, what use are those features, really?
I’m not saying that those features don’t have practical uses, only suggesting that such examples don’t actually help shed any light on what those uses are. And concrete, practical examples do seem rather hard to come by for some reason.
Jolyon, if you’re seriously interested in learning why it’s worthwhile to bother with functional programming styles, I recommend reading the writings of John Backus, starting with his Turing award address.
Raymond, I’ll show something along those lines when I get the chance.
Great example, thanks.
When Composite = 12 (2*2*4) cycle should be endless.
Thank you for very curious example.
One more interesting thing to mention is that actually it’s neither the Sieve of Eratosthenes, nor the sieve at all. Here’s the fine paper explaining why, with examples in Haskell:
http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
"A much beloved and widely used example showing the elegance and simplicity of lazy functional programming represents itself as “The Sieve of Eratosthenes”. This paper shows that this example is not the sieve, and presents an implementation that actually is."
Anyway your example is great.
Weird. Despite having read a lot of Haskell tutorials, I never knew this was a "common" example!
{ 3 } Trackbacks
[...] the comments to another post on the subject of Delphi 2009 generics, Raymond asked for an implementation of MapReduce. I thought about how I might demonstrate that in the context of generics, and decided that [...]
[...] to do in code. But recall that my purpose in writing this series was to answer commentor Raymond’s request for "something like MapReduce." So when you read this post and wonder why I’ve chosen such a roundabout method of doing [...]
[...] Craig Stuntz’s Weblog: An Enumeration of Prime Numbers with Anonymous Methods [...]
Post a Comment