[Jprogramming] LCM performance

['Mike Day' via Programming]

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 <donguinn at 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