Prev: analysing a program's performance
Next: any javascript expert out there? help please!
From: Scott Sauyet on 9 Jun 2010 10:08
RobG wrote:
> On Jun 9, 3:51 am, transkawa <transk...(a)yahoo.fr> wrote:
>> I just want to confirm only on the fermatTest(n) function.
>
> Checked it out on Wikipedia[1], your fermatTest() function is wrong.

The test once fixed is considered weak evidence that a number is
prime. Done multiple times it increases the likelihood that a number
is prime. But there are pseudoprimes for various bases (every
positive integer > 1?), and there are numbers which are not prime and
yet pass this test for every single base relatively prime to our test
number; these are the "Carmichael numbers". It's not a good test of
primality, but it is one that's generally easy to implement.

--
Scott
From: Scott Sauyet on 9 Jun 2010 10:18
RobG wrote:
> On Jun 9, 3:51 am, transkawa <transk...(a)yahoo.fr> wrote:
>>     //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);

Because the OP is not including the modulus in these calculations,
you're probably right. But this sort of technique can allow you to
quickly calculate the value of fairly large numbers to very high
powers to a certain modulus, which you can't do when you run into
overflow or rounding errors with the standard number objects.

This code, though, was clearly ported from another language and
doesn't take advantage of some of the constructs of Javascript.

Seeing the number of posts made in a row by the OP and the lack of
followup, though, I tend to agree with Thomas that this is some sort
of trolling.

--
Scott
From: RobG on 9 Jun 2010 20:36
On Jun 10, 12:08 am, Scott Sauyet <scott.sau...(a)gmail.com> wrote:
> RobG wrote:
> > On Jun 9, 3:51 am, transkawa <transk...(a)yahoo.fr> wrote:
> >> I just want to confirm only on the fermatTest(n) function.
>
> > Checked it out on Wikipedia[1], your fermatTest() function is wrong.
>
> The test once fixed is considered weak evidence that a number is
> prime. Done multiple times it increases the likelihood that a number
> is prime. But there are pseudoprimes for various bases (every
> positive integer > 1?), and there are numbers which are not prime and
> yet pass this test for every single base relatively prime to our test
> number; these are the "Carmichael numbers". It's not a good test of
> primality, but it is one that's generally easy to implement.

Thanks.

I'm no mathematician, but find implementing this stuff an interesting
challenge. I thought it was more likely that the OP was looking for
answers to a homework question so didn't want to post anything
resembling a solution.

The formula is fairly easy to implement, however the obvious simple
algorithm exceeds the capability of the built-in ECMAScript number
primitives with fairly small numbers. e.g. testing whether 29 is prime
is likely to be wrong about half the time because in processing it,
numbers are generated that are far larger than ECMAScript can safely
handle.

Do you know of any ECMAScript libraries (where "library" is just a
collection of functions) that can be used to deal with large integers?
Or where some reasonably easy to understand algorithms have been
published so I might have a go at creating creating some to do simple
arithmetic with very large numbers?


--
Rob
From: Scott Sauyet on 10 Jun 2010 00:28
RobG wrote:
> On Jun 10, 12:08 am, Scott Sauyet <scott.sau...(a)gmail.com> wrote:
>> RobG wrote:
>>> On Jun 9, 3:51 am, transkawa <transk...(a)yahoo.fr> wrote:
>>>> I just want to confirm only on the fermatTest(n) function.
>
>>> Checked it out on Wikipedia[1], your fermatTest() function is wrong.
>
>> The test once fixed is considered weak evidence that a number is
>> prime.  Done multiple times it increases the likelihood that a number
>> is prime.  But there are pseudoprimes for various bases (every
>> positive integer > 1?), and there are numbers which are not prime and
>> yet pass this test for every single base relatively prime to our test
>> number; these are the "Carmichael numbers".  It's not a good test of
>> primality, but it is one that's generally easy to implement.
>
> I'm no mathematician, but find implementing this stuff an interesting
> challenge. I thought it was more likely that the OP was looking for
> answers to a homework question so didn't want to post anything
> resembling a solution.

It's an interesting enough question, but there is definitely something
odd about the OP's burst of unrelated posts;,

> The formula is fairly easy to implement, however the obvious simple
> algorithm exceeds the capability of the built-in ECMAScript number
> primitives with fairly small numbers. e.g. testing whether 29 is prime
> is likely to be wrong about half the time because in processing it,
> numbers are generated that are far larger than ECMAScript can safely
> handle.

That's why doing the modulus operation after every operation is
useful. That was the point of the attempt at a fast exponent
function.



> Do you know of any ECMAScript libraries (where "library" is just a
> collection of functions) that can be used to deal with large integers?
> Or where some reasonably easy to understand algorithms have been
> published so I might have a go at creating creating some to do simple
> arithmetic with very large numbers?

I don't know of one. I'd be curious to know if one is out there. But
with the modulus operation, it is not actually necessary for the
problem at hand.

--
Scott
From: Stefan Weiss on 10 Jun 2010 01:47
On 10/06/10 06:28, Scott Sauyet wrote:
> RobG wrote:
>> Do you know of any ECMAScript libraries (where "library" is just a
>> collection of functions) that can be used to deal with large integers?
>> Or where some reasonably easy to understand algorithms have been
>> published so I might have a go at creating creating some to do simple
>> arithmetic with very large numbers?
>
> I don't know of one. I'd be curious to know if one is out there.

I haven't worked with one, either, but they're out there.

For example, here's a demo I stumbled across a couple of months ago,
which is actually related to the OP's question - it implements the RSA
algorithm and has an option to choose between probable primes and true
primes:
http://www.leemon.com/crypto/BigInt.html

You can find several other implementations by searching for "javascript
bigint". Obligatory disclaimer: I haven't looked at the source of any of
these libraries.

AFAIK, many (most?) modern arbitrary precision libraries for other
languages are implemented by using base-256 strings as containers. C
might have a problem with that (when such a string contains a null
byte), but many other languages, including C++, Java, and JS, can hold
arbitrary binary data in their string types. In theory, we should be
able to use base-65536 in JS strings. It shouldn't be too hard to create
a library for the most common numeric operations, and I'd be surprised
if there wasn't already something usable out there to build on.

Concerning the primality test required by the OP - I have discovered a
truly marvelous and efficient way to prove beyond a doubt whether a
number is prime. Unfortunately, the margin of this posting is too narrow
to contain it.


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