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
