simple algorithm for finding primes

[someone else]

hi all

I'm a newbie to this group. my apologies if I break any rules.

I've wrote a simple program to find the first 1,000,000 primes, and to find
all primes within any range (up to 200 * 10^12)

it's pretty efficient, it took 15 minutes to compute the first 1,000,000
primes.

I would like to here your opinion about it

p.s. I'm not a mathematician, in fact, my math level is primary school
(hardly).

please Cc all replies to ae****@arach.net.au

replace the aesqq with (hrneo) before the @,

thanks

michael

//compiler: ms visual c++ 7.0

#include <stdio.h>

#include <conio.h>

#include <math.h>

int main()

{

long nth,pause;

//************collect info from user**************

printf("\t***WELCOME***\nthis program displays all prime numbers up to about
2 billion\nsince the output proccess taks a lot of resources,if you wish to
display large numbers, it is recommended that you set the Nth prime to be
larger then 100");

printf("\n\nplease enter the Nth prine to be displayed, if you select 10,
the 10th, 20th, 30th... primes will be displayed.\n\nplease select a number
between 1 and 10,000, or 0 to exit\n");

fflush(stdin);

scanf("%d",&nth);

if (!nth) return 0;

printf("please enter after how meny numbers to pause. plese select a number
between 2 and 10,000\n");

fflush(stdin);

scanf("%d",&pause);

//************end collect info from user**************

//create and arry to store the first 5000 primes:

long *prime = new long[1000000];long counter=3;bool flag =1;

prime[0]=1;prime[1]=2;prime[2]=3; //set the first three primes

printf("\n\n\t\t---finished\n\n"); getch();

// i is the number that will be checked if it's a prime

//loop with i = 5 initially, add 2 to i evey cycle,terminate if the counter
is greater then 10000000

for (long i=5;counter<1000000;i+=2,flag=1)

{

//check all primes that satisfy sqrt(i) >= prime

for (long j=2;prime[j]<long(sqrt(double(i))+1);j++)

{

if (i%prime[j]==0)//i is not a prime, go back to the first loop

{

flag=0;

break;

}

}
if (flag)

// now we know that i is a prime (since it's not divisible by any prime that
( root(i) >= prime )

{

prime[counter]=i;

counter++;

if(counter%nth==0) printf("\t%ld",i);

if (counter%(nth*pause)==0) getch();

flag=0;

}

else

continue;

}

printf("\n\n***************************finished*** ***************\n\npress
any key to exit");

getch();

return 0;

}

/**************************

//code to store the first 1000000 primes to a binary file:

//place the code at the END of the file

FILE *fp=fopen("15000pri.bin","r+b");

if (!fp) printf("unable to open file");

fwrite(prime,sizeof(prime)*1000000,1,fp);

if (fclose(fp))

printf("\n\nfile not closed\n\n");

else

printf("\n\nfile successfully closed\n\n");

getch();

//code to get the first 1000000 primes from the binary file:

//place the code right after the declaration of *prime

FILE *fp=fopen("15000pri.bin","r+b");

if (!fp) printf("unable to open file");

fread(prime,sizeof(prime)*1000000,1,fp);

if (fclose(fp))

printf("\n\nfile not closed\n\n");

else

printf("\n\nfile successfully closed\n\n");

getch();

//code to check the chances of a number being a prime when number%pause==0

// pause is a variable entered by the user

double chance = 1.0;

for (long k=1;k<1000000;k++)

{

if (k%(pause/1000)==0) printf("%ld ",prime[k]);

chance -= double(1.0/double(prime[k])*chance);

if (k%pause==0) {printf("\t%f\t%ld",chance,k); getch(); }

}

//code to check primes within a range (maximum 1,000,000,000,000)

// you must have the first 1,000,000 primes loaded from a file or calculated
into the array (prime[1000000])

__int64 lower,upper;

printf("\n\nplease enter the lower range.\n\nplease select a number between
5 and 10^12 (1, and 12 zeroes) , or 0 to exit\n");

fflush(stdin);

scanf("%I64",&lower);

if (!nth) return 0;

printf("please enter the lower range.\n\nplease select a number between 5
and 10^12 (1, and 12 zeroes)");

fflush(stdin);

scanf("%I64",&upper);

if (upper<5 || upper>pow(10.0,12.0) || lower<5 || lower>pow(10.0,12.0))

{ printf("invalid range...exiting"); getch(); return 0; }

for (__int64 l=lower;l<=upper;l+=2,flag=1)

{

//check all primes that satisfy sqrt(i) >= prime

for (long m=2;prime[m]<long(sqrt(double(l))+1);m++)

{

if (l%prime[m]==0)//i is not a prime, go back to the first loop

{

flag=0;

break;

}

}
if (flag)

// now we know that i is a prime (since it's not divisible by any prime that
( root(i) >= prime )

{

printf("\t%I64",l);

flag=0;

}

else

continue;

}

//****************************/

[Jack Klein]

On Tue, 9 Dec 2003 07:23:50 +0800, "someone else"
<zo****@fuck.the.spammers.net> wrote in comp.lang.c:

hi all
Hi yourself.
I'm a newbie to this group. my apologies if I break any rules.
One very important one, as a matter of fact.
I've wrote a simple program to find the first 1,000,000 primes, and to find
all primes within any range (up to 200 * 10^12)

it's pretty efficient, it took 15 minutes to compute the first 1,000,000
primes.

I would like to here your opinion about it

p.s. I'm not a mathematician, in fact, my math level is primary school
(hardly).

please Cc all replies to ae****@arach.net.au

replace the aesqq with (hrneo) before the @,

thanks

michael

//compiler: ms visual c++ 7.0

#include <stdio.h>

#include <conio.h>
Non-standard header.
#include <math.h>

int main()
{

long nth,pause;

//************collect info from user**************

printf("\t***WELCOME***\nthis program displays all prime numbers up to about
2 billion\nsince the output proccess taks a lot of resources,if you wish to
display large numbers, it is recommended that you set the Nth prime to be
larger then 100");

printf("\n\nplease enter the Nth prine to be displayed, if you select 10,
the 10th, 20th, 30th... primes will be displayed.\n\nplease select a number
between 1 and 10,000, or 0 to exit\n");

fflush(stdin);
Oh, there you've gone and invoked undefined behavior. The fflush()
function is undefined on input streams.
scanf("%d",&nth);
Undefined behavior if the value typed in by the user is outside the
range of a signed int.
if (!nth) return 0;

printf("please enter after how meny numbers to pause. plese select a number
between 2 and 10,000\n");

fflush(stdin);

scanf("%d",&pause);

//************end collect info from user**************

//create and arry to store the first 5000 primes:

long *prime = new long[1000000];long counter=3;bool flag =1;
Here's the biggest rule that you broke:

***THIS IS NOT C CODE AT ALL***

There is no such thing as "new" in C, nor is there a type "bool"
unless you have a compiler that supports C99's <stdbool.h> header and
have included that header. That leaves out every single Microsoft
compiler released to data.

[snip]
printf("\n\n\t\t---finished\n\n"); getch();

There is no function named getch() in either the C or C++ language.

Overall, your code is littered with non-standard Microsoft specific
extensions that are not part of either standard C or C++. You should
not be posting to comp.lang.c or comp.lang.c++ until you at least know
the difference between C and C++. A better place for you might be the
group news:comp.alt.lang.learn.c-c++ until you know more.

You should also get a good C programming book if you want to use C,
like one of these two excellent choices:

The C Programming Language, Second Edition
Brian W. Kernighan & Dennis M. Ritchie
Prentice Hall 1988
Hardcover ISBN 0131103709
Softcover ISBN 0131103628

C Programming: A Modern Approach
K. N. King
W. W. Norton & Company 1996
Softcover ISBN 0393969452

Finally, you are reinventing a well-rounded wheel. Do a Google search
on the phrase "Sieve of Eratosthenes" to find an algorithm that is
several thousand years old.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++ ftp://snurse-l.org/pub/acllc-c++/faq

[someone else]

Sieve of Eratosthenes:

Make a list of all the integers less than or equal to n (and greater than
one).
Strike out the multiples of all primes less than or equal to the square root
of n.
Then the numbers that are left are the primes.

"Jack Klein" <ja*******@spamcop.net> wrote in message
news:9h********************************@4ax.com...

On Tue, 9 Dec 2003 07:23:50 +0800, "someone else"
<zo****@fuck.the.spammers.net> wrote in comp.lang.c:

hi all
Hi yourself.

I'm a newbie to this group. my apologies if I break any rules.

One very important one, as a matter of fact.

I've wrote a simple program to find the first 1,000,000 primes, and to find all primes within any range (up to 200 * 10^12)

it's pretty efficient, it took 15 minutes to compute the first 1,000,000
primes.

I would like to here your opinion about it

p.s. I'm not a mathematician, in fact, my math level is primary school
(hardly).

please Cc all replies to ae****@arach.net.au

replace the aesqq with (hrneo) before the @,

thanks

michael

//compiler: ms visual c++ 7.0

#include <stdio.h>

#include <conio.h>

Non-standard header.

duh!

#include <math.h>

int main()
{

long nth,pause;

//************collect info from user**************

printf("\t***WELCOME***\nthis program displays all prime numbers up to about 2 billion\nsince the output proccess taks a lot of resources,if you wish to display large numbers, it is recommended that you set the Nth prime to be larger then 100");

printf("\n\nplease enter the Nth prine to be displayed, if you select 10, the 10th, 20th, 30th... primes will be displayed.\n\nplease select a number between 1 and 10,000, or 0 to exit\n");

fflush(stdin);
Oh, there you've gone and invoked undefined behavior. The fflush()
function is undefined on input streams.

scanf("%d",&nth);

Undefined behavior if the value typed in by the user is outside the
range of a signed int.

if (!nth) return 0;

printf("please enter after how meny numbers to pause. plese select a number between 2 and 10,000\n");

fflush(stdin);

scanf("%d",&pause);

//************end collect info from user**************

//create and arry to store the first 5000 primes:

sorry, my mistake, i meant the first 1,000,000 primes
long *prime = new long[1000000];long counter=3;bool flag =1;

Here's the biggest rule that you broke:

***THIS IS NOT C CODE AT ALL***

There is no such thing as "new" in C, nor is there a type "bool"
unless you have a compiler that supports C99's <stdbool.h> header and
have included that header. That leaves out every single Microsoft
compiler released to data.

true, i could have used:
long *prime = malloc(sizeof(long)*1000000)
but i tried to keep the code more readable by avoiding the use of pointers,
and "bool" could as well have been int

[snip]

printf("\n\n\t\t---finished\n\n"); getch();
There is no function named getch() in either the C or C++ language.

getch() is an istruction to pause the DOS console until a key is pressed so
it has to be platform specific and non standard.

Overall, your code is littered with non-standard Microsoft specific
extensions that are not part of either standard C or C++. You should
not be posting to comp.lang.c or comp.lang.c++ until you at least know
the difference between C and C++. A better place for you might be the
group news:comp.alt.lang.learn.c-c++ until you know more.

You should also get a good C programming book if you want to use C,
like one of these two excellent choices:

The C Programming Language, Second Edition
Brian W. Kernighan & Dennis M. Ritchie
Prentice Hall 1988
Hardcover ISBN 0131103709
Softcover ISBN 0131103628

C Programming: A Modern Approach
K. N. King
W. W. Norton & Company 1996
Softcover ISBN 0393969452

Finally, you are reinventing a well-rounded wheel. Do a Google search
on the phrase "Sieve of Eratosthenes" to find an algorithm that is
several thousand years old.
as i quoted at the beggining, Sieve of Eratosthenes is based on creating an
array of all numbers, while i only created an array of primes, i'm aware
that there are more comlex ways of checking for primes but they require a
university degree in math, and most of them only say that the number is
"allmost sertainly a prime" while my way is absolutely certain, and can be
undestood by non mathematician's.
and finally, since there's no 64 bit integers in standard c, i used
microsoft's implementation, i could have as well used other libraries for 64
bit integers.

all i can say is that if things as nimor as getch() disturb you, i shouldn't
post here anymore, and news:comp.alt.lang.learn.c-c++ is a non active group
--
Jack Klein

michael

[CBFalconer]

someone else wrote:

.... snip ..
all i can say is that if things as nimor as getch() disturb you,
i shouldn't post here anymore, and news:comp.alt.lang.learn.c-c++
is a non active group From the rear: No, one of news:comp.lang.learn.c-c++ and

news:alt.lang.learn.c-c++ is not non-active. Maybe you
shouldn't. The pronoun 'I' should be capitalized. getch() does
not exist in standard C. The word nimor is unknown to me. The
pronoun 'I' should be capitalized. Sentences should usually begin
with a capital letter.

Should nimor be intended to mean normal, the point is that getch
is not a normal thing in C programs, except within the relatively
small subset using certain compilers under certain operating
systems, and thus there is no reason to make any assumptions
whatsoever about what getch does.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

[Grumble]

Jack Klein wrote:

Overall, your code is littered with non-standard Microsoft specific
extensions that are not part of either standard C or C++. You should
not be posting to comp.lang.c or comp.lang.c++ until you at least know
the difference between C and C++. A better place for you might be the
group news:comp.alt.lang.learn.c-c++ until you know more.

I think you meant alt.comp.lang.learn.c-c++ (there is not comp.alt
hierarchy).

[osmium]

someone else wrote:

Finally, you are reinventing a well-rounded wheel. Do a Google search
on the phrase "Sieve of Eratosthenes" to find an algorithm that is
several thousand years old.
as i quoted at the beggining, Sieve of Eratosthenes is based on creating

an array of all numbers, while i only created an array of primes, i'm aware
that there are more comlex ways of checking for primes but they require a
university degree in math, and most of them only say that the number is
"allmost sertainly a prime" while my way is absolutely certain, and can be
undestood by non mathematician's.
and finally, since there's no 64 bit integers in standard c, i used
microsoft's implementation, i could have as well used other libraries for 64 bit integers.

The place to tell us that (sieve) was in a comment in the program, not in a
rebuttal to a Usenet thread.

You will be treated more seriously if you use standard, formal English. The
headers on your post indicate you have a spell checker available. Also, get
rid of all that white space.

You might be happier in a forum or chat room or bulletin board or something.
Richard Heathfield mentioned a chat room, IIRC a week or so ago. You might
try to find that using google advanced groups. The other newsgroup
suggested is also anal retentive WRT things such as getch(). I would expect
a more relaxed attitude in some of these other access methods, though I have
never tried them.

[August Derleth]

"someone else" <zo****@fuck.the.spammers.net> wrote in message news:<3f******@funnel.arach.net.au>...

Sieve of Eratosthenes:

Make a list of all the integers less than or equal to n (and greater than
one).
Strike out the multiples of all primes less than or equal to the square root
of n.
Then the numbers that are left are the primes.
Yes. We know this. We've probably programmed it in more languages than
you even know of.

"Jack Klein" <ja*******@spamcop.net> wrote in message
news:9h********************************@4ax.com...

On Tue, 9 Dec 2003 07:23:50 +0800, "someone else"
<zo****@fuck.the.spammers.net> wrote in comp.lang.c:

#include <conio.h>
Non-standard header.

duh!

Please try not to be rude. If you must be rude, try not to be stupid.

Since it's non-standard, it's off-topic here. Try another newsgroup.

Here's the biggest rule that you broke:

***THIS IS NOT C CODE AT ALL***

There is no such thing as "new" in C, nor is there a type "bool"
unless you have a compiler that supports C99's <stdbool.h> header and
have included that header. That leaves out every single Microsoft
compiler released to data.

true, i could have used:
long *prime = malloc(sizeof(long)*1000000)
but i tried to keep the code more readable by avoiding the use of pointers,
and "bool" could as well have been int

And in doing so, you wrote code that isn't C and has no place here.
Try again later, with some brains and common courtesy.

[snip]

printf("\n\n\t\t---finished\n\n"); getch();
There is no function named getch() in either the C or C++ language.

getch() is an istruction to pause the DOS console until a key is pressed so
it has to be platform specific and non standard.

You understand that much and yet are still so clueless.

comp.lang.c is for discussing Standard C. Any reading of the FAQ would
tell you that. You did read the FAQ, didn't you?

If not, goodbye.
all i can say is that if things as nimor as getch() disturb you, i shouldn't
post here anymore, and news:comp.alt.lang.learn.c-c++ is a non active group

Finally, you get it. Goodbye.

[Randy Howard]

In article <3F***************@yahoo.com>, cb********@yahoo.com says...

someone else wrote:

all i can say is that if things as nimor as getch() disturb you,

The word nimor is unknown to me.

My guess would be "minor".

--
Randy Howard _o
2reply remove FOOBAR \<,
______________________()/ ()______________________________________________
SCO Spam-magnet: po********@sco.com

[someone else]

hi all

I'm a newbie to this group. my apologies if I break any rules.

I've wrote a simple program to find the first 1,000,000 primes, and to find
all primes within any range (up to 200 * 10^12)

it's pretty efficient, it took 15 minutes to compute the first 1,000,000
primes.

I would like to here your opinion about it
I sincerely apologise for not following the rules last time.
and I would really appreciate RELEVANT responses,
p.s. I'm not a mathematician, in fact, my math level is primary school
(hardly).

thanks

Michael

//compiler: ms visual c++ 7.0
#include <stdio.h>
#include <math.h>

int main()
{
long nth,pause;

//************collect info from user**************

printf("\t***WELCOME***\nthis program displays all prime numbers up to about
2 billion\nsince the output process takes a lot of resources,if you wish to
display large numbers, it is recommended that you set the Nth prime to be
larger then 100");

printf("\n\nplease enter the Nth prime to be displayed, if you select 10,
the 10th, 20th, 30th... primes will be displayed.\n\nplease select a number
between 1 and 10,000, or 0 to exit\n");

scanf("%d",&nth);

if (!nth) return 0;

printf("please enter after how many numbers to pause. please select a number
between 2 and 10,000\n");

scanf("%d",&pause);

//************end collect info from user**************

//create and array to store the first 5000 primes:
long *prime = malloc(sizeof(long)*1000000);long counter=3;int flag =1;
*prime=1;*(prime+1)=2;*prime+2)=3; //set the first three primes
printf("\n\n\t\t---finished\n\n");
// i is the number that will be checked if it's a prime
//loop with i = 5 initially, add 2 to i every cycle,terminate if the counter
is greater then 10000000
for (long i=5;counter<1000000;i+=2,flag=1)
{
//check all primes that satisfy sqrt(i) >= prime
for (long j=2;*(prime+j)<long(sqrt(double(i))+1);j++)
{
if (i%*(prime+j)==0)//i is not a prime, go back to the first loop
{
flag=0;
break;
}
}

// now we know that i is a prime (since it's not divisible by any prime
that
( root(i) >= prime )

if (flag)
{
*(prime+counter)=i;
counter++;
if(counter%nth==0) printf("\t%ld",i);
if (counter%(nth*pause)==0) scanf("%*c");
flag=0;
}
else
continue;
}//end for loop
free(primes);
printf("\n\n***************************finished*** ***************\n\n);
scanf("%*c");
return 0;
}
/**************************

//code to store the first 1000000 primes to a binary file:

//place the code at the END of the file

FILE *fp=fopen("15000pri.bin","r+b");
if (!fp) printf("unable to open file");
fwrite(prime,sizeof(prime)*1000000,1,fp);
if (fclose(fp))
printf("\n\nfile not closed\n\n");
else
printf("\n\nfile successfully closed\n\n");

//code to get the first 1000000 primes from the binary file:
//place the code right after the declaration of *prime
FILE *fp=fopen("15000pri.bin","r+b");
if (!fp) printf("unable to open file");
fread(prime,sizeof(prime)*1000000,1,fp);
if (fclose(fp))
printf("\n\nfile not closed\n\n");
else
printf("\n\nfile successfully closed\n\n");

//code to check the chances of a number being a prime when number%pause==0
// pause is a variable entered by the user
double chance = 1.0;
for (long k=1;k<1000000;k++)
{
if (k%(pause/1000)==0) printf("%ld ",*(prime+k));
chance -= double(1.0/double(*(prime+k)) * chance);
if (k%pause==0) {printf("\t%f\t%ld",chance,k); scanf("%*c"); }
}

//code to check primes within a range (maximum 200,000,000,000,000)

// you must have the first 1,000,000 primes loaded from a file or calculated
into the *prime
__int64 lower,upper;//non standard c. for the purpose of dealing with 64 bit
integers
//it can be changed to unsigned long, but then it will only support numbers
up to 4,294,967,296
// and change scanf("%I64") to scanf("%lu")

printf("\n\nplease enter the lower range.\n\nplease select a number between
5 and 10^12 (1, and 12 zeroes) , or 0 to exit\n");

scanf("%I64",&lower);
if (!nth) return 0;
printf("please enter the lower range.\n\nplease select a number between 5
and 10^12 (1, and 12 zeroes)");
fflush(stdin);
scanf("%I64",&upper);
if (upper<5 || upper>pow(10.0,12.0) || lower<5 || lower>pow(10.0,12.0))
{ printf("invalid range...exiting"); scanf("%*c); return 0; }

for (__int64 l=lower;l<=upper;l+=2,flag=1)
{
//check all primes that satisfy sqrt(i) >= prime
for (long m=2;prime[m]<long(sqrt(double(l))+1);m++)
{
if (l%prime[m]==0)//i is not a prime, go back to the first loop
{
flag=0;
break;
}
}

if (flag)
// now we know that i is a prime (since it's not divisible by any prime that
( root(i) >= prime )
{
printf("\t%I64",l);
flag=0;
}
else
continue;
}

//****************************/

[Paul Hsieh]

In article <3f******@funnel.arach.net.au> says...

Sieve of Eratosthenes:

Make a list of all the integers less than or equal to n (and greater than
one). Strike out the multiples of all primes less than or equal to the
square root of n. Then the numbers that are left are the primes.

This discussion is probably better suited to something like comp.programming.
They are not much into algorithms or non-C related subjects at all around here.
But in any event, here's a nice little Sieve of Eratosthenes for you:

#define QF_SIEVE_SIZE (1024*1024)
static unsigned int qfSieve[QF_SIEVE_SIZE];
#define qfsIdx(x) ((x) >> 6)
#define qfsBit(x) (1 << (((x) & 63) >> 1))

/* You need to call this before calling the function below */

static void initQFSieve (void) {
int i, j, p;
for (i=0; i < QF_SIEVE_SIZE; i++) qfSieve[i] = 0;
qfSieve[0] = 1;
for (p=3; p < (QF_SIEVE_SIZE * 64); p += 2) {
if ((qfSieve[qfsIdx (p)] & qfsBit (p)) != 0) continue;
j = p + p;
for (i = j + p; i < (QF_SIEVE_SIZE * 64); i += j) {
qfSieve[qfsIdx (i)] |= qfsBit (i);
}
}
}

enum QPT_result {
QPT_COMP = 0,
QPT_PRIME = 1,
QPT_DUNNO = 2
};

/* Test for evenness, equal to 2 or 3, otherwise the sieve of eratosthenes */

enum QPT_result quickPrimeTest (unsigned int l) {
if (l - 2 < 2) return QPT_PRIME;
if ((l & 1) == 0) return QPT_COMP;
if (l >= (QF_SIEVE_SIZE * 64)) return QPT_DUNNO;
if ((qfSieve[qfsIdx (l)] & qfsBit (l)) == 0) return QPT_PRIME;
return QPT_COMP;
}

You can find a more generic prime testing algorithm that handles all positive
singed numbers up to 32 bits in length in reasonable time, with reasonable
resources here:

http://www.pobox.com/~qed/32bprim.c

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[Richard Heathfield]

Paul Hsieh wrote:

<snip>

You can find a more generic prime testing algorithm that handles all
positive singed numbers up to 32 bits in length in reasonable time, with
reasonable resources here:

http://www.pobox.com/~qed/32bprim.c

Just like your line-reading code, this didn't compile:

gcc -g -W -Wall -ansi -pedantic -o foo foo.c -lm
foo.c: In function 'mulMod':
foo.c:91: '__int64' undeclared (first use in this function)
foo.c:91: (Each undeclared identifier is reported only once
foo.c:91: for each function it appears in.)
foo.c:91: parse error before 'a'
foo.c:94: 'a' undeclared (first use in this function)
foo.c:94: parse error before 'x'
foo.c:94: parse error before 'y'
foo.c:90: warning: unused parameter 'x'
foo.c:90: warning: unused parameter 'y'
foo.c:97: warning: control reaches end of non-void function
foo.c: In function 'powMod':
foo.c:107: warning: comparison between signed and unsigned
foo.c: In function 'SPPTestBase':
foo.c:130: warning: unused variable 'in'
foo.c: In function 'main':
foo.c:173: warning: unused parameter 'argc'
foo.c:173: warning: unused parameter 'argv'
make: *** [foo] Error 1
--
Richard Heathfield : bi****@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

[Arthur J. O'Dwyer]

On Wed, 10 Dec 2003, someone else wrote:

hi all

I'm a newbie to this group. my apologies if I break any rules.
Yes, but not quite as egregiously. Please don't change the subject
line of an old thread unless you are adding an [OT] flag or forking
a new discussion topic. Please try as hard as you can to write
properly capitalized and grammatical English, as we have many non-
native speakers of English here. And lastly, please please *please*
don't post unindented code that looks like trash and doesn't even
compile! See below.
I've wrote a simple program to find the first 1,000,000 primes, and to find
all primes within any range (up to 200 * 10^12)

it's pretty efficient, it took 15 minutes to compute the first 1,000,000
primes.
That *sounds* slow, but it obviously depends on your system.

I would like to here your opinion about it
I sincerely apologise for not following the rules last time.
and I would really appreciate RELEVANT responses,
p.s. I'm not a mathematician, in fact, my math level is primary school
(hardly).
If you're looking for good algorithms, try comp.programming.
If you want good C criticism, you'd better format your code before
you try posting it here again. If it doesn't compile (as yours
doesn't, due to incomplete string literals and badly wrapped comment
text), I won't explain what's wrong with it. And if I can't even
*read* it (as I can't yours, due to your lack of indentation and
terrible use of whitespace), then I won't even bother to fix the
mistakes that make it not compile.

printf("\t***WELCOME***\nthis program displays all prime numbers up to about
2 billion\nsince the output process takes a lot of resources,if you wish to
display large numbers, it is recommended that you set the Nth prime to be
larger then 100");
Line breaks are significant in C. Fix your string.
long *prime = malloc(sizeof(long)*1000000);long counter=3;int flag =1;
Line breaks are significant to your users, also. Fix your
declarations so that they're readable. Also note the bad use
of sizeof(long) in place of sizeof *prime.
*prime=1;*(prime+1)=2;*prime+2)=3; //set the first three primes
This line just plain isn't C. Also note that // comments are new
in C99, and IMHO should have been deprecated anyway.
is greater then 10000000
This line isn't C either.
//check all primes that satisfy sqrt(i) >= prime
for (long j=2;*(prime+j)<long(sqrt(double(i))+1);j++)
This line isn't C either. The long(...) syntax looks like old-style
C++, though. Also, do you have some personal vendetta against the
[] subscripting operator? *(prime+j) == prime[j].
( root(i) >= prime )
This line is going to get you some funny messages from the compiler,
too.
if (counter%(nth*pause)==0) scanf("%*c");
This is not the preferred way to discard a single character from
stdin. Write getchar(); if that's what you mean. Otherwise, write

while (getchar() != '\n') continue;

or something similar.

//code to store the first 1000000 primes to a binary file:

//place the code at the END of the file
Didn't you just close 'main'? You can't put executable code at
file scope; it won't compile. And you meant to open 'fp' for
writing ("wb") at this point, no doubt.
fwrite(prime,sizeof(prime)*1000000,1,fp);
fwrite(prime, 1000000, sizeof *prime, fp);
fread(prime,sizeof(prime)*1000000,1,fp);
fread(prime, 1000000, sizeof *prime, fp);

fflush(stdin);
Undefined behavior. Write scanf("%*[^\n]\n"); if that's what
you mean.
for (__int64 l=lower;l<=upper;l+=2,flag=1)
Please don't use 'l' as a variable name in Usenet-posted code.
There's a good reason why not, and I will give you 1 guess.
printf("\t%I64",l);
Try not to use tabs in your output. Ever. Because it makes your
output look silly when the user has his terminal configured slightly
differently from how you have *your* terminal configured. And
because in general, you're just using '\t' as an obfuscation for
' ' anyway. Do you think the backslash makes it look cooler
or something?
//****************************/

Finally, this comment style will definitely confuse your maintenance
programmers, because it means *slightly* different things in C89 and
C99. Stick to a comment style that either (1) works in both languages,
or (2) fails spectacularly in C89. Don't mix the two unless you want
frustrated users who can't understand why the compiler is complaining
about /'s not being a unary operator.

Format your code properly, fix these bugs, and submit it again.
Then I bet you'll get some real help with whatever problems you're
having with the program itself.

HTH,
-Arthur

[Arthur J. O'Dwyer]

On Tue, 9 Dec 2003, Richard Heathfield wrote:

Paul Hsieh wrote:

http://www.pobox.com/~qed/32bprim.c

Just like your line-reading code, this didn't compile:

gcc -g -W -Wall -ansi -pedantic -o foo foo.c -lm
foo.c: In function 'mulMod':
foo.c:91: '__int64' undeclared (first use in this function)

To Richard: Note that Paul did address this problem in a
comment buried in the code. If I were to use his code in a
project, I'd make sure to read all the comments before starting
to compile it.

To Paul: IMHO it would be better to write the *portable*
version of the code by default (e.g., use 'long int' instead of
'__int64'), and then have a comment buried in the code (or
preferably at the top of the file) telling the sophisticated
source diver what to do if he wants better performance on a
Microsoft compiler. This way, people can use the code "out of
the box," like Richard tried to do, and it will work -- but
those who need the performance can make minor adjustments and
get their performance, too.
Best of both worlds: set up a 'typedef' at the top of the
file, with an explanatory comment, and let it default to the
most portable setting possible.

-Arthur

[Sidney Cadot]

Richard Heathfield wrote:

Paul Hsieh wrote:

<snip>

You can find a more generic prime testing algorithm that handles all
positive singed numbers up to 32 bits in length in reasonable time, with
reasonable resources here:

http://www.pobox.com/~qed/32bprim.c

Just like your line-reading code, this didn't compile:

gcc -g -W -Wall -ansi -pedantic -o foo foo.c -lm
foo.c: In function 'mulMod':
foo.c:91: '__int64' undeclared (first use in this function)
foo.c:91: (Each undeclared identifier is reported only once
foo.c:91: for each function it appears in.)
foo.c:91: parse error before 'a'
foo.c:94: 'a' undeclared (first use in this function)
foo.c:94: parse error before 'x'
foo.c:94: parse error before 'y'
foo.c:90: warning: unused parameter 'x'
foo.c:90: warning: unused parameter 'y'
foo.c:97: warning: control reaches end of non-void function
foo.c: In function 'powMod':
foo.c:107: warning: comparison between signed and unsigned
foo.c: In function 'SPPTestBase':
foo.c:130: warning: unused variable 'in'
foo.c: In function 'main':
foo.c:173: warning: unused parameter 'argc'
foo.c:173: warning: unused parameter 'argv'
make: *** [foo] Error 1

....You probably just forgot the flag to enable the experimental
"operator introduction" feature.

Just venting some frustration....

Best regards, Sidney

[someone else]

Paul Hsieh" <qe*@pobox.com> wrote in message
news:MP************************@news.sf.sbcglobal. net...

In article <3f******@funnel.arach.net.au> says...

Sieve of Eratosthenes:

Make a list of all the integers less than or equal to n (and greater than one). Strike out the multiples of all primes less than or equal to the
square root of n. Then the numbers that are left are the primes.
This discussion is probably better suited to something like

comp.programming. They are not much into algorithms or non-C related subjects at all around here. But in any event, here's a nice little Sieve of Eratosthenes for you:
<snip>
I tried the code from the link http://www.pobox.com/~qed/32bprim.c
and indeed it's a little faster then mine (10%-15%)
but it's pretty comlicated and requires a good understanding of both math
and c, and like you said, is better suited to comp.programming, and unestly,
i did not understand all of it.

i truncated my code to show you how simple it is:

/* just remember to include math.h and stdio.h */
long *prime = malloc(sizoof(long)*1000000);long counter=3;int flag =1;
prime[0]=1;prime[1]=2;prime[2]=3;
for (long i=5;counter<100000000;i+=2,flag=1) {
/*check all primes that satisfy sqrt(i) >= prime */
for (long j=2;prime[j]<long(sqrt(double(i))+1);j++) {
if (i%prime[j]==0) { /* i is not a prime, go back to the first loop
*/
flag=0;
break;
}
}

if (flag) {
// now we know that i is a prime (since it's not divisible by any prime
that ( root(i) >= prime )
if (counter<1000000) {prime[counter]=i; counter++; }
printf("\t%ld",i);
flag=0;
}
else
continue;
}
printf("\n\n*****************finished***********\n \npress any key to exit");
getchar();
You can find a more generic prime testing algorithm that handles all positive singed numbers up to 32 bits in length in reasonable time, with reasonable
resources here:

http://www.pobox.com/~qed/32bprim.c

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[glen herrmannsfeldt]

Arthur J. O'Dwyer wrote:

(snip)

To Richard: Note that Paul did address this problem in a
comment buried in the code. If I were to use his code in a
project, I'd make sure to read all the comments before starting
to compile it.

It just occurred to me how nice it would be to have a statement,
probably for the preprocessor, that would cause a message to
be printed when it compiled. Such warnings could then be
put in that way.

The IBM S/360 Assemblers, and successors, have an opcode to
print out a message at assembly time, mostly so that macro
expansions can print error messages.

It would seem that preprocessed C could also have messages
that need to be printed.

#ifdef NUM<0
#note Oops, NUM is less than zero!
#else
int x[NUM];
#endif

-- glen

[Dik T. Winter]

In article <g5wBb.71820$_M.359005@attbi_s54> glen herrmannsfeldt <ga*@ugcs.caltech.edu> writes:
....

It would seem that preprocessed C could also have messages
that need to be printed.

#ifdef NUM<0
#note Oops, NUM is less than zero!
#else
int x[NUM];
#endif

#if NUM<0
#error Oops, NUM is less than zero!
#else
int x[NUM];
#endif
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, [phone]
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

[Paul Hsieh]

someone says...

Paul Hsieh" <qe*@pobox.com> wrote:

In article <3f******@funnel.arach.net.au> says...

Sieve of Eratosthenes:

Make a list of all the integers less than or equal to n (and greater
than one). Strike out the multiples of all primes less than or equal to
the square root of n. Then the numbers that are left are the primes.
This discussion is probably better suited to something like
comp.programming. They are not much into algorithms or non-C related
subjects at all around here. But in any event, here's a nice little Sieve
of Eratosthenes for you:

<snip>
I tried the code from the link http://www.pobox.com/~qed/32bprim.c
and indeed it's a little faster then mine (10%-15%)

Well it includes the Sieve of Eratosthenes within the source. It also includes
a kind of "parallel small prime divisor test" (using gcd!) before I bring out
the big guns (Strong-Pseduo-Prime test.) Given that you don't seem to care
about memory usage, you can easily crank the performance for small primes such
as all those < 10^6 by simply increasing the size of the sieve (QF_SIEVE_SIZE)
as desired.
but it's pretty comlicated and requires a good understanding of both math
and c, and like you said, is better suited to comp.programming, and unestly,
i did not understand all of it.

Well, completely understanding it may be a tall order. But I give references
for the math-related algorithms, so you can study those at your leisure. What
is worth-while *understanding* in my algorithm is that it takes roughly the
same amount of time (once it gets past the sieve, and trivial divisors, I mean)
regardless of the size of the input.

Your algorithm is a fine, simplistic algorithm, however it really only works
because you determine the entire sequence of primes one after another. But
for longer and longer sequence of primes it will get slower and slower and
you'll run out of memory sooner or later.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[Paul Hsieh]

aj*@nospam.andrew.cmu.edu says:

To Paul: IMHO it would be better to write the *portable*
version of the code by default (e.g., use 'long int' instead of
'__int64'), and then have a comment buried in the code (or
preferably at the top of the file) telling the sophisticated
source diver what to do if he wants better performance on a
Microsoft compiler. This way, people can use the code "out of
the box," like Richard tried to do, and it will work -- but
those who need the performance can make minor adjustments and
get their performance, too.

Well, as you can imagine my considerations of whether or not Richer Heathfield
can find some violation of the ANSI standard in my code is not exactly high on
my todo list. I've got navel lint that needs sorting.

I am not typically prone to writing non-portable code just for the fun of it.
Using __int64 is not a "performance concern" (it rarely is) -- its a
functionality consideration. Using "long int" which may be implemented by a
compiler to be 32 bits, is not an acceptable compromise -- it would reduce the
correctness of the algorithm to a range of <65536 (the Sieve of Eratosthenes,
by itself can easily go beyond this.) This is the whole "widening multiply"
thing all over again (which I won't regurgitate here, as it always seems to
take 10 posts of explanation before people "get it".)

But since you asked so nicely, I have made a correction which uses *doubles* in
place of __int64 if compiled with an unrecognized compiler. This allows it to
work for inputs that are up to 26 bits on most typical machines with a 64 bit
IEEE-754 double implementation (it would also work for all 32bits for typical
80+ bit FP implementations). And I threw in some "guesswork code" about how it
might work on gcc.

So its now more "portable", but that won't help it be any more correct on
platforms without a 64 bit integer (or 80 bit FP.)

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[glen herrmannsfeldt]

Dik T. Winter wrote:

In article <g5wBb.71820$_M.359005@attbi_s54> glen herrmannsfeldt writes:
...

> It would seem that preprocessed C could also have messages
> that need to be printed.
>
> #ifdef NUM<0
> #note Oops, NUM is less than zero!
> #else
> int x[NUM];
> #endif

#if NUM<0
#error Oops, NUM is less than zero!
#else
int x[NUM];
#endif

Not quite what I wanted. That seems to cause a fatal error.

I suppose the example isn't very good, but there are cases when
a warning, or even less. Maybe just a reminder to the person
compiling the program.

-- glen

[Richard Heathfield]

Paul Hsieh wrote:

aj*@nospam.andrew.cmu.edu says:

To Paul: IMHO it would be better to write the *portable*
version of the code by default (e.g., use 'long int' instead of
'__int64'), and then have a comment buried in the code (or
preferably at the top of the file) telling the sophisticated
source diver what to do if he wants better performance on a
Microsoft compiler. This way, people can use the code "out of
the box," like Richard tried to do, and it will work -- but
those who need the performance can make minor adjustments and
get their performance, too.
Well, as you can imagine my considerations of whether or not Richer
Heathfield can find some violation of the ANSI standard in my code is not
exactly high on
my todo list. I've got navel lint that needs sorting.

Oh, I see. Since you posted it in comp.lang.c, I made a not unnatural, but
nevertheless apparently incorrect, assumption that the code was intended to
be portable. If it were not so intended, then of course it's not surprising
that I got compilation errors. What /is/ surprising is that you should post
(a link to) such code here in comp.lang.c.

I am not typically prone to writing non-portable code just for the fun of
it. Using __int64 is not a "performance concern" (it rarely is) -- its a
functionality consideration. Using "long int" which may be implemented by
a compiler to be 32 bits, is not an acceptable compromise -- it would
reduce the correctness of the algorithm to a range of <65536 (the Sieve of
Eratosthenes,
by itself can easily go beyond this.)
Yes, I managed to get a sieve working cheerfully even right up to one
million even under MS-DOS (admittedly I saved lots of space by testing 2
separately and throwing out all other even numbers).
This is the whole "widening
multiply" thing all over again (which I won't regurgitate here, as it
always seems to take 10 posts of explanation before people "get it".)

But since you asked so nicely, I have made a correction which uses
*doubles* in
place of __int64 if compiled with an unrecognized compiler. This allows
it to work for inputs that are up to 26 bits on most typical machines with
a 64 bit IEEE-754 double implementation (it would also work for all 32bits
for typical
80+ bit FP implementations). And I threw in some "guesswork code" about
how it might work on gcc.
Why not just use bignums, which can be written 100% portably and with 100%
accuracy?
So its now more "portable", but that won't help it be any more correct on
platforms without a 64 bit integer (or 80 bit FP.)

Solutions are possible that are correct and portable even to such platforms.

--
Richard Heathfield : bi****@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

[Arthur J. O'Dwyer]

On Wed, 10 Dec 2003, Richard Heathfield wrote:

Paul Hsieh wrote:

aj*@nospam.andrew.cmu.edu says:

To Paul: IMHO it would be better to write the *portable*
version of the code by default (e.g., use 'long int' instead of
'__int64'), and then have a comment buried in the code (or
preferably at the top of the file) telling the sophisticated
source diver what to do if he wants better performance on a
Microsoft compiler. This way, people can use the code "out of
the box," like Richard tried to do, and it will work -- but
those who need the performance can make minor adjustments and
get their performance, too.

Well, as you can imagine my considerations of whether or not Richer
Heathfield can find some violation of the ANSI standard in my code is
not exactly high on my todo list. I've got navel lint that needs
sorting.

Oh, I see. Since you posted it in comp.lang.c, I made a not unnatural, but
nevertheless apparently incorrect, assumption that the code was intended to
be portable.

You know, Richard, I was *trying* to defuse the situation. :-)
Anyway, the point is that Paul (AFAICT) writes code for Pentiums. It
seems to be "what he does." It is slightly unreasonable to expect
Paul to re-write the Pentium code on his website -- which /is/ *mostly*
portable C code -- every time he wants to give an example of how
something could be done in (*completely* portable) C.
It's not good to post code that isn't portable -- especially if
it's unportable enough to actually refuse to compile on many
implementations -- in comp.lang.c. But Paul certainly added to the
discussion, and it would be fairly trivial to "portabilize" his code
when or if the OP needed it. All that was required, IMHO, was a little
note: "__int64 is not standard C. Replace it with some type that has
64 or more bits of integer precision on your system."

I am not typically prone to writing non-portable code just for the fun of
it. Using __int64 is not a "performance concern" (it rarely is) -- its a
functionality consideration. Using "long int" which may be implemented by
a compiler to be 32 bits, is not an acceptable compromise -- it would
reduce the correctness of the algorithm to a range of <65536 (the Sieve of
Eratosthenes, by itself can easily go beyond this.)
Given a suitably Turing-complete programming language, *everything* is
a performance concern. ;-) In this case, one portable alternative would
be to compute the "widening multiply" in halves (most significant and
least significant 32-bit sections). I don't know how you would do this
in C, but I assure you it can be done.
Richard, in his flamboyant way, suggests bignums. :)

This is the whole "widening
multiply" thing all over again (which I won't regurgitate here, as it
always seems to take 10 posts of explanation before people "get it".)
I think I get it, and I know why you used __int64 in the first
place. I merely think that you should have given a slightly larger
nod to portability before posting the code in a group dedicated to
*portable* code.

<snip> 80+ bit FP implementations). And I threw in some "guesswork code" about
how it might work on gcc.

<OT> Does gcc have C99's type int64_t (or whatever it really is)? </OT>

-Arthur

[Richard Heathfield]

Arthur J. O'Dwyer wrote:

On Wed, 10 Dec 2003, Richard Heathfield wrote:
<snip>

Oh, I see. Since you posted it in comp.lang.c, I made a not unnatural,
but nevertheless apparently incorrect, assumption that the code was
intended to be portable.

You know, Richard, I was *trying* to defuse the situation. :-)

So was I, believe it or not. The paragraph you quote above was intended to
explain to Paul that I had jumped to an incorrect conclusion about the
intended scope of the code he posted.
Anyway, the point is that Paul (AFAICT) writes code for Pentiums. It
seems to be "what he does." It is slightly unreasonable to expect
Paul to re-write the Pentium code on his website -- which /is/ *mostly*
portable C code -- every time he wants to give an example of how
something could be done in (*completely* portable) C.
Um, no, it's not unreasonable at all. If he wants to give an example of how
something could be done in *completely* portable C, then nothing is
preventing him from doing that, but I don't see how he can provide a
portable example using /non/-portable code.
It's not good to post code that isn't portable -- especially if
it's unportable enough to actually refuse to compile on many
implementations -- in comp.lang.c.
Right.
But Paul certainly added to the
discussion, and it would be fairly trivial to "portabilize" his code
when or if the OP needed it.

I don't dispute either of these points. Nor was I trying to get on Paul's
case, particularly. I was not being disingenuous in my original reply; I
simply made an incorrect assumption (viz. that the posted code was intended
to be portable).

<snip>

--
Richard Heathfield : bi****@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

[Paul Hsieh]

Arthur J. O'Dwyer says...

On Wed, 10 Dec 2003, Richard Heathfield wrote:

Paul Hsieh wrote:

Arthur J. O'Dwyer says:
> To Paul: IMHO it would be better to write the *portable* version of
> the code by default (e.g., use 'long int' instead of '__int64'), and
> then have a comment buried in the code (or preferably at the top of
> the file) telling the sophisticated source diver what to do if he
> wants better performance on a Microsoft compiler. This way, people
> can use the code "out of the box," like Richard tried to do, and it
> will work -- but those who need the performance can make minor
> adjustments and get their performance, too.

Well, as you can imagine my considerations of whether or not Richer
Heathfield can find some violation of the ANSI standard in my code is
not exactly high on my todo list. I've got navel lint that needs
sorting.
Oh, I see. Since you posted it in comp.lang.c, I made a not unnatural, but
nevertheless apparently incorrect, assumption that the code was intended
to be portable.

You know, Richard, I was *trying* to defuse the situation. :-)
Anyway, the point is that Paul (AFAICT) writes code for Pentiums.

As is evidenced by the feedback I get for http://bstring.sf.net/ from people
who use Linux and Mac OS X. I have a bunch of stuff on my website about
Pentiums in my assembly pages. And __int64 is a MSVC/WATCOM-ism, not a
"Pentiumism". Linux on Pentium and Borland C people are likely to have as many
objections with my use of it as anyone else.

The OP was clearly writing DOS or Windows code, and my response was clearly
directed at the OP, not anyone else. I was trying to tell the OP that this is
not a group where algorithms or performance can be sensibly discussed. The
fact that *I* am posting and reading this newsgroup is a complete fluke, and so
I was trying to indicate to the OP should probably broaden his/her horizons
when seeking those kind of answers.
[...] It
seems to be "what he does." It is slightly unreasonable to expect
Paul to re-write the Pentium code on his website -- which /is/ *mostly*
portable C code -- every time he wants to give an example of how
something could be done in (*completely* portable) C.
No, I would prefer to write portable code, because my occasional use of
"Pentium code" is limited to when I can't find a realistic way to do without,
or when I am really just analyzing a Pentium (or one of its clones.) Writing
"Pentium-C" is tantamount to writing assembly -- and I do it sometimes, but its
not because I have some aversion to writing portable code.
It's not good to post code that isn't portable -- especially if it's
unportable enough to actually refuse to compile on many implementations --
in comp.lang.c. But Paul certainly added to the discussion, and it would be
fairly trivial to "portabilize" his code when or if the OP needed it.
No its not, or I would have done so. For example, I've now changed it to code
that will *compile* portably, but will not *function* optimally. On platforms
that don't have a 64 bit integer, the code will produce incorrect results. In
fact, because of the way it was written, it will actually fail using the native
compilers on Sparc, MIPS, PA-RISC and Alpha even though *ALL* those CPUs have
64bit integers with all the right ALUs.
[...] All that was required, IMHO, was a little note: "__int64 is not
standard C. Replace it with some type that has 64 or more bits of integer
precision on your system."
Well, that's what I started with. There still a note there.

I am not typically prone to writing non-portable code just for the fun of
it. Using __int64 is not a "performance concern" (it rarely is) -- its a
functionality consideration. Using "long int" which may be implemented by
a compiler to be 32 bits, is not an acceptable compromise -- it would
reduce the correctness of the algorithm to a range of <65536 (the Sieve of
Eratosthenes, by itself can easily go beyond this.)
Given a suitably Turing-complete programming language, *everything* is a
performance concern. ;-) In this case, one portable alternative would be to
compute the "widening multiply" in halves (most significant and least
significant 32-bit sections).

And how will that help the fact that there is also a shortening divide in
there?

A bignum divide that I have written on top of a bignum multiply is 98 lines
with a big while-loop around most of it. And that's only because I realized
that you could use FP approximations to sneakily perform the estimation step.
Of course, its a modulo divide so there's probably a better approach, but
either way its not going to be very pretty.

That's the alternative to the 1-line divide in the source I showed.

I would have brought this up earlier, but people in this newsgroup have enough
trouble understanding widening multiplies, I didn't think bringing this up was
exactly going to register with anyone.
[...] I don't know how you would do this in C, but I assure you it can be
done.
Its algebra:

((a<<16) + b) * ((c<<16) + d) == ((a*c)<<32) + ((a*d + b*c)<<16) + b*d

I'm the last person that needs to be assured that this can be done.
Richard, in his flamboyant way, suggests bignums. :)
No -- in his *hyppocritical* way, he suggest bignums. Making bignums portable
is tantamount to reducing it to the Turing machine that you suggested tongue
in cheek. At some point you have to stop and recognize when a programming
language has failed you, and in the case of ANSI C, bignum-like issues show it
for all its inadequacies.

This is the whole "widening multiply" thing all over again (which I
won't regurgitate here, as it always seems to take 10 posts of
explanation before people "get it".)
I think I get it, and I know why you used __int64 in the first place.

You do? You seemed to have missed the shortening divide that's in there.
[...] I merely think that you should have given a slightly larger nod to
portability before posting the code in a group dedicated to *portable* code.

<snip> 80+ bit FP implementations). And I threw in some "guesswork code" about
how it might work on gcc.

<OT> Does gcc have C99's type int64_t (or whatever it really is)? </OT>

Who cares? C99 is *far* less portable than anything I've written.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[Richard Heathfield]

Paul Hsieh wrote:

<snip>

Richard, in his flamboyant way, suggests bignums. :)
No -- in his *hyppocritical* way, he suggest bignums.

I don't deny being any less susceptible to hypocrisy than the next man (and
it would be hypocritical to claim otherwise), but your claim that a
suggestion to use bignums is somehow hypocritical has completely flummoxed
me.
Making bignums portable is tantamount to reducing it to the Turing
machine that you suggested tongue in cheek.
Actually, it isn't all that difficult to make bignums portable. There is no
particular reason why you shouldn't be able to implement, say, RSA using
code that will work on any conforming hosted implementation (and, indeed,
on freestanding implementations if they have the RAM for it; if you have a
few kilobytes, you can do it).
At some point you have to stop and recognize when a programming
language has failed you, and in the case of ANSI C, bignum-like issues
show it for all its inadequacies.

About the only nuisance I've encountered in this regard is the lack of
operator overloading which, in this particular field, would be very welcome
indeed.

<snip>

--
Richard Heathfield : bi****@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

[osmium]

Richard Heathfield writes:

Paul Hsieh wrote:

<snip>

Richard, in his flamboyant way, suggests bignums. :)
No -- in his *hyppocritical* way, he suggest bignums.

I don't deny being any less susceptible to hypocrisy than the next man

(and it would be hypocritical to claim otherwise), but your claim that a
suggestion to use bignums is somehow hypocritical has completely flummoxed
me.

Making bignums portable is tantamount to reducing it to the Turing
machine that you suggested tongue in cheek.
Actually, it isn't all that difficult to make bignums portable. There is

no particular reason why you shouldn't be able to implement, say, RSA using
code that will work on any conforming hosted implementation (and, indeed,
on freestanding implementations if they have the RAM for it; if you have a
few kilobytes, you can do it).

I am just an innocent bystander here. But you, Richard, seem to be
comparing a program that *could* be written with one that *has* been
written. I notice you always refer to bignum in the future tense. If you
are speaking of an actual library it most likely has an actual name and a
parent. My guess is that is where the alleged hypocrisy comes in.

If I were to write a reasonably fast bignum library I would sure like to see
that well hidden carry bit.

[Mark McIntyre]

On Wed, 10 Dec 2003 03:06:57 GMT, in comp.lang.c , glen herrmannsfeldt
<ga*@ugcs.caltech.edu> wrote:

Arthur J. O'Dwyer wrote:

(snip)

To Richard: Note that Paul did address this problem in a
comment buried in the code. If I were to use his code in a
project, I'd make sure to read all the comments before starting
to compile it.

It just occurred to me how nice it would be to have a statement,
probably for the preprocessor, that would cause a message to
be printed when it compiled. Such warnings could then be
put in that way.

many compilers offer an extension #warning. I tend to use it to
document places I'd like to do better work on, but don't have time to
address right now.
--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.angelfire.com/ms3/bchambless0/welcome_to_clc.html>
----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---

[Jim]

On Wed, 10 Dec 2003 05:12:12 GMT, glen herrmannsfeldt
<ga*@ugcs.caltech.edu> wrote:

Dik T. Winter wrote:

In article <g5wBb.71820$_M.359005@attbi_s54> glen herrmannsfeldt writes:
...

> It would seem that preprocessed C could also have messages
> that need to be printed.
>
> #ifdef NUM<0
> #note Oops, NUM is less than zero!
> #else
> int x[NUM];
> #endif

#if NUM<0
#error Oops, NUM is less than zero!
#else
int x[NUM];
#endif

Not quite what I wanted. That seems to cause a fatal error.

I suppose the example isn't very good, but there are cases when
a warning, or even less. Maybe just a reminder to the person
compiling the program.

-- glen

Some compilers do this with a pragma. Two compilers I'm using allow
this:
#pragma message("remember to initialise this structure!")

Jim

[Richard Heathfield]

osmium wrote:

Richard Heathfield writes:

Actually, it isn't all that difficult to make bignums portable. There
is no particular reason why you shouldn't be able to implement, say,
RSA using code that will work on any conforming hosted implementation
(and, indeed, on freestanding implementations if they have the RAM
for it; if you have a few kilobytes, you can do it).
I am just an innocent bystander here. But you, Richard, seem to be
comparing a program that *could* be written with one that *has* been
written.

Well, if he'd written a portable bignum program already, he'd have said so,
wouldn't he?
I notice you always refer to bignum in the future tense. If you
are speaking of an actual library it most likely has an actual name and a
parent. My guess is that is where the alleged hypocrisy comes in.
Ah, I see. Well, we already have Miracl and GMP, do we not? And yes, I have
my own bignum library, which works (except for Rabin-Miller, which I hope
to fix today), but which is still a bit untidy, which is why I haven't
published it yet. The fastest in the world it ain't (because the emphasis
is on readability and portability), but it's fast enough that it is
unlikely to be the bottleneck in typical usages.
If I were to write a reasonably fast bignum library I would sure like to
see that well hidden carry bit.

Perhaps I'm talking through ignorance here, despite having written one
myself, but why would anyone need to *hide* a carry bit?

--
Richard Heathfield : bi****@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

[Grumble]

Jim wrote:

glen herrmannsfeldt wrote:

Dik T. Winter wrote:

glen herrmannsfeldt wrote:
...
It would seem that preprocessed C could also have messages
that need to be printed.

#ifdef NUM<0
#note Oops, NUM is less than zero!
#else
int x[NUM];
#endif

#if NUM<0
#error Oops, NUM is less than zero!
#else
int x[NUM];
#endif

Not quite what I wanted. That seems to cause a fatal error.

I suppose the example isn't very good, but there are cases when
a warning, or even less. Maybe just a reminder to the person
compiling the program.

Some compilers do this with a pragma.

Some have a #warning preprocessor directive.
http://gcc.gnu.org/onlinedocs/cpp/Diagnostics.html

[osmium]

Richard Heathfield <do******@address.co.uk.invalid> wrote in message
news:br**********@hercules.btinternet.com...

osmium wrote:

Richard Heathfield writes:

Actually, it isn't all that difficult to make bignums portable. There
is no particular reason why you shouldn't be able to implement, say,
RSA using code that will work on any conforming hosted implementation
(and, indeed, on freestanding implementations if they have the RAM
for it; if you have a few kilobytes, you can do it).
I am just an innocent bystander here. But you, Richard, seem to be
comparing a program that *could* be written with one that *has* been
written.

Well, if he'd written a portable bignum program already, he'd have said

so, wouldn't he?

I notice you always refer to bignum in the future tense. If you
are speaking of an actual library it most likely has an actual name and a parent. My guess is that is where the alleged hypocrisy comes in.
Ah, I see. Well, we already have Miracl and GMP, do we not? And yes, I

have my own bignum library, which works (except for Rabin-Miller, which I hope
to fix today), but which is still a bit untidy, which is why I haven't
published it yet. The fastest in the world it ain't (because the emphasis
is on readability and portability), but it's fast enough that it is
unlikely to be the bottleneck in typical usages.

If I were to write a reasonably fast bignum library I would sure like to
see that well hidden carry bit.

Perhaps I'm talking through ignorance here, despite having written one
myself, but why would anyone need to *hide* a carry bit?

From the Miracl page:

"MIRACL is compact, fast and efficient and its
now easier than ever to get the same near-optimal
performance from any processor. Although
essentially a portable library, inline assembly
and special techniques can be invoked for
blistering speed"

It would seem to me that the designers of Miracl also wanted to see that
carry out bit which the designers of the C language hid. And the inline
assembly destroys the portability. It is not clear to me that a sensible,
fast, binary, arithmetic big numbers library is possible. I say binary to
exclude BCD arithmetic which is a different kettle of fish. I read
"blistering speed" as meaning reasonably fast.

I will let someone else research GMP. My algorithm is first in, first out.

If I were designing C, I would have considered adding the carry out (and
perhaps other things) as a standard signal. But even so, the resulting big
numbers library would still be slower than necessary.

[Wolfgang Riedel]

Paul Hsieh wrote:

Arthur J. O'Dwyer says...

On Wed, 10 Dec 2003, Richard Heathfield wrote:

Paul Hsieh wrote:
> Arthur J. O'Dwyer says:

<snip> Richard, in his flamboyant way, suggests bignums. :)
No -- in his *hyppocritical* way, he suggest bignums.

Paul,

maybe, he has every right, to be critical of hippos?!

Btw., I think, you do yourself no good with those hypocritical
ad hominem attacks.

Let's stay civilized.

Wolfgang

<snip> --
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

[Chris Torek]

In article <br************@ID-179017.news.uni-berlin.de>
osmium <r1********@comcast.net> writes:

If I were designing C, I would have considered adding the carry out (and
perhaps other things) as a standard signal.

Carry-out of unsigned addition of two operands is trivial to pick
up:

unsigned long a, b, result;
int carry;

result = a + b;
carry = result < a; /* or result < b */

In assembly languages for CPUs without carry flags (e.g., MIPS),
this C code is often a direct translation of the required
assembly code:

addu rRESULT, rA, RB # set register RESULT = A + B
slt rCARRY, rRESULT, rA # set register CARRY = RESULT < A

and on CPUs with carry flags, a compiler should be able to optimize
the "carry = " operation appropriately. If the carry is then fed
into a subsequent op:

r2 = a2 + b2 + carry;

it should even be able to emit an "ADC" instruction, if one exists.
Of course, obtaining carry-out of 3-or-more operand add instructions
is more difficult to achieve, but quite a few modern CPUs have no
three-operand-input operations (including no "add with carry"
instructions; indeed, MIPS, as mentioned above, has no carry flag
at all). Still:

carry = r2 < a2 || (r2 == a2 && carry);
/* or equivalently, carry = (r2 < a2) | ((r2 == a2) & carry); */

(since "carry" is either 0 or 1 initially).

(Whether your compiler does such optimizations is another question
entirely. If those optimizations are important to you, I suggest
that you could put some time, money, and/or effort into seeking
out -- or creating, e.g., by modifying gcc -- compilers that do
them.)

(V9 SPARC points out one reason MIPS does not have a carry flag.
V8 and earlier had only the "condition codes" register, %cc, with
the usual four condition codes: N V C and Z => negative, overflow,
carry, and zero. V9 has %icc, the 32-bit condition codes, and
%xcc, the 64-bit condition codes. A 64-bit register holding a
result of 0x0000000087654321 is negative in 32-bits, but positive
in 64-bits. The sum of 0x00000000ffffffff and 0x00000000ffffffff
is 0x00000001fffffffe, which has no carry in 64-bits but a carry
in 32-bits.)
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) [phone]
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.