6!:2 'n=:*/p^<.y^.~p=.p:i._1 p:y=.100000x'
0.690272
40{.":n
6952838362417071970003075865264183883398
On Mon, Mar 11, 2019 at 10:07 AM 'Mike Day' via Programming <
programm...@jsoftware.com> wrote:
> As mentioned (indirectly) in my second attempt to comment, the _ q:
> version failed (on my Windows 10 laptop, with 16Gb memory!) for 100000,
> while yours was ok. As, of course, you know, your approach avoids factoring
> by predicting the maximum prime powers.
>
> Cheers,
>
> Mike
>
> Please reply to mike_liz....@tiscali.co.uk.
> Sent from my iPad
>
> > On 11 Mar 2019, at 15:50, Raul Miller <rauldmil...@gmail.com> wrote:
> >
> > And, that said, after playing with this, lcmseq 100000x seems to be
> > significantly faster than >./&.(_&q:) 1+i. 100000x (at least on this
> > machine).
> >
> > FYI,
> >
> > --
> > Raul
> >
> > P.S. if you are reading this in a context where the rest of this
> > thread is not available, the definition of lcmseq was:
> >
> > lcmseq=: 3 : 0
> > primes=. i.&.(p:inv) y
> > maxsq=. 1+primes I.%:y
> > */primes^x:1>.(#primes){.<.(maxsq{.primes)^.y
> > )
> >
> >> On Mon, Mar 11, 2019 at 10:08 AM Raul Miller <rauldmil...@gmail.com>
> wrote:
> >>
> >> Wasn’t thinking clearly though because the _ q: representation is much
> nicer...
> >>
> >> Sorry about the noise...
> >>
> >> —
> >> Raul
> >>
> >>> On Monday, March 11, 2019, Raul Miller <rauldmil...@gmail.com> wrote:
> >>>
> >>> __ q: I meant..
> >>>
> >>> Thanks,
> >>>
> >>> —
> >>> Raul
> >>>
> >>>> On Monday, March 11, 2019, Raul Miller <rauldmil...@gmail.com> wrote:
> >>>>
> >>>> That’s a good approach.
> >>>>
> >>>> The _ q: representation is really nice for this task.
> >>>>
> >>>> Thanks,
> >>>>
> >>>> —
> >>>> Raul
> >>>>
> >>>>> On Monday, March 11, 2019, Eugene Nonko <eno...@gmail.com> wrote:
> >>>>>
> >>>>> Here's the solution I ended up using:
> >>>>>
> >>>>> _&q:^:_1 >./ _ q: >: i. 10000x
> >>>>>
> >>>>> Just factorize to prime exponents representation, find maximums and
> convert
> >>>>> back from prime exponent representation.
> >>>>>
> >>>>>> On Sun, Mar 10, 2019 at 2:35 PM Raul Miller <rauldmil...@gmail.com>
> wrote:
> >>>>>>
> >>>>>> 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 <james.fa...@epitech.eu
> >
> >>>>>> 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 <programming-boun...@forums.jsoftware.com> on
> behalf
> >>>>>> of Eugene Nonko <eno...@gmail.com>
> >>>>>>> Sent: Sunday, March 10, 2019 9:00 PM
> >>>>>>> To: programm...@jsoftware.com
> >>>>>>> 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
> >>>>>
> ----------------------------------------------------------------------
> >>>>> 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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
