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
