Roger Hui wrote:
The problem with the phrase that you used,
_10{. ": >: 28433 * 2^7830457x
is that it computes all the 2.36 million (7830457 * 10^.2)
digits of the number, and further computes a 2 million digit
product and a 2 million digit sum, before just taking the
last 10 digits.
Skip Says:
The amazing thing to me was that that phrase
_10{. ": >: 28433 * 2^7830457x
inefficient as it was, worked! I got the answer I wanted, with minimal
programming time.
Sure, that solution was inefficient computationally, and it took awhile
to get the answer,
but my simple mind would have spent hours coming up with an efficient
solution anywhere
close to what Roger presented. It took me less than 20 seconds of
programming time, and less than
15 minutes of processing time (which I spent productively in other
pursuits)to get the answer
I needed.
It is a testament to the efficiency of J (and Moore's law) that even an
inefficient
algorithm can often get the right answer.
Skip
Roger Hui wrote:
Spoiler alert: If you intend to solve MathsChallenge problem
#97 the solution is included below.
On a very pedestrian 500 Mhz Pentium 3 laptop:
ts 'y=: m | >: 28433 * 2 m&|@^ 7830457 [ m=: 10^10x'
0.000663492 16192
y
8739992577
The problem with the phrase that you used,
_10{. ": >: 28433 * 2^7830457x
is that it computes all the 2.36 million (7830457 * 10^.2)
digits of the number, and further computes a 2 million digit
product and a 2 million digit sum, before just taking the
last 10 digits. The fast method just keeps the last 10 digits
at every step.
The phrase m&|@^ is documented in the dictionary page for | :
The dyad m&|@^ on integer arguments is computed in a way that
avoids large intermediate numbers. For example: 2 (1e6&|@^) 10^100x
The last phrase computes the last 6 digits of 10^100x :
ts 'y=: 2 (1e6&|@^) 10^100x'
0.00568536 174784
y
109376
Try that in Maple! The number 2^10^100x has 0.3 googol (3e99)
decimal digits and can not be computed directly. x m&|@^ y
is available in Mathematica as PowerMod[x,y,m] .
----- Original Message -----
From: "John Randall" <[EMAIL PROTECTED]>
To: "Programming forum" <[email protected]>
Sent: Saturday, February 18, 2006 4:23 AM
Subject: Re: [Jprogramming] If Maple can, why can't J?
Here's the timing I get on Maple:
|\^/| Maple 8 (SUN SPARC SOLARIS)
._|\| |/|_. Copyright (c) 2002 by Waterloo Maple Inc.
\ MAPLE / All rights reserved. Maple is a registered trademark of
<____ ____> Waterloo Maple Inc.
| Type ? for help.
time(((28433*2^7830457)+1) mod 10000000000);
0.409
bytes used=21394452, alloc=19329580, time=83.71
Machine hardware: sun4u
OS version: 5.8
Processor type: sparc
Hardware: SUNW,Sun-Fire-880
Best wishes,
John
bill lam wrote:
For the problem 97
http://www.mathschallenge.net/index.php?section=project&ref=problems&id=97
Maple (and also Mathematica) user claimed it could be solved using brute
force
within 30 seconds of computing time.
Can someone verfiy the claim?
Assume it is true, why J cannot calculate the expression within a
reasonable time limit?
_10{. ": >: 28433 * 2^7830457x
Ps. I think this does not give additional information for members
still working with this problem.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
