You don't really need extended precision (for a while), which makes it
obviously a lot faster.
foo=: 3 : '*/p^<.y^.~p=.p:i._1 p:y'
100000(-:&foo)100000x
1
R.E. Boss
> -----Oorspronkelijk bericht-----
> Van: Programming <programming-boun...@forums.jsoftware.com>
> Namens Don Guinn
> Verzonden: maandag 11 maart 2019 17:38
> Aan: Programming forum <programm...@jsoftware.com>
> Onderwerp: Re: [Jprogramming] LCM performance
>
> 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
> > >>>>>>
> > >>>>>>
> >
> 6952838362417071970003075865264183883398742917680351135360275375615
> 0414421750212375062579868286020477636128776978764548927336600810587
> 0757535968316298519927347209547516689789186138157883056062709938348
> 3382709560516260628624180504874681127372319705939469099...
> > >>>>>> 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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
