J's extended precision integer implementation is part of it. But
floating point numbers don't really work for this kind of problem for
anything longer than i.11
But, also, I imagine a part of this also might be that Haskell has
optimizations which improve performance of this kind of problem, which
we don't have in J.
Here's a J approach that gets the solution to this kind of problem a bit faster:
lcmseq=:3 :0
primes=. i.&.(p:inv) y
maxsq=. 1+primes I.%:y
*/primes^x:1>.(#primes){.<.(maxsq{.primes)^.y
)
lcmseq 100000x
6952838362417071970003075865264183883398742917680351135360275375615041442175021237506257986828602047763612877697876454892733660081058707575359683162985199273472095475166897891861381578830560627099383483382709560516260628624180504874681127372319705939469099...
6!:2'lcmseq 100000x'
0.398073
I hope this helps,
--
Raul
--
Raul
On Sun, Mar 10, 2019 at 5:10 PM james faure <[email protected]> wrote:
>
> That, I suspect, can be blamed mostly on the abysmally slow extended
> precision integers in J, and the fact that *. must manipulate these extended
> precision integers more often than other verbs.
>
> Indeed, If you remove the 'x', it runs extremely fast.
> ________________________________
> From: Programming <[email protected]> on behalf of
> Eugene Nonko <[email protected]>
> Sent: Sunday, March 10, 2019 9:00 PM
> To: [email protected]
> Subject: [Jprogramming] LCM performance
>
> I need to find the smallest number that divides all numbers from 1 to n.
> The solution, of course is this:
>
> *./ >: i. n
>
> What I don't understand is why this solution seems to scale so poorly:
>
> 6!:2 '*./ >: i.10000x'
> 0.326128
> 6!:2 '*./ >: i.11000x'
> 1.00384
> 6!:2 '*./ >: i.12000x'
> 4.133
> 6!:2 '*./ >: i.13000x'
> 11.8082
>
> When I perform similar calculation in Haskell it produces result in
> negligible time, even when n = 100,000.
>
> λ: foldr1 lcm [1 .. 100000]
> 695283836241707197000307586...
>
> If I use a verb other than *. it runs very quickly, as expected.
>
> What's so special about LCM?
>
> Thanks,
> Eugene
> ----------------------------------------------------------------------
> 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 see http://www.jsoftware.com/forums.htm
