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

Arie Groeneveld Thu, 03 Apr 2008 10:31:09 -0700

Going explicit with special code m&|@^

z5n017=: 3 : 0
 m2=. -/2 5 (+/@}.@(<[EMAIL PROTECTED]:a:))"0 y
 p=. 3,3}.i.&.(_1&p:)y
 m=. p (+/@}.@(<[EMAIL PROTECTED]:a:))"0 y
 100000&|@*/(2,p) (100000&|@^) m2, m
)


  5 ts 'z5n017 1e6'
0.6990236 2624960

  5 ts 'f2 >:i. 1e6'
7.24984 90118592

  (z5n017-:(f2@:>:@:i."0))1e6
1


=@@i


Henry Rich schreef:

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 thelast fivenon-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 seemsimplementing 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 largefactorial. 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 withoutcalculating 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 seehttp://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums seehttp://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums seehttp://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

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

Reply via email to