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
