Primality by Wilson Theorem

[janus]

# include <stdio.h>


long long int factorial( long long int num){
long long int tempNum ;
long long int acc = 1;
for(tempNum = 1; tempNum < num + 1; ++tempNum){
acc = acc * tempNum;
}
return acc;

}

long long int cosAndFactorial( long long int num){
long long int factValue = factorial(num - 1);
long long int result = (factValue + (long long int)1 ) % num;
return result;

}

int main (){
long long int i;
int pcount = 0;
long long int value;
for( i = 3; i < 1000000; i = i + 2){

value = cosAndFactorial(i);

if((int)value == 0){
++pcount;
printf("Factorial : This number %llu is a Prime\n", i);
}
if(pcount == 10) {
break;
}
}

return 0;
}

I am trying to code Wilsons Theorem, http://mathworld.wolfram.com/WilsonsTheorem.html?affilliate=1
The above returns;
Factorial : This number 3 is a Prime
Factorial : This number 5 is a Prime
Factorial : This number 7 is a Prime
Factorial : This number 11 is a Prime
Factorial : This number 13 is a Prime
Factorial : This number 17 is a Prime
Factorial : This number 19 is a Prime
Factorial : This number 35 is a Prime


Regards, \Janus

 

[Nick Keighley]

# include <stdio.h>

long long int  factorial( long long int num){
        long long int tempNum ;
        long long int acc = 1;
        for(tempNum = 1; tempNum < num + 1; ++tempNum){
                acc = acc * tempNum;
        }
        return acc;

}

 long long int  cosAndFactorial( long long int  num){
        long long int factValue = factorial(num - 1);
        long long int result = (factValue + (long long int)1 ) % num;
        return result;

}

int main (){
        long long  int i;
        int pcount = 0;
        long long int value;
        for( i =  3; i < 1000000; i = i + 2){

                value = cosAndFactorial(i);

                if((int)value == 0){
                        ++pcount;
                        printf("Factorial : This number %llu is a Prime\n", i);
                }
                if(pcount == 10) {
                        break;
                }
        }

return 0;

}

I am trying to code Wilsons Theorem,http://mathworld.wolfram.com/WilsonsTheorem.html?affilliate=1
The above returns;
Factorial : This number 3 is a Prime
Factorial : This number 5 is a Prime
Factorial : This number 7 is a Prime
Factorial : This number 11 is a Prime
Factorial : This number 13 is a Prime
Factorial : This number 17 is a Prime
Factorial : This number 19 is a Prime
Factorial : This number 35 is a Prime

and?

 

[Alan Curry]

# include <stdio.h>


long long int factorial( long long int num){ [...this part is fine...]
}

long long int cosAndFactorial( long long int num){
long long int factValue = factorial(num - 1);
long long int result = (factValue + (long long int)1 ) % num;
return result;

}

I can't figure out what "cos" means here. Not cosine. "cosine and factorial"
would be a weird concept...

int main (){
long long int i;
int pcount = 0;
long long int value;
for( i = 3; i < 1000000; i = i + 2){

value = cosAndFactorial(i);

You're trying to compute factorials up to 1000000 and fit them in long longs?
That's usually a 64-bit type (63 useful bits since you didn't say
"unsigned"). Even if you find a compiler that'll bump it up to 128 or 256
bits for you, factorials just grow too fast. factorial(20) is the biggest one
that'll fit in 64 bits. factorial(58) is the last one that'll fit in 256
bits.

factorial(1000000) is ridiculous. Even in common floating point types it's
indistinguishable from infinity. If my quick application of Stirling's
approximation is correct, its exact value requires about 18,488,885 bits or
5,565,709 decimal digits.

You can probably compute it with an arbitrary precision arithmetic library,
but that is not an efficient thing to do and not necessary in an
implementation of the Wilson test.

To compute factorial(x) % y, you don't have to actually compute factorial(x)
first. Instead use this identity:

(a*b)%x == (a%x)*(b%x) == ((a%x)*b)%x

in other words, you can apply the modulo operator *during* your factorial
loop, after every multiplication, so you don't need gigantic intermediate
numbers.

The above returns;
Factorial : This number 3 is a Prime
Factorial : This number 5 is a Prime
Factorial : This number 7 is a Prime
Factorial : This number 11 is a Prime
Factorial : This number 13 is a Prime
Factorial : This number 17 is a Prime
Factorial : This number 19 is a Prime

Notice how the results for numbers below 20 are correct!

 

[Noob]

and?

and the primality of 35 has been questioned in the past ;-)

 

[gwowen]

Notice how the results for numbers below 20 are correct!

Alan has covered your problem thoroughly.

It's worth noting that you can alleviate this integer overflow by
noting the identity

(a * b) % m == ((a%m) * (b%m)) % m

so as your factorial grows, you can shrink it again.

/// e.g.
/// NB: probably not the most efficient...
/// Won't overflow for num < sqrt(max long long int)
long long int cosAndFactorial( long long int num)
{
long long int tempNum ;
long long int acc = 1LL;
for(tempNum = 1LL; tempNum < num; ++tempNum){
acc = (acc * tempNum) % (num);
}
return (acc+1)%num;
}

 

[Barry Schwarz]

# include <stdio.h>


long long int factorial( long long int num){
long long int tempNum ;
long long int acc = 1;
for(tempNum = 1; tempNum < num + 1; ++tempNum){
acc = acc * tempNum;

The first iteration contributes nothing to the result. You could
start with tempNum set to 2

}
return acc;

}

long long int cosAndFactorial( long long int num){
long long int factValue = factorial(num - 1);
long long int result = (factValue + (long long int)1 ) % num;

Why the cast? You didn't put a cast in expression-2 of the for loop
in factorial(). The constant would be promoted automatically without
it. If you are really concerned, why not change 1 to 1LL to start
with, though any decent compiler should do that automatically.

return result;

}

int main (){
long long int i;
int pcount = 0;
long long int value;
for( i = 3; i < 1000000; i = i + 2){

value = cosAndFactorial(i);

if((int)value == 0){

Why the cast? Is there some reason you only want to test the low
order 32 bits? Are you aware that every factorial above 33! has at
least 32 low order zeros when expressed in binary. This explains the
result you see for 35.

++pcount;
printf("Factorial : This number %llu is a Prime\n", i);
}
if(pcount == 10) {
break;
}
}

return 0;
}

I am trying to code Wilsons Theorem, http://mathworld.wolfram.com/WilsonsTheorem.html?affilliate=1
The above returns;
Factorial : This number 3 is a Prime
Factorial : This number 5 is a Prime
Factorial : This number 7 is a Prime
Factorial : This number 11 is a Prime
Factorial : This number 13 is a Prime
Factorial : This number 17 is a Prime
Factorial : This number 19 is a Prime

21! requires 66 bits so it does not fit into a 64 bit value. How
large is a long long on your system. Hint: your code did not work for
23.

Even if long long were 128 bits, 34! would not fit.

 

[janus]

wrote:


The first iteration contributes nothing to the result. You could
start with tempNum set to 2


Why the cast? You didn't put a cast in expression-2 of the for loop
in factorial(). The constant would be promoted automatically without
it. If you are really concerned, why not change 1 to 1LL to start
with, though any decent compiler should do that automatically.


Why the cast? Is there some reason you only want to test the low
order 32 bits? Are you aware that every factorial above 33! has at
least 32 low order zeros when expressed in binary. This explains the
result you see for 35.


21! requires 66 bits so it does not fit into a 64 bit value. How
large is a long long on your system. Hint: your code did not work for
23.

Even if long long were 128 bits, 34! would not fit.

Thank you all. I have learnt a couple of things.

 

[Paul]

Thank you all. I have learnt a couple of things.

You could have fun with this.

http://gmplib.org/#WHAT

"GMP is a free library for arbitrary precision arithmetic,
operating on signed integers, rational numbers, and floating point numbers."

It's available for C and C++. The C++ code is easier to read,
but you can write slightly tighter code (reduced memory footprint)
with C. If you're careful, with C, you might shave off the
odd temporary variable, and when numbers have 40 million digits
or more, that can be important.

For an example of using the library, see the C++ example here.
For fun, I re-coded it in C, but continued to use the same library.

http://rosettacode.org/wiki/Lucas-Lehmer_test

It should take you a while to exhaust the capabilities of GMP.
The slowdown, from doing math on large numbers, will see to that

Paul

 

[Ike Naar]

The first iteration contributes nothing to the result. You could
start with tempNum set to 2

But then factorial(1) would no longer work.

 

[Ike Naar]

But then factorial(1) would no longer work.

Whoops, brain fart. Sorry.

 

[janus]

You could have fun with this.

http://gmplib.org/#WHAT

"GMP is a free library for arbitrary precision arithmetic,
operating on signed integers, rational numbers, and floating point numbers."

It's available for C and C++. The C++ code is easier to read,
but you can write slightly tighter code (reduced memory footprint)
with C. If you're careful, with C, you might shave off the
odd temporary variable, and when numbers have 40 million digits
or more, that can be important.

For an example of using the library, see the C++ example here.
For fun, I re-coded it in C, but continued to use the same library.

http://rosettacode.org/wiki/Lucas-Lehmer_test

It should take you a while to exhaust the capabilities of GMP.
The slowdown, from doing math on large numbers, will see to that

Paul

Thanks

 

[Robert Miles]

# include<stdio.h>


long long int factorial( long long int num){
long long int tempNum ;
long long int acc = 1;
for(tempNum = 1; tempNum< num + 1; ++tempNum){
acc = acc * tempNum;
}
return acc;

} [snip]
Regards, \Janus

Maybe you'd like to know about a BOINC project that is calculating
primes using Wilson's theorem. Source code is available, but I
haven't checked if it's written in C.

The main site, with descriptions in Spanish:

http://www.ibercivis.es/

Descriptions of their subprojects in English:

http://www.ibercivis.net/index.php?...els&action=view&id_channel=3&id_subchannel=33

The section on their Wilson primes subproject:

http://www.ibercivis.net/index.php?...ls&action=view&id_channel=2&id_subchannel=138

There's also a site with the descriptions in Portuguese; I don't have
the link handy.

Robert Miles

 

[88888 Dihedral]

Robert Milesæ–¼ 2012å¹´3月31日星期六UTC+8下åˆ1時38分09秒寫é“：

# include<stdio.h>


long long int factorial( long long int num){
long long int tempNum ;
long long int acc = 1;
for(tempNum = 1; tempNum< num + 1; ++tempNum){
acc = acc * tempNum;
}
return acc;

} [snip]
Regards, \Janus

Maybe you'd like to know about a BOINC project that is calculating
primes using Wilson's theorem. Source code is available, but I
haven't checked if it's written in C.

The main site, with descriptions in Spanish:

http://www.ibercivis.es/

Descriptions of their subprojects in English:

http://www.ibercivis.net/index.php?...els&action=view&id_channel=3&id_subchannel=33

The section on their Wilson primes subproject:

http://www.ibercivis.net/index.php?...ls&action=view&id_channel=2&id_subchannel=138

There's also a site with the descriptions in Portuguese; I don't have
the link handy.
are
Robert Miles

If all primes less than n and the series of prime products of the first prime to the last prime are known in constants for n! within a 64-bit register, then the above code is too slow.
then it can speed a lot for the factorial computation