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. > >Tracy >----------------------------------------------------------- >----------- For information about J forums see >http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
