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
