Sieve of Eratosthenes
Ramon Leon
ramon.leon at allresnet.com
Mon Oct 9 21:21:46 UTC 2006
> -----Original Message-----
> From: squeak-dev-bounces at lists.squeakfoundation.org
> [mailto:squeak-dev-bounces at lists.squeakfoundation.org] On
> Behalf Of Davide Varvello
> Sent: Monday, October 09, 2006 1:53 PM
> To: The general-purpose Squeak developers list
> Subject: Sieve of Eratosthenes
>
> Hi All,
> I did some performance tests comparing java and squeak. The
> java code is this:
> public class GeneratePrimes {
> public static double generate(int n) {
> long start = System.currentTimeMillis();
> boolean sieve[] = new boolean[n];
> Arrays.fill(sieve, true);
> sieve[0] = false;
> sieve[1] = false;
> for (int i = 2; i < n; i++) {
> if (sieve[i]) {
> for (int j = 2 * i; j < n; j += i) {
> sieve[j] = false;
> }
> }
> }
>
> return (System.currentTimeMillis() - start);
> }
>
> The Squeak one is:
>
> runOn: aNumber
> | sieve |
>
> sieve := Array new: aNumber withAll: true.
> sieve at: 1 put: false.
>
> (2 to: aNumber) do: [:i | (sieve at: i) ifTrue: [(i to:
> aNumber by: i) do: [:k | sieve at: k put: false] ]
>
> The Squeak code is better (of course) but on a number of
> 1000000 Java spends 94 msec instead Squeak 2650!
> Am I using the right approach or should I change something in
> my squeak code to make it perform better (but preserving clearness)?
Here's my implementation, it's a little faster, but not much.
Integer>>sieveOfEratosthenes
"generates primes up to self, educational algorithm, not for
production use"
| primes |
primes := ByteArray new: self.
2 to: self do: [:each |
(primes at: each) = 0 ifTrue: [each + each to: self
by: each do: [:notPrime |
primes at: notPrime put:
1]]].
^(2 to: self) select: [:each | (primes at: each) = 0]
More information about the Squeak-dev
mailing list
|