| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 812.1 | Same Answer | TALLIS::STEELY | | Thu Jan 07 1988 09:17 | 11 |
| I happened to have been playing around with a prime number program a while
back.
Starting with 2 as the first prime number I also get 203,280,221 prime numbers
less than 2^32. I stopped my program with the first prime greater than
2^32, which is 2^32+15.
My program is written in Ada. I ran it last night on a VAXstation 2000 running
VMS V4.6 and it took 15 hours 22 minutes and 18.91 seconds of CPU time.
Simon
|
| 812.2 | Same ballpark, that's reassuring | SMURF::JMARTIN | Joseph A. Martin, ULTRIX kernel | Mon Jan 11 1988 11:18 | 4 |
| Thanks, Simon. Using C (compiled with vcc) and a little assembly (for
zeroing out the sieve), it took my microVAX II and ULTRIX v2.2 9.48 hours
of CPU time and 9.75 of wall clock time.
--Joe
|
| 812.3 | Algorithm details? | JON::MORONEY | Redundancy example: Criminal lawyer. | Tue Jan 12 1988 17:40 | 5 |
| re .*:
Did you use a 2^32 bit sieve for this or did you use some method to fold it?
-Mike
|
| 812.4 | My approach | TALLIS::STEELY | | Tue Jan 12 1988 21:28 | 17 |
| Here's a real short story of what I believe my program is doing. I
haven't looked at in quite a while.
My program uses either an 8K or 16K sieve of longwords. For each
sieve-writing pass, I write the pass-number into the longwords which are
multiples of primes. After marking all multiples of primes, the sieve is
examined and all entries which don't match the present pass are primes.
I also have a steps array that is modulo 2*3*5*7*11*13 that controls
the examination of entries in the sieve to only numbers that aren't
already divisible by one of those primes.
Since Joe has reported a faster program I'm going to spend some time
one of these weekends and look at unrolling my sieve writing loop
and see if I can get an Ada program to match his times.
Simon
|
| 812.5 | Before you unroll... | SMURF::JMARTIN | Joseph A. Martin, ULTRIX kernel | Wed Jan 13 1988 10:21 | 12 |
| My sieve is folded into 4-million-byte sections each representing 8 million
consecutive odd integers. The table of times (in seconds) seems to
indicate that memory access dominates. Put another way, I'm not using
cache or write buffers to any advantage. Consequently, I was considering
getting my sieve sections down under the cache size for an 8650 or 8700
to see if that helps.
35096.5 real 33757.8 user 388.9 sys eldrad (microVAX II)
12853.2 real 12722.0 user 32.9 sys hollow (VAX 8650)
34089.0 real 34071.5 user 10.9 sys halted (VAX 8300)
--Joe
|
| 812.6 | send me a copy | DPDMAI::FRAMELI | | Fri Apr 01 1988 06:33 | 7 |
| i would be very interested in getting a copy of the benchmarks you
have for computing prime numbers.
dale
frameli.dale @dpd
|