Prev: analysing a program's performance
Next: any javascript expert out there? help please!
From: Scott Sauyet on 10 Jun 2010 15:13
Stefan Weiss wrote:
> 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.

Oh, if you're having trouble with your margins, there's this wonderful
DOM library that can help. It was written by Andrew Wiles based on
work from Yukata Taniyama and involves ingenious use of non-modular
elliptic curves.

Thanks for the laugh!

--
Scott
From: RobG on 10 Jun 2010 17:17
On Jun 10, 3:47 pm, Stefan Weiss <krewech...(a)gmail.com> wrote:
[...]
> 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.

Oh, that would be Weiss' last theorem? :-)


--
Rob
From: Dr J R Stockton on 10 Jun 2010 10:46
In comp.lang.javascript message <248c82b8-021d-499e-9413-8d80fda5dcf3(a)h3
7g2000pra.googlegroups.com>, Tue, 8 Jun 2010 21:10:07, RobG
<rgqld(a)iinet.net.au> posted:

>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.

Transpose the operands of the + and it will not need to be clearer

On a PC, ERATOST3 can list more prime numbers than you are likely to
want to remember, as will, somewhat slower,
<URL:http://www.merlyn.demon.co.uk/js-misc0.htm#SE>.

I wonder what the largest prime ECMAScript Number is? 2^53-1 has factors
6361 69431 20394401.

--
(c) John Stockton, nr London, UK. ?@merlyn.demon.co.uk Turnpike v6.05 MIME.
Web <URL:http://www.merlyn.demon.co.uk/> - FAQqish topics, acronyms & links;
Astro stuff via astron-1.htm, gravity0.htm ; quotings.htm, pascal.htm, etc.
No Encoding. Quotes before replies. Snip well. Write clearly. Don't Mail News.
From: Dr J R Stockton on 11 Jun 2010 16:58
In comp.lang.javascript message <58ce556e-67b7-4c97-8e18-5e38e4411bfd(a)11
g2000prw.googlegroups.com>, Wed, 9 Jun 2010 17:36:51, RobG
<rgqld(a)iinet.net.au> posted:

>
>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?


Web <URL:http://www.merlyn.demon.co.uk/js-misc0.htm#CDC> contains some
of the sort of code that would be in such a library.

IMHO, one should use arrays of digits rather than strings. But note
that a UniCode string has base-65536 elements, and could be used as such
if all are *possible* in any order.

If you are old enough, you will have been taught how to do arithmetic on
large numbers (i.e. > 9) using the tables for non-large numbers that you
had previously been taught. Years ago, I once consulted an older friend
about school square root (not taught in my tile AFAIR); that algorithm
was then used on an 8-bit machine as part of the national measurement
system.

<URL:http://www.merlyn.demon.co.uk/programs/longcalc.pas> does it;
either read it or write a Pascal interpreter in JavaScript! Longcalc is
programmable in RPN, using TLAs.

Make the base/radix a variable; then you can test with base 10 and later
gain speed with larger bases. The base should be less than the square
root of MAXINT, to allow multiplication; bases 10^6 or 2^20 would be
useful.

Given your apparent programming ability and the skill level that library
writers seem to possess, I suggest writing your own.

One trick : there is a way of multiplying long numbers which is quicker
than taught in schools. To school-multiply AB and CD (where A B C D are
multi-digit, and the school way needs 4 units of "*") one does three
multiplications of combinations of A B C D and some additions and/or
subtractions, which is faster. Now recurse to handle each of the three
smaller multiplications ...

--
(c) John Stockton, near London. *@merlyn.demon.co.uk/?.?.Stockton(a)physics.org
Web <URL:http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links.
Correct <= 4-line sig. separator as above, a line precisely "-- " (RFC5536/7)
Do not Mail News to me. Before a reply, quote with ">" or "> " (RFC5536/7)
From: transkawa on 23 Jun 2010 06:43
In article <7a83765e-a9d5-4e44-ae5e-b25db79e53e2@
11g2000prw.googlegroups.com>, rgqld(a)iinet.net.au says...
>
> 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

won't pick up the bet on fastExpt but I know Math.pow exists. Just
wanted it that way. context issues.
the square function was thrown away. don't see the point myself after
reading your post. thanks.
I think i might have to disagree with your input on the evenOrNot
function. the modulus function returns a number and the conditional is
not checking for *existence* of the modulus but rather whether 0 or
something other than 0 was returned.
as for the try...catch, file was used for something else with a
try...catch and while working decided to allow it be; just in case i
have an err. thanks anyway.

--
Never question, keep asking
234 702 866 8957
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4
Prev: analysing a program's performance
Next: any javascript expert out there? help please!