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

[Geoff Canyon]

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
>