Reading this blog - The Sieve of Eratosthenes by ravi.bhatnagar - inspired me to do something I've been wanting to do for a very long time, but have never quite managed - go back to my Computer Science roots and write some proper object oriented code, doing an abstract task (i.e. nothing to do with journals, purchase orders, or anything else business-related) in ABAP. Perverse, maybe, but there must be a general purpose programming language hiding in there somewhere, amongst all the select statements and tables, right? So here goes...
As explained in Ravi's blog, the Sieve of Eratosthenes is very simple (in concept) way of generating prime numbers.
- First write out all the whole numbers from 2 upwards (2 is the first prime, so no point in looking at lower numbers).
- The lowest number (initially 2) on the list is a prime, but all of its multiples aren't so cross them off.
- Go back to step 2.
Next time around the loop, 3 is the lowest number, then 5 (4 was previously crossed off as a multiple of 2), then 7 (6 disappeared as a multiple of 2), etc. Try it with a piece of paper and a pencil.
One thing to note about this description - you need to decide up front what is the largest prime you want to find, because you have to write them all out before you start. Ravi's implementation has this problem and I was keen to avoid it. Conceptually, you should start with an infinite list and each time you find a new prime cross off the infinite number of multiples of it. Now "infinity" is a tricky thing to handle in code, especially infinitely sized data structures. The way to avoid it is to use a technique called "lazy evaluation" - only calculate numbers when you are asked for them.
I'm going to start with a class called Counter. This is constructed with a starting value and has a "get" method that gets the next value in sequence.
class Counter definition.
public section.
methods:
constructor importing start type i,
get returning value(r) type i.
private section.
data: value type i.
endclass.
class Counter implementation.
method constructor.
value = start.
endmethod.
method get.
r = value.
value = value + 1.
endmethod.
endclass.
start-of-selection.
data: n type i value 1.
data: c type ref to Counter.
data: p type i.
create object c exporting start = 2.
while n <= 10.
p = c->get( ).
write:/ p.
n = n + 1.
endwhile.
Run this and you should get the numbers 2..11. OK so far. We have a class that generates a list of numbers as long as we like, but only as many as we ask for. Now we need to start crossing off some of those numbers. Let's build a filter:
class Filter definition.
public section.
methods:
constructor importing src type ref to Counter
f type i,
get returning value(r) type i.
private section.
data: filter type i,
source type ref to Counter.
endclass.
class Filter implementation.
method constructor.
super->constructor( ).
me->source = src.
me->filter = f.
endmethod.
method get.
data: n type i.
n = source->get( ).
while n mod filter = 0.
n = source->get( ).
endwhile.
r = n.
endmethod.
endclass.
This takes a Counter object and a number, and only returns values from the Counter stream that are not multiples of that filter number. So, call it like this and we get the odd numbers 3..21.
start-of-selection.
data: n type i value 1.
data: c type ref to Counter.
data: f type ref to Filter.
create object c exporting start = 2.
create object f exporting src = c, f = 2.
while n <= 10.
data: p type i.
p = f->get( ).
write:/ p.
n = n + 1.
endwhile.
We're almost there, but we need a little trick before we can put these pieces together. I'm going to skip that for the moment and present one more class, the sieve class:
class Sieve implementation.
method constructor.
data: c type ref to Counter.
create object c exporting start = 2.
source = c.
endmethod.
method get.
data: n type i.
data: nfilter type ref to Filter.
n = source->get( ).
create object nfilter exporting src = source f = n.
source = nfilter.
r = n.
endmethod.
endclass.
This starts by creating a Counter with start value 2, calling it source. Then each time its "get" method is called it takes the next value from the source and returns that as the next prime. It also builds a filter that takes the current source and filters out all multiples of this new prime, and replaces its source with this new filter. Each time, then we are building a chain of filters, each one removing multiples of new primes as we find them. This only works if the Filter object can filter not just Counters but also other Filters. And this is the trick - inheritance. We achieve that by having both Filter and Counter inherit from a common base class - I call this "Source". I won't repeat the class definitions using inheritance - the complete source to my program is attached.
In summary, a little object orientation, a little inheritance, a little lazy evaluation and you get a nice little prime number generator. I've quite enjoyed this little wander down memory lane, with a twist. I may do it again with another programming problem from my Computer Science past :smile: . Any suggestions? Any thoughts on using ABAP in this way? I still haven't got comfortable using object orientation in the code I write for business applications - somehow it doesn't seem to fit. Maybe if I do some more exercises like this I'll get better at it.
