Oh, wait, 1000000 has one more zero than 100000, so that won't work. How about: first process the i. 1000000 by dividing every power of 5 by 10 (so you have 1 2 3 4 0.5 6 7 8 9 1 11 ...); then (optionally) limit those values to 5 digits; then do 100000&|@*/
Make sure you turn 25 into 0.25, 125 into 0.125, etc Henry Rich > -----Original Message----- > From: [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED] On Behalf Of Henry Rich > Sent: Thursday, March 27, 2008 1:31 PM > To: 'Programming forum' > Subject: RE: [Jprogramming] Trying to handle large factorials > -- odd error > > Only the low 5 digits of each input number contribute, so once you > get up to 100000 you can use those results to calculate higher > values quickly. > > Henry Rich > > > -----Original Message----- > > From: [EMAIL PROTECTED] > > [mailto:[EMAIL PROTECTED] On Behalf Of Geoff Canyon > > Sent: Thursday, March 27, 2008 11:18 AM > > To: Programming forum > > Subject: Re: [Jprogramming] Trying to handle large factorials > > -- odd error > > > > Thanks for the tip! I solved my problem by switching to > > > > f =: (((|.&.":)@(5{.":&(".@(,&'x')@|.&":)))@*)/ > > > > I should have been more clear. I'm talking _very_ large > factorials: > > 100,000 up to perhaps a million. For numbers like those, > > simply doing ! > > 100000x and then extracting the last five non-zero digits > is at best > > inefficient and likely a go-make-a-cup-of-coffee proposition. > > > > At each step, only the last five non-zero digits need to be > kept, so > > for example, rather than multiplying 10001 by !10000x (a > 35660-digit > > number) and then getting the digits I want, I just multiply > 10001 by > > 79008 (the last five non-zero digits of !10000x) to get the > > last five > > non-zero digits of !10001. At least, that's the plan. > > > > And it seems to work: > > > > f =: (((|.&.":)@(5{.":&(|.&.":)))@*)/ > > Ts 'f >:i.5000x' > > 0.0493279 782208 > > Ts 'f >:i.6000x' > > 0.059438 918400 > > Ts 'f >:i.7000x' > > 0.0696259 1.05459e6 > > > > So I don't like the storage requirements, but the time > taken appears > > to be scaling roughly linearly, which it doesn't come near > to doing > > with actual factorials. Looking at it more concretely, consider my > > code vs. ! for 10000x: > > > > Ts 'f >:i.10000x' > > 0.0983548 1.56147e6 > > Ts '!10000x' > > 1.08737 1.01062e6 > > > > My code is 100 times faster, although it takes more space. > I figure > > that the way to solve both the space issue might be to switch to a > > recursive function. > > > > regards, > > > > Geoff > > > > > > On Mar 26, 2008, at 10:40 PM, bill lam wrote: > > > You need to add the trailing 'x' to the formatted number. > > > I'm unskillful in writing tacit form but the following seems > > > implementing your logic. > > > _5{. |. ": ". ,&'x' |. ": */ 1+i.10x > > > 36288 > > > _5{. |. ": ". ,&'x' |. ": */ 1+i.20x > > > 17664 > > > _5{. |. ": ". ,&'x' |. ": */ 1+i.10050x > > > 69696 > > > > > > btw I think that ! should be more efficient than */@:>:@:i. > > > > > > Geoff Canyon wrote: > > >> I'm trying to find the last five non-zero digits of a large > > >> factorial. So for: > > >> !10x = 3628800 > > >> the answer would be 36288 while for: > > >> !20x = 2432902008176640000 > > >> the answer would be 17664. > > >> I'm trying to do this by calculating /* 1+i.1000 without > > >> calculating large numbers by losing the trailing zeroes at each > > >> step and the leading digits more than five. Here's what > I have so > > >> far: > > >> (((|.&.":)@(5{.":&(|.&.":)))@*)/ 1+i.20x > > >> The truncating code: > > >> -- Converts to string, transposes, and converts back to > a number. > > >> That loses trailing zeroes (because they're now leading zeroes). > > >> -- Converts to string and grabs the first five > characters (which > > >> were the last five non-zero digits). > > >> -- Converts to string again -- not sure why this is > > necessary, but > > >> it doesn't work otherwise -- transposes, and converts back to a > > >> number. > > >> This whole thing is performed atop *, and the resulting verb is > > >> inserted into the list from 1 to a large number. > > >> This seems to work for large numbers up to 10049x. At > > 10050x I get > > >> an ill-formed number error. > > >> Where did I go wrong? > > >> regards, > > >> Geoff > > >> > > > ---------------------------------------------------------------------- > > >> For information about J forums see http://www.jsoftware.com/ > > >> forums.htm > > > > > > > > > ---------------------------------------------------------------------- > > > For information about J forums see > > http://www.jsoftware.com/forums.htm > > > > > > > > ---------------------------------------------------------------------- > > For information about J forums see > > http://www.jsoftware.com/forums.htm > > ---------------------------------------------------------------------- > For information about J forums see > http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
