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
