a little help please; fermat's theorem, program [JavaScript]

Prev: analysing a program's performance
Next: any javascript expert out there? help please!

From: transkawa on 8 Jun 2010 13:51

i wrote this here little program and it gives me misleading result. can
someone help confirm for me if my code is wrong or just because of the
nature of the test. it's a test for primality of a number using fermat's
little theorem.
the following functions are okay; they were embedded from another
program I wrote: square, fastExpt, evenOrNot and evenN.
I just want to confirm only on the fermatTest(n) function.
sorry for the long verbose below:
/*
* program for fermat's test for primality. if n is prime and a is any
positive
* integer less than n, then a raised to the nth power is congruent to
* a modulo n.
*/
function fermatTest(n){
//get a random number between 1 and n-1 inclusive
var rand = Math.random()* (n - 1);
//raise to power of n
rand = fastExpt(rand,n);
if ( rand % n == rand ){ //if congruent
return ' is prime ';
}else{
return ' is not prime ';
}
}
function evenN(b,n){
var x = n/2; //number of times to multiply the base
//multiply the base its number of times
var bresult = 1; //the invariant quantity
for (var i=0; i<x; i++){
bresult = bresult * b; //equivalent to y when loop ends
}
bresult = square(bresult);
return bresult;
}
function square(x) {
return (x * x);
}
//b is base, n is factor to raise it to
function fastExpt(b,n){
var result = 0;
if ( n == 0) return 1;
if (evenOrNot(n)){
//even
result = evenN(b,n)
return result;
}else{
result = evenN(b, n-1);
result = b * result;
return result;
}
}
function evenOrNot(x){
return ( x % 2 == 0);
}
function checkFeat(){
try{
//fermat test
var numberInput = parseInt(prompt('input the number'));
var ops = fermatTest(numberInput);
//return result to three decimal places
document.getElementById('res').value = numberInput + ops;
}
catch(err){
alert('error report: '+ err.toString());
}
}
the html:
<body>
<form action="http://www.example.com/" id="form1">
<input type="button" id="but1" name="but1" value="click this
button!"
onclick="checkFeat();"><br />
<label for="res">Result:</label>
<input type="text" size="20" id="res" >
</form>

</body>

--
Never question, keep asking
234 702 866 8957

From: Scott Sauyet on 8 Jun 2010 15:28

On Jun 8, 1:51 pm, transkawa <transk...(a)yahoo.fr> wrote:
> i wrote this here little program and it gives me misleading result. can
> someone help confirm for me if my code is wrong or just because of the
> nature of the test. it's a test for primality of a number using fermat's
> little theorem.
> the following functions are okay; they were embedded from anotherprogram I wrote: square, fastExpt, evenOrNot and evenN.
>
> I just want to confirm only on the fermatTest(n) function.

> function fermatTest(n){
> //get a random number between 1 and n-1 inclusive
> var rand = Math.random()* (n - 1);
> //raise to power of n
> rand = fastExpt(rand,n);
> if ( rand % n == rand ){ //if congruent
> return ' is prime ';
> }else{
> return ' is not prime ';
> }}

Forgetting the fact that the Carmichael numbers make the Fermat
primality test less than ideal, I think the main problem you're facing
is that Math.random()*(n-1) is not returning an integer. Add a
Math.floor call to that. Then add 1.

A real inefficiency of this is that you're not reducing your nth
powers by your modulus as you proceed. That imposes an unnecessary
restriction on the size of your problem.

--
Scott

From: RobG on 8 Jun 2010 21:59

On Jun 9, 3:51 am, transkawa <transk...(a)yahoo.fr> wrote:
> i wrote this here little program and it gives me misleading result. can
> someone help confirm for me if my code is wrong or just because of the
> nature of the test. it's a test for primality of a number using fermat's
> little theorem.
> the following functions are okay; they were embedded from anotherprogram I wrote: square, fastExpt, evenOrNot and evenN.
>
> I just want to confirm only on the fermatTest(n) function.
> sorry for the long verbose below:

I have no idea about the deeper mathematics, but can comment on some
of the js functions:

> /*
> * program for fermat's test for primality. if n is prime and a is any
> positive
> * integer less than n, then a raised to the nth power is congruent to
> * a modulo n.
> */
> function fermatTest(n){
> //get a random number between 1 and n-1 inclusive
> var rand = Math.random()* (n - 1);

If, as Scott says, the intention is to return an integer, then:

var rand = Math.random()* (n - 1) | 0;

is equivalent to Math.floor and considered faster.

> //raise to power of n
> rand = fastExpt(rand,n);

I don't get the point of fastExpt. I haven't tested it, but I'll bet
that it's much slower than:

rand = Math.pow(rand, n);

> if ( rand % n == rand ){ //if congruent
> return ' is prime ';
> }else{
> return ' is not prime ';
> }}
>
> function evenN(b,n){
> var x = n/2; //number of times to multiply the base
> //multiply the base its number of times
> var bresult = 1; //the invariant quantity
> for (var i=0; i<x; i++){
> bresult = bresult * b; //equivalent to y when loop ends
> }
> bresult = square(bresult);
> return bresult;}
>
> function square(x) {
> return (x * x);}

I don't see the point of creating a function for such a simple
statement, it's almost certainly faster to put it in the caller.

>
> //b is base, n is factor to raise it to
> function fastExpt(b,n){
> var result = 0;
> if ( n == 0) return 1;
> if (evenOrNot(n)){

The evenOrNot function can be simplified to:

!(n%2)

and as with square, would be much faster as an expression in the
caller than a separate function if speed matters.

> //even
> result = evenN(b,n)
> return result;
> }else{
> result = evenN(b, n-1);
> result = b * result;
> return result;
> }}
>
> function evenOrNot(x){
> return ( x % 2 == 0);}
>

The four functions fastExpt(), evenN(), evenOrNot() and square() can
all be replaced by Math.pow(). If you are concerned about the look-up
time, create a local variable such as:

var fastExpt = Math.pow;

and forget the other three functions.

> function checkFeat(){
> try{

I don't understand why you need a try..catch block here.

> //fermat test
> var numberInput = parseInt(prompt('input the number'));

You may want to test numberInput here is not NaN before going further,
there's no point calling fermatTest if you know it will fail. Is that
why you've used try..catch?

> var ops = fermatTest(numberInput);
> //return result to three decimal places
> document.getElementById('res').value = numberInput + ops;
> }
> catch(err){
> alert('error report: '+ err.toString());
> }}
>

--
Rob

From: RobG on 9 Jun 2010 00:10

On Jun 9, 11:59 am, RobG <rg...(a)iinet.net.au> wrote:
> On Jun 9, 3:51 am, transkawa <transk...(a)yahoo.fr> wrote:
[...]
> > //get a random number between 1 and n-1 inclusive
> > var rand = Math.random()* (n - 1);
>
> If, as Scott says, the intention is to return an integer, then:
>
> var rand = Math.random()* (n - 1) | 0;

Ooops:

var rand = (Math.random() * (n-1) + 1) | 0;

The outer brackets aren't required but make it a bit clearer.

--
Rob

From: RobG on 9 Jun 2010 02:31

| Next | Last
Pages: 1 2 3 4
Prev: analysing a program's performance
Next: any javascript expert out there? help please!