[Jprogramming] Trying to handle large factorials -- odd error

[Henry Rich]

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: programming-bounces at jsoftware.com 
> [mailto:programming-bounces at jsoftware.com] 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: programming-bounces at jsoftware.com 
> > [mailto:programming-bounces at jsoftware.com] 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: programming-bounces at jsoftware.com 
> > > [mailto:programming-bounces at jsoftware.com] 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