On Wed, 10 Feb 2010, Randal L. Schwartz wrote:

>>>>>> "Levente" == Levente Uzonyi <leves at elte.hu> writes:
>
> Levente> On Wed, 10 Feb 2010, Enrico Spinielli wrote:
>>> SICP to the rescue
>>> http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#%_sec_3.5.2
>
> Levente> Well, this is not efficient. It states that it implements the sieve of
> Levente> Eratosthenes, but it uses division... A smalltalk equivalent with generators
> Levente> would look like this (according to my minimal lisp knowledge):
>
> What you really want is a set of generators that produce
> 2, 4, 6, 8 ...
> 3, 6, 9, 12 ...
> 5, 10, 15, 20, ...
>
> and could efficiently "merge" them in order, so that you could "subtract" that
> merge from a generator counting 1..n.  If anything made it past that subtract,
> it would become a new sequence generator.

Something like this?

primeGenerator := Generator on: [ :yield |
 	| generators i |
 	generators := OrderedCollection new.
 	i := 2.
 	[
 		(generators noneSatisfy: [ :generator |
 			[ generator lastValue < i ] whileTrue: [
 				generator next ].
 			generator lastValue = i ]) ifTrue: [
 				yield value: i.
 				(generators add: (Generator on: [ :filterYield |
 					| prime k |
 					prime := i.
 					k := prime.
 					[
 						filterYield value: k.
 						k := k + prime.
 						true ] whileTrue ])) next.
 				"#next ensures that prime's value is set to i's value
 				and initializes lastValue" ].
 		i := i + 1.
 		true ] whileTrue ].

[ 1 to: 9592 do: [ :i | primeGenerator next ] ] timeToRun "===> 23982"

Note that Andreas' Generator has to be changed a bit to run this code. I 
added a new instance variable "lastValue" and an accessor for it. I also 
changed #nextPut:'s last line to:
^lastValue := anObject "returns anObject to retrieverContext (i.e., #next)"


Levente

>
> I think I saw this technique in "Higher Order Programming", a book
> about using Perl closures to do some really wicked stuff.
>
> -- 
> Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095
> <merlyn at stonehenge.com> <URL:http://www.stonehenge.com/merlyn/>
> Smalltalk/Perl/Unix consulting, Technical writing, Comedy, etc. etc.
> See http://methodsandmessages.vox.com/ for Smalltalk and Seaside discussion
>