Presumably it's the usual trade-off between whole array programming and
the loopy approach.
It must* be worth truncating the logarithm when in a loop, or indeed,
doing two consecutive loops,
from 2 to ~ sqrt n, and then from > ~ sqrt n to n; less useful when
working on the whole array.
*Having said that, I thought I should try it, so here goes in another
interpreted language, Pari GP;
the results aren't that impressive:
(10:02) gp >
(10:03) gp > \\ one loop from 2 to n
(10:03) gp > lcm1(n) = {my(l=1,pow,logn=log(n)); \\ don't really need
variable "pow"
forprime(p=2, n,
l*=p^(pow=logn\log(p)); \\ base e logs only, I think.
);
l;
}
(10:03) gp >
(10:03) gp > \\ two loops, from 2 to ~ sqrt(n) and from sqrt(n) to n
(10:03) gp > lcm2(n) = {my(l=1,pow,logn=log(n));
forprime(p=2, sqrt(n)\1,
l*=p^(pow=logn\log(p));
);
forprime(p=1+sqrt(n)\1, n, \\ no logs needed
l*=p;
);
l;
}
(10:04) gp > lcm1(100)==lcm2(100) \\ same results
%16 = 1
(10:04) gp > #lcm1(1000000) \\ time for 10^6
time = 7,329 ms.
%17 = 22533
(10:04) gp > #lcm2(1000000) \\ time for 10^6 , two loops
time = 5,719 ms.
%18 = 22533
(10:05) gp > lcm1(100) \\ correct result, by the way!
%19 = 69720375229712477164533808935312303556800
Also, trying Pari GP's lcm primitive, which only admits two arguments,
(10:13) gp > l=1; for(i=2,1000000, l=lcm(l,i)); #l \\ explicit loop
for 10^6
*** at top-level: l=1;for(i=2,1000000,l=lcm(l,i));#l \\ breaking
with ctrl-C
*** ^------------
*** lcm: user interrupt after 36,532 ms
... so there's no great improvement here from square root stunt(ing). I
could compile a Fortran or
C program, but I'm inclined to leave that to others!
Mike
On 11/03/2019 16:46, Raul Miller wrote:
Yeah, looks like I wasn't saving any significant time with that square
root stunt on the logarithm calculation.
Thanks,
On Mon, Mar 11, 2019 at 12:38 PM Don Guinn <dongu...@gmail.com> wrote:
6!:2 'n=:*/p^<.y^.~p=.p:i._1 p:y=.100000x'
0.690272
40{.":n
6952838362417071970003075865264183883398
[rest of thread omitted by Thunderbird...]
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
