S. Ron Oliver
Sat, 18 Nov 2000 09:32:15 -0700
At 05:56 PM 11/17/00 -0800, rajani kanth wrote:
>I need some reference for the "SIEVE OF ERATOTHENES"
>FOR GENERATING PRIME NUMBERS IN ADA.
>I will be thankful to you if you could suggest me
>someting reffered to it.
Well, I've searched through all my directories readily available to me and
cannot find my solution. I know I wrote one many years ago.
It really is very simple to write - so simple I did not include it in my
Ada95 Test Suite, as it did not seem to offer anything of interest.
You could probably implement it yourself in less time than you can find,
retrieve and understand someone else's solution.
The main limitation is that you can't get very many primes, even if you use
"double integer", or whatever it is called.
Many many years ago, while I was a student at Morningside College, I was
inspired by a visiting lecturer from the University of Nebraska who
reported on research he was doing there to find primes on a large IBM
mainframe. At Morningside we only had a small IBM 1130. The technique the
lecturer described was to treat all of memory as 1 long string of
bits. Each bit represented an odd number. Initialize all bits to 0 (or 1)
then starting with the 1st bit (representing 3) reset every 3rd bit to be 1
(or 0). Next find the next 0 (or 1) bit, and reset every number it divides
to 1 (or 0), and so on, until you have reached the first remaining 0 bit at
a location higher than half your total memory space. Every 0 (or 1) bit
now in memory represents a prime.
So what? What do you do with the "0" bits? We were using IBM's FORTRAN II
with Commercial Subroutines to do most of our development. The Commercial
Subroutines library had a nice set of routines that made it possible to do
arithmetic on numeric character strings, which made it possible to deal
with integer numbers much larger than 32767. With this it was fairly easy
to use the Sieve to generate numeric character strings for enough primes to
fill up a removable disk pack (a WHOPPING 2.5 Kilobytes!).
When I did that I think that was the first time I started to worry that I
was becoming what we now refer to as a "Computer Cowboy"! :) (Or was it
the time I wrote the APL program to compute how much nuclear energy there
was (via fusion) in a pencil? :)
Just thought I'd pass along some interesting historical trivia.
S. Ron Oliver, semi-retired professor of Computer Science and Computer
Tire of sucky software! ? Check out www.caressCorp.com and follow the
links to software sucks and The Oliver Academy.