Fix to My Evil Seive
Some time ago, I posted an academic program I'd written as an example of simple C for calculating primes using the seive of Eratosthenes. However, I have not used C in recent years (I almost returned to it recently and decided not to because of its limitations and my own), and I made an error.
To break up a long printf between readable lines, I'd thoughtlessly used strcat!
This was boneheaded, since strcat assumes that there is space allocated to the right of the left string as opposed to higher-level languages and their string concatenation operator, when an expression using strcat is evaluated.
The error was similar to errors I'd make in the 1970s for a few days or hours when returning from Cobol to assembler, because C looks high level and is not.
The fixed code is at the end of this blog entry.
Since the code wasn't very useful and I'd posted it for comment and for bug finding nobody mentioned the error until recently, when some guy from usenet, with whom I'd clashed in the past, found it and posted a sarcastic note.
Up to now, I've occasionally went looking for trouble in usenet because in the past I have found it a resource for managing anger, learning how to interact with geeks, clarifying my own thinking, and learning from others. Being partly Irish I also like a fight.
However, the learning goal is seldom attained, since as in the case of a post here, the correction is usually in the format "raca, thou fool..." and makes global inferences, which I then counter with an indepth analysis of why the person who said that is wrong, with appropriate references to programming and general culture.
With the result, usually, that hordes of people with nothing better to do are attracted to the crime scene.
Young males, and older males who haven't grown up, of which there are a lot in America and on usenet, are attracted to scenes wherein a single person or usenet poster is the "mark" who has outlier views and an unusual way of expressing himself, especially complexity of speech.
Having been in my younger days on the side of the bully in a bullying group, I am well aware that this allows the young male to relieve his anxiety that he might be queer or otherwise deficient because the "mark" as a scapegoat so obviously is.
This makes no sense. The "mark", the queer, the programmer who "can't" program because he made a mistake AND uses long identifiers, could be a schnook but the people in the lynch mob could remain deficient. Of course, psychological logic of this addictive nature is bad logic, and when we awake we realize that we have better things to do.
For this reason I willingly participated in usenet for 20 years honestly posting my own actual views which were at variance with the majority, honestly taking upon myself the role of victim, but instead of turning the other cheek, fighting back. I also would occasionally come to the aid of others who were being brutalized like the Lone Ranger or the Cisco Kid.
This is at an end.
I started responding to the critic on comp.lang.c but early this morning realized that I was spamming comp.lang.c because as opposed to comp.programming, I have little to offer on C. I last used it at the time when I assisted Nash with C and a lot has changed, and in returning to it I make too many errors.
But more generally I have decided to stay completely away from usenet which is dominated by trolls (who have a nasty habit of using that very word) who have been ejected from the finer establishments by moderators, maitre d'hotels, croupieres and bouncers like Dan Read here.
I am not a Christian, but the Sermon on the Mount contains some practical advice:
Matthew 5:22 But I say unto you, That whosoever is angry with his brother without a cause shall be in danger of the judgment: and whosoever shall say to his brother, Raca, shall be in danger of the council: but whosoever shall say, Thou fool, shall be in danger of hell fire.
Matthew 7:6 Don't give that which is holy to the dogs, neither throw your pearls before the pigs, lest perhaps they trample them under their feet, and turn and tear you to pieces.
Here is the fixed code. I have also fixed the fact that the Web posting destroys My Beautiful Comment Box.
// 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).
//
//
// CHANGE RECORD
//
// 06 25 06 Nilges Bug: use of strcat() was incorrect: doesn't
// obtain storage in C: caused segfaults: fixed
//
#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( "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( "Sieve of Eratosthenes primes from least prime >= %d to greatest prime <= %d\nSieve 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( "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;
}
Response
I first used C in 1978. I can assure you that your "standard" C conventions grew up after that date, and are mostly developer laziness and aliteracy.
In his groundbreaking work on programming style, Kernighan suggested meaningful identifiers in 1975, using English...not single letters as are "standard" only as praxis. Not LOOONG identifiers: this is a caricature by programmers who cannot think up meaningful words because of aliteracy.
I happen to believe that you cannot actually program if you cannot write about programming. I'll grant this is a minority view, but I prefer meaningful names.
Sure, in string2Integer, the 2 is a pun on TO. Boo hoo. The practice was used to name functions in the rexx language and I have nothing but admiration for the (literate) developer of rexx, IBM Fellow Mike Cowlishaw.
The rage expressed on usenet as to this pun is completely disproportionate and rather than speaking its name (an anxiety about one's literacy) it speaks of an unwritten standard that "real", studly C programmers use, and in this, and in the use of longer (not "long") identifiers wif gude gramer and speling, and as regards Hungarian, I refuse to acknowledge any "standard".
This "standard" is simply the collective bad practice of C programmers who aren't in modern terms very productive, who've colonized embedded system design, whose work is disappearing to the Far East, and whose productivity is primarily the result of managerial work, as managers cleverly marshal narrowness, aliteracy and incompetence, and set programmers into infantile competition as opposed to cooperations.
I've maintained C programs written under this regime, and they suck. The use of single letters is not just "confusing", not just in the same psychological way that the use of a longer word is to people who hate language, it is simply the use of a set so bounded as to be inadequate for creating anything like a self-documenting program.
The C standard library is not ignored. However, because my purpose was to code globally, I needed a "minimal set of preconditions" and this means that in trivial cases such as isdigit() functionality, where the "hand" implementation is just as fast as the macro expansion, the "hand" implementation is preferable.
It's already been pointed out in the usenet discussion that there ARE C implementations without all functions in standard library, or worse, buggy or partial implementations.
The mark of a good programmer is not overreliance and overtrust in tools: this is a mark of the subservient and the authoritarian job holder coder.
Not so sure what "pseudo" Hungarian is. Prior to Charles Szymonyi's PhD thesis, which PROVED (not "asserted") that Hungarian notation works to add understandability, a form of "Hungarian" was already in use by IBM mainframe programmers and it added, according to IBM studies, REAL clarity and REAL maintainability (not confirmation and comfort).
There has been NO refutation of this...only laziness and indiscipline.
The "original" algorithm appeared in Niklaus Wirth, Systematic Programming, and was a set or range of algorithms, from brute force to one that used a seive and stopped calculation at the square root and not n/2.
The idea that there is one right and proper algorithm is a type of nasty fundamentalism which simply means that too many programmers don't code, lest some *mullah* make silly generalizations.
It appears you've taken a bunch of secondhand charges from the usenet Swift Boating of the code (where Swift Boating is the hurling of a series of charges, not all defensible, in hoping that the shit sticks to an enemy) and reposted them here in summary format.
I see nothing but bad faith in this.
Feel free to reply. I'd appreciate fewer moralistic and blanket assertions, and less trivia (I know that 2 is prime).
So many things wrong...
Hungarian notation isn't self-documenting in C. Seeing the type of a variable is as simple as scrolling up to "int i;". HN does, however, make it difficult to change the type.
What does this mean to you: short longIntValue;
Unless you want to retype the name of a variable in every instance when you change its type, HN is bad.
You stated that Szymonyi PROVED that HN improves understandability. Understandability is subjective, and therefore can't be "proved".
Since you aren't going to buy a copy of the Standard no matter how much we tell you to, here's a copy of a draft: http://www.open-std.org/JTC1/SC22/WG14/www/docs/n1124.pdf
That looks to me more like a document than "developer laziness and aliteracy".
Also, note the posting of one Usenet regular of another algorithm for this problem. He showed that for large inputs, his method worked billions of times faster than yours. While there may not be one true algorithm, there are terrible algorithms, and yours is one.
Finally, any code that assumes that printf() works also assumes that isdigit() works. That you would create a separate, convoluted, useless function that can be replaced with a quick (isdigit(n) ? n-'0' : -1) is idiocy. Not only that, but the way that you used it was simple to re-implement strtoul. Any code that assumes printf() works also assumes that strtoul() works.
Re-sponse (sigh)
I posted the code for constructive comments and as a result fixed its strcat bug. Andrew Poelstra, you're being manipulated in a Swift Boating by Richard Heathfield based on the latter's resentment, dating from 2000, that I threatened his dominance of the intellectual slum comp.programming with a well-received, literate review of After the Gold Rush.
IF Hungarian notation is "subjective" (where this term of art has reversed meaning since the 17th century and today means "opinions are like assholes, everyone's got one"), then the productivity of NOT using HN is also "subjective".
Globally, not all programmers have Visual Studio and they may not be able to "scroll up", or down, or sideways.
Hungarian notation is indicated for module and local variables because at this level, the type is also known, whereas objects and resources should not use it. It provides a dramatic differentiation between white box variables where the type is known, and resources that can be implemented in different ways over time.
Thanks for the standard. I had one but it got lost in a move to Asia.
However, as I have pointed out, C CANNOT BE STANDARDIZED any more than an assembler can be standardized, and this is because of aliasing, the fact that C in general can write programs such that it's impossible to predict their behavior, owing to aliasing.
Modern standardization of Java and C# MEANS that automated tools have close to a six-sigma chance to verify what code does. This cannot be done for C.
It is simply idiotic to say that if you have printf then you have isdigit; a poster back in the abandoned thread has already pointed out implementations of C which have broken or nonexistent isdigit, whereas printf is more commonly used.
The title of your post is Swift Boating, because unethically and unprofessionally it implies many more things "wrong" than just your opinions. Keith Thompson of the San Diego Supercomputer Center (a man whose credibility is enhanced because he hates my code and unlike Heathfield doesn't hide his identity) has already shown that the code (once you fix strcat) works.
Your anxiety is I might take your job, because it makes no sense to use C in American development (globally, I thought at the time it might make sense to use it, while making a minimal use of the "standard" library). You therefore Swift Boat to prove that The Worst Programmer in the World ain't you.
This is your anxiety, and managers use this anxiety to ensure that programmers work too many hours, replacing what they fear are their limitations, a qualitative anxiety, with quantity.
A woman in Texas ten years ago, whose husband appears to have been some sort of coder, fell into an undiagnosed and untreated post-partum depression and drowned her kids because her weakling husband was more concerned with establishing his shaky sense of mastery by working too many hours, probably because in the Texas engineering culture, he was afraid of this type of Swift Boating: a global challenge to his worth based on a set of lies and stylistic charges.
I've already stated here that my own wife fell into an untreated post-partum depression because I worked in a company where Swift Boating, based not on actual technical facts but on some bearded asshole's opinion, was the norm.
The suits in this company used Bearded Assholes as technical authorities despite the fact that the knowlede of the BA's was limited to IBM mainframes and they typically specialized in one technology such as VTAM.
The key to promotion to BA: working 16 hours a day but billing the client 8, and not claiming pay for the extra 8 in a company where a formal promise had been made to pay for all hours worked.
This, an a consistent projection of sheer arrogance, in which the BA would treat his stylistic prejudices as Holy Writ.
This Swift Boating is welcomed by the suits in place of humanistic Extreme development where a natural worker solidarity occurs.
But even in an Extreme C coding situation, I wouldn't use so-called "standard" C style (single letter identifiers). This is because the standard is just praxis in a backwater.
You and Heathfield and the rest of the massed trolls in comp.programming are promoting in fact what anthropologist Diane Vaughan calls a "normalized deviance".
This is where a group agrees to believe bullshit.
Vaughan showed how "normalized deviance" caused Challenger Space-Shuttle engineers to approve the 1986 launch because their previous procedures were thought by the suits to be like Hungarian Notation.
Today, according to a recent news story, the Space Shuttle astronauts will have a 1/100 chance of DYING in the next launch, because the foam strike problem which brought down Columbia in 2003 hasn't been fixed. Nonetheless, the Bush appointee in charge of NASA has approved the launch because to do otherwise would look bad.
Engineering in America is decadent; it is white people holding on to their jobs and health insurance by any means necessary. You may be able to write C code according to your mental standard, but I don't think it works or forms a rational component of a larger subsystem.
Whereas with no money, living in a cheap hotel room, I developed and published a 26000 line compiler which has been acknowledged as a surprising amount of code for a mere computer book. It's downloadable at Apress and it works.
You will be relieved that I am not looking for a job as a C code monkey. This is because in fact code in industry has to look like the rest of the code produced by the workgroup. If people don't share my style, my style is disruptive and worthless, because it doesn't add in any dramatic way to megaefficiency, and in some ways is micro-inefficient, as in the case, for my vision of clarity, I put the calculation of the limit in the test expression of a short For loop.
Your fear is that under the obscene industrial discipline of the white collar, obscene (as C. Wright Mills knew in 1954) because it is less about "productivity" and more in manufacturing consent and a buffer class between the suits and the immiserated, the members of which fantasize (like Arthur Miller's Willy Loman) that they are meaningful and productive people all their lives.
The world happens not to need another prime number generator EXCEPT in one case. This is education, and it was my goal to get back up to speed in C in order to coach a cs major. I pointed out that running up to n/2 was a choice and there were others, and that the program might have bugs.
I did recommend literate (not long for the sake of long) identifiers and I did recommend Hungarian. But I also warned the student he needed to learn the professor's desires in this regard.
Men who can't teach, who cannot speak to other people except in the register of Swift Boating, the register their uncaring fathers used and from which they haven't recovered, destroy teaching worldwide. They insist on eliminating evolution and Hungarian Notation for identical reasons.
Adorno wrote "all scientists are candidates for posts". That is, they consistently allow careerism and here the need to trash to affect their science.
But is it scientific fact that identifiers should be long and meaningful English words? Perhaps they SHOULD be short and like algebraic symbols as in argc and argv because math is a universal language!
The problem is that the English letters are just as ethno and Euro centric as the words, but the words form a richer semantic space with more choices in the service of meaning...and, English is a global lingua franca.
Have a nice day.
Should have had my head examined
...for using C.
Oh well. Dan works hard to maintain the quality of this site.
I will chill the homeys for him by responding to each and every critique from the trolls massed outside this site.
Unfortunately this will fill Dan's very useful comment display on the main form and make it harder for CSS people to find links to the very interesting discussion of a CSS compiler.
Dan, the Lamma Island site (http://www.lamma.com.hk/) has a "Fight Club" with special permission needed to enter for flame wars. Perhaps I could be your Brad Pitt :-) and the usenet trolls could register with you, enter Fight Club, and go at it with me.
Sorry, but horrible
Sorry, but I think this is a horrible implementation and post, as you managed to misspell both Sieve and Eristophanes, this time.
Also why post code which isn't good, ask for constructive criticism and they say, it might have bugs as if you don't care about them?
Problems with the code:
1)You arbitrarily decided to start counting primes from 3 - what happened to 2?
2)No decomposition into functions except for string stuff. Just one long procedure. :(
3)This isn't the sieve as I know it! The sieve as I know it is supposed to work by filtering using multiplication (efficient!). 0 is not prime. 1 is not prime. 2 is prime. Cross out all multiples of 2. 3 is not crossed out, cross out all multiples of 3. And so on.
4)Bug: searching in range 1 to 10,000, I get 1228 primes found, 3771 nonprimes found in the sieve, and 0 nonprimes found by brute force?
5)You only have to check for divisors up to sqrt(n). Well sounds like you already knew about that one.
Oops
I spell it wrong too (Eratosthenes)
*sigh* Hungarian notation
*sigh* Hungarian notation has nothing to do with data types. See http://www.joelonsoftware.com/articles/Wrong.html (the last third of the page)
Thanks!
Look! Facts!
There sure are a lot of experts in this comment thread!
Glad I stopped by. Unfortunately I now feel like sighing frequently for the rest of the day, just to fit in. These are the times when I'm glad Dan goes to the lengths he does to keep out the trolls.
Further, this the quintessential example of why I never post code in the interweb unless I'm asking for specific help. And in those cases I print the smallest contextually meaningful piece of code I can. No matter how solid your code is, there's a troll with a complaint somewhere.
I think I'm going to spend the rest of the evening correcting the spelling of internet forum posts... :?)
Bad style & implementation
This implementation of the sieveOfErathostenes - if one can call it so - should not be shown to students. Cause it's really bad written C code
Standard C conventions are strictly ignored.
The C standard library is mostly ignored.
An, at least irritating, pseudo "hungarian" notation is used.
It seem's as if the author only knows some parts of the original algorithm. So this version is more a (slow) brute force approach using a cache for the first N primes than an implementation of the sieveOfErathostenes. And at last it is faulty, 2 is not given as prime by this version.