f2 =: 100000&|@*/ @: (0.5&([`(5 I.@:= ])`]})&.q:) Horribly inefficient way to divide by 5 but I wondered if it would work.
f2 >:i.1000000 12544 Henry Rich > -----Original Message----- > From: [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED] On Behalf Of Henry Rich > Sent: Thursday, March 27, 2008 2:18 PM > To: 'Programming forum' > Subject: RE: [Jprogramming] Trying to handle large factorials > -- odd error > > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
