I had to develop an instructor solution to a simple C problem, the calculation of primes using the Sieve of Eratosthenes.
The first challenge in teaching the Sieve of Eratosthenes Beta of Cyrene (who was, according to Wikipedia, called Beta because he produced second-prize winning solutions on several occasions) is twofold:
(1) Getting everybody to spell sieve correctly by teaching the i before e rule, the full form of which is "i before e, except after c, and except for the word weird which in being a legacy of old English and from Anglo-Saxon *wyrd* (a man's soul, his destiny, his *wyrd*) has a legacy spelling." The first part up to the weird part is my late Mom's rule: the weird part, the part about weird and wyrd, is my own discovery.
(2) Getting everybody to spell and pronounce Eratosthenes.
It is IMPORTANT to get everybody to spell sieve and Eratosthenes correctly. This is because spelling errors cause HAVOC in program maintenance and at build time, where the maintainers and the build team often have an aural understanding of keywords.
If some clown has named a variable, and object, or a file with his favorite mis-spelling of a common word, the change breaks or the build crashes.
Returning to C was interesting, for I'd forgot that its bugs are those of assembly. In the following solution I initially declared the sieve array as intSieve[SIEVESIZE - 1]...thinking in Visual Basic and not C.
Because I knew that C programming is consistently more bug-ridden than programming in a truly high-level language, I coded an "inspect" routine to check the sieve upon completion of the requested table of primes for all and only prime numbers.
Imagine my chagrin when in testing certain ranges the inspect routine reported failure. It displayed a message saying that the sieve, which is supposed to contain prime numbers (since to determine primehood you need ONLY to divide by all primes up to one-half the candidate) contained the nonprime number 999!
Looking at the code I realized I was back in the thrilling days of C and yesteryear, for the code did not appear accidentally to assign an index value to a table entry. I realized that I'd been bitten by the fact that in C, it is always possible to assign garbage to a variable in an unpredictable way and that I'd somehow gotten 999 into the LAST entry of the table!
I felt like Woody Harrelson when in Terence Malick's noble film THE THIN RED LINE, Harrelson's character accidentally pulls the pin on his grenade and just before he dies, says, "What a f**kin' recruit error."
But I went immediately to the declaration of the sieve and then to the C standard on the Web. Oops, ok, right, size of the table, not upper bound, got it, I'm ON the mothaf*r boss.
My current praxis in OO languages including VB.Net and C# is to develop objects with an inspect routine that checks a number of assertions. The genesis of this practice is my days with C and before that with assembler, where I realized the need for a level of caution one level above that which is needed with languages that like VB and C# prevent the vision of the memory that C "allows", a "vision" that makes all too clear the von Neumann adjacency of variables that in a TRUE high level language are in a noncontiguous space.
Wow, that hurt. What I mean is that it is an historical accident, the accident of the von Neumann machine, that "variables" are neighbors in a sequential neighborhood less like Mister Rogers and more like that of Eddie Murphy:
This is how we ansah da door in MAH neighborhood, boys and girls:
"WHO DAT!!?"
Which means that inspect and use of the assert() function are critically important in C, and that its supposed "power" is a vice: someday in the far future a fabulist will tell of mad men in a city who called their chains, heaps of pearl.
Now, you should be aware that certain personalities, among them the editor of C Unleashed, Richard Heathfield, don't think I "know" (in the sense of grok, in the sense of being with the program, in the sense of coding right, in the sense of being a regular guy) C. Richard acidulously explained my assisting John Nash with C [1] as an instance of the ape with the typewriter, in fact.
It is true that I have not used C in recent years, and my style tracks old fashioned C book C, Wayne and Garth era Wayne's World C. Nor am I like to return to C full time except as a part-time teacher of C. I do indeed need in this role to get up to speed on recent developments, and truly good practice.
[Richard Heathfield and his team have some good advice in his book, but don't believe everything you read.]
But as a teacher of C I plan to stress its flaws and its pitfalls from my POV (point of view).
A critical theory of computer science demands teachers who are informed less by loyalty to artifacts and more by hatred of the flaws of artifacts: David Gerlenter of Yale is the exception for he has said he dislikes most computers and their software.
The rule is some part-time prof and full time corporate slave who is too overworked to research alternative paradigms and thus filled with a passionate loyalty to a hobby-horse. The class divide in American education visits such wads upon students who can't afford a better school, where the ACM guidelines are more strictly followed, and academic freedom trumps corporate demands.
Anyway, here is the code. Comments and corrections are welcome.
Note: the program is designed to run from the command line using this syntax:
"sieveOfEratosthenes"
where and are the lower and upper bounds of the desired table of primes.
Yes, I named the EXE, sieveOfEratosthenes. May as well practise our spelling of the two words!
Editor's Note: Updated version of this code, and accompanying commentary, posted here [2].
// ***********************************************************************
// * *
// * sieveOfEratosthenes *
// * *
// * *
// * This program shows an example of work that may be considered *
// * excellent in your computer science program. It calculates a range *
// * of prime numbers from a starting point to an ending point, using *
// * the standard "tricks" to save time: *
// * *
// * *
// * * Each prime found can be recorded in the famous "sieve" of *
// * Eratosthenes, and to test primality, we can just divide *
// * candidates by sieve members...until the numbers in the *
// * sieve run out. *
// * *
// * * If the sieve does not contain all prime numbers up to n-2 *
// * where n is the (odd) candidate then starting after m+2, *
// * where m is the last element of the sieve (or 3 when the *
// * sieve is empty), we can divide the candidate by odd numbers *
// * up to and including floor(n/2) (the integer part of the *
// * candidate n divided by 2). *
// * *
// * *
// ***********************************************************************
#include <stdio.h>
#include <string.h>
#include <time.h>
// ***** Constants and macros *******************************************
#define SIEVESIZE (1000)
#define SYNTAX_REMINDER \
("sieveOfEratosthenes <start> <finish> [<sieveLimit>]")
#define IS_FACTOR( n, m ) ( (n) % (m) == 0 )
#define MAX( x, y ) ( (x) > (y) ? (x) : (y) )
// ***** Tools ***********************************************************
// -----------------------------------------------------------------------
// Convert character to its numeric form
//
//
int char2Number( char chrInChar )
{
int intInCharValue = ( int )chrInChar;
int intZeroValue = ( int )'0';
if ( intInCharValue < intZeroValue
||
intInCharValue > ( int )'9' ) return -1;
return intInCharValue - intZeroValue;
}
// -----------------------------------------------------------------------
// Convert a string containing an unsigned number to its value: return
// true (-1) on success or false (0) on failure
//
//
// This function returns false when the number's value overflows, but in
// this case, its reference parameter intValue is still returned. In
// this case the value will be negative.
//
//
int string2Number( char *strInstring, int *intValue )
{
int intIndex1;
int intCharValue;
for ( intIndex1 = 0, *intValue = 0;
intIndex1 < strlen( strInstring );
intIndex1++ )
{ intCharValue = char2Number(strInstring[intIndex1]);
if ( intCharValue < 0 ) return 0;
*intValue = *intValue * 10 + intCharValue;
if ( *intValue < 0 ) return 0; }
return -1;
}
// ***** Main ************************************************************
int main( int intArgCount,
char *strArgValues[] )
{
if ( intArgCount == 2 && strcmp( strArgValues[1], "/?" ) == 0 )
{
printf( strcat(strcat("The %s program calculates primes ",
"in a user-specifiable range. "),
"Use the following syntax: %s"),
strArgValues[0],
SYNTAX_REMINDER );
return 0;
}
int intStart;
int intFinish;
if ( intArgCount < 3
||
! string2Number(strArgValues[1], &intStart)
||
! string2Number(strArgValues[2], &intFinish) )
{
printf( "Syntax: %s\n", SYNTAX_REMINDER );
return -1;
}
int intSieveLimit = SIEVESIZE;
if ( intArgCount > 3
&&
( ! string2Number(strArgValues[3], &intSieveLimit)
||
intSieveLimit > SIEVESIZE ) )
{
printf( "Sieve limit is not valid\n" ); return 0;
}
printf( strcat(strcat("Sieve of Eratosthenes primes from least prime >= %d ",
"to greatest prime <= %d\n"),
"Sieve contains %d entries\n"),
MAX(intStart, 3),
intFinish,
intSieveLimit );
int intSieve[SIEVESIZE];
int intPrimes = 0;
int intSievePrimes = 0;
int intDisplayedPrimes = 0;
int intTest;
int intHalfway;
int intIndex1;
int intFound;
time_t ttTimeStart; time( &ttTimeStart );
int intFoundInSieve = 0;
int intFoundUsingBruteForce = 0;
for ( intTest = 3; intTest <= intFinish; intTest = intTest + 2 )
{
intHalfway = (int)(intTest / 2);
intFound = 0;
for ( intIndex1 = 0;
intIndex1 < intSievePrimes
&&
intSieve[intIndex1] <= intHalfway;
intIndex1++ )
if ( IS_FACTOR( intTest, intSieve[intIndex1] ) )
{ intFound = 1; break; }
if ( ! intFound )
for ( intIndex1 =
intSievePrimes > 0 ? intSieve[intSievePrimes - 1] + 2 : 3;
intIndex1 <= intHalfway;
intIndex1 = intIndex1 + 2 )
if ( IS_FACTOR( intTest, intIndex1 ) )
{ intFound = 2; break; }
switch ( intFound )
{
case (0):
{
if ( intSievePrimes < intSieveLimit )
{
intSieve[intSievePrimes] = intTest;
intSievePrimes++;
}
intPrimes++;
if (intTest >= intStart)
{
intDisplayedPrimes++;
printf( "%d%s\n",
intTest,
intPrimes == intSieveLimit ?
" End of the sieve" : "" );
}
break;
}
case (1):
{
intFoundInSieve++; break;
}
case (2):
{
intFoundUsingBruteForce++; break;
}
default:
{
printf( "Programming error: unexpected case\n" );
return 0;
}
}
}
time_t ttTimeEnd; time( &ttTimeEnd );
int intIndex2;
for ( intIndex1 = 0; intIndex1 < intSievePrimes; intIndex1++ )
{
for ( intIndex2 = intIndex1 - 1;
intIndex2 >= 0;
intIndex2-- )
if ( IS_FACTOR(intSieve[intIndex1], intSieve[intIndex2]) )
{
printf( strcat( "Programming error: nonprimes occur in the ",
"sieve at %d and %d: %d and %d\n" ),
intIndex1, intIndex2,
intSieve[intIndex1], intSieve[intIndex2] );
break;
}
if ( intIndex2 >= 0 ) break;
}
if ( intIndex1 != intSievePrimes )
{
return 0;
}
printf( "Number of primes found: %d\n", intPrimes );
printf( "Number of nonprimes found using the sieve: %d\n", intFoundInSieve );
printf( "Number of nonprimes found using brute force: %d\n", intFoundUsingBruteForce );
printf( "Number of primes in the sieve: %d\n", intSievePrimes );
printf( "Number of primes displayed: %d\n", intDisplayedPrimes );
printf( "Time in approximate seconds: %d\n",
(long)ttTimeEnd - (long)ttTimeStart );
return 0;
}
Editor's Note: Updated version of this code, and accompanying commentary, posted here [3].