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
