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

Well, this is not efficient. It states that it implements the sieve of 
Eratosthenes, but it uses division... A smalltalk equivalent with 
generators would look like this (according to my minimal lisp knowledge):

primeGenerator := Generator on: [ :yield |
 	| primes i |
 	yield value: 2.
 	primes := OrderedCollection with: 2.
 	i := 3.
 	[
 		(primes noneSatisfy: [ :prime | i \\ prime = 0 ])
 			ifTrue: [
 				primes add: i.
 				yield value: i ].
 		i := i + 2.
 		true ] whileTrue ].

There are 9592 primes that are smaller than 100000.

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

Compare this with a real sieve (which doesn't use division at all):

[ Integer primesUpTo: 100000 do: #yourself ] timeToRun "===> 13"

1000x faster.


Levente

>
> Probably inspiring in the context of this thread.
> Bye
> Enrico
>
> On Wed, Feb 10, 2010 at 8:16 AM, Levente Uzonyi <leves at elte.hu> wrote:
>
>> On Tue, 9 Feb 2010, Andreas Raab wrote:
>>
>>  Colin Putney wrote:
>>>
>>>> Also, Stephen Pair posted an implementation here in December:
>>>> http://n4.nabble.com/ANN-CoroutineReadStream-tt963004.html#a963004
>>>>
>>>
>>> Brilliant! That's the ticket! Once I got down the right path it's even
>>> simpler than that. I put a version of Generator into the inbox for people to
>>> play with and give feedback. With 5 methods total you get to do fun stuff
>>> like:
>>>
>>> | gen max |
>>> max := 10000000.
>>> gen := Generator on:[:yield| Integer primesUpTo: max do: yield].
>>> 'Computing primes' displayProgressAt: Sensor cursorPoint
>>>        from: 1 to: max during:[:bar| | prime |
>>>                [prime := gen next] whileNotNil:[bar value: prime].
>>>        ].
>>>
>>> I think we should add support for Generators. They are so incredibly
>>> useful where you have complex operations that you don't want to spend the
>>> upfront effort on to compute everything (like primes) before you can do some
>>> work with the results.
>>>
>>
>> I wonder how can you use generators to generate primes efficiently _and_ on
>> the fly.
>>
>>
>> Levente
>>
>>
>>> Cheers,
>>>  - Andreas
>>>
>>>
>>>
>>
>
>
> -- 
> Enrico Spinielli
> "Do Androids dream of electric sheep?"? Philip K. Dick
> "Hear and forget; see and remember;do and understand."?Mitchel Resnick
>