I finally got the Wilson approximation to work correctly.
Taking out some of the terms of the stirling approximation:
Below I have calculated the actual and the
stirling approximation and the actual value
of factorial for 10, 100, 1000, 10000, 100000 and 1 billion
Note as the number increases the relative difference is
going down.
-------------factorial(10)--------------
(10 * ln 10) - 10
13.0259
ln ! 10
15.1044
-------------factorial(100)--------------
(100 * ln 100) - 100
360.517
ln ! 100
363.739
-------------factorial(1,000)--------------
(1000x * ln 1000x) - 1000x
5907.76
ln ! 1000x
5912.13
--------------factorial(10,000)-----------
ln ! 10000x
82108.9
(10000x * ln 10000x) - 10000x
82103.4
---------------factorial(100,000)---------
ln ! 100000x
1.0513e6
(100000x * ln 100000x) - 100000x
1.05129e6
NB. approximate factorial 1 billion
(10^11 * ^. 10^11) - 10^11
4.10012e278
So given the merseme prime of 43112609, the approximate
calculation for its factorial using the wilsons
approximation:
since p is 43112609, I need to calculate !(p-1)
!(p) is calculated as follows:
(43112609 * ^. 43112609) - 43112609
7.14778e8
so !(p-1) is calculated by:
(43112608 * ^. 43112608) - 43112608
7.14778e8
Now my thoughts are, how can I use the approximation of
!(p-1)
in Wilson Formula.
Wilson's theorem states that p > 1 is a prime number if and
only if
!(p-1) congruent -1 (mod p)
hum........
Any comments would be appreciated.
thanks
----- Original Message Follows -----
From: Roger Hui <[email protected]>
To: Programming forum <[email protected]>
Subject: Re: [Jprogramming] how to speed up 2^N where N >
10,000,000
Date: Sun, 01 Mar 2009 06:50:46 -0800
>http://www.jsoftware.com/jwiki/Essays/Stirling's_Approximation
>
>
>
>----- Original Message -----
>From: [email protected]
>Date: Saturday, February 28, 2009 22:48
>Subject: Re: [Jprogramming] how to speed up 2^N where N >
>10,000,000 To: Programming forum
><[email protected]>
>
>> Maybe using Stirlings approximation of the prime of a
>> large number would be useful.
>>
>> ln !(N) = N ln N - N where N is some large number
>>
>> I found this on:
>>
>>
>http://hyperphysics.phy-astr.gsu.edu/hbase/math/stirling.html
>>
>> In J I thought it was:
>>
>> (N * ( ln N )) - N
>>
>> My idea is to compute the approximation of the desired
>> factorial with
>> the stirling approximation.
>>
>> Then use it in some manner in the wilson formula.
>>
>> Yes I know, it won't work.
>>
>> Anyhow, I haven't been able to get my code for the
>> stirling approximation
>> to return reasonable results
>>
>> n =: 7
>> strlAprox =: (n * ^. n) - n
>>
>> strlAprox
>> 6.62137
>>
>> ^. ! 7
>> 8.52516
>>
>> As you can see, my stirling approximation is off by a
>> bunch.
>> Anybody?
>>
>> ----- Original Message Follows -----
>> From: Tracy Harms <[email protected]>
>> To: Programming forum <[email protected]>
>> Subject: Re: [Jprogramming] how to speed up 2^N where N >
>> 10,000,000
>> Date: Sat, 28 Feb 2009 17:48:50 -0800
>>
>> >Hi, Butch,
>> >
>> >Several tests to determine whether a number is prime are
>> >detailed in the J wiki, here:
>> >
>> >http://www.jsoftware.com/jwiki/Essays/Primality%20Tests
>> >
>> >The Wikipedia article on Wilson's theorem says:
>> >"Wilson's theorem is useless as a primality test in
>> >practice, since computing (n - 1)! modulo n for large n
>> >is hard, and far easier primality tests are known"
>> >
>> >That recognized, we can of course code that test in J.
>> >Hope it doesn't deflate any of your efforts to do so for
>> >me to post my solutions here.
>> >
>> > wilsonX=: verb :'=/ y | _1 , ! y-1x'"_1
>> > wilson0=: (] | _1:) = ] | 1x !...@-~]
>> >
>> > }.I. wilsonX i. 55
>> >2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53
>> > }.I. wilson0 i. 55
>> >2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53
>> >
>> > NB. compare:
>> > I. 1 p: i.55
>> >2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53
>> >
>> >It's important to note that p: is a primary verb within
>> >J. Beyond that, the tests on the previously mentioned
>> >wiki page may the most applicable to your quest.
>-----------------------------------------------------------
>----------- For information about J forums see
>http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
