Sorry - I pressed "send" instead of "paste..." !
Second try... taking a while as my J session got clogged up with extended
hangovers and I had to force a close.
You can save a bit of time and space by deferring the conversion to
extended type:
(_&q:^:_1 >./ _ q: >: i. 10000x) -: _&q:^:_1 x:>./ _ q: >: i. 10000
1
ts'_&q:^:_1 >./ _ q: >: i. 10000x'
1.7056 3.86282e8
ts'_&q:^:_1 x:>./ _ q: >: i. 10000'
0.482409 1.37203e8
ts'lcmseq 10000' NB. but Raul's constructive approach is preferred
0.25041 771008
where
ts
6!:2 , 7!:2@]
Also, note that Raul's approach works for larger arguments
20{.": lcmseq 100000
69528383624170719700
20{.": _&q:^:_1 >./ _ q: >: i. 100000x
|limit error
| 20{.":_&q:^:_1>./_ q:>:i.100000
Raul constructs the prime power and doesn't need to factor
anything; eg, for 1 to 100:
>./ _ q: >: i. 100 NB. factoring all 100
6 4 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
100 <.@^.~ p: i. 25 NB. construct powers using 1st 25 primes
6 4 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Sorry for delayed paste/post,
Mike
On 11/03/2019 07:51, Eugene Nonko 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 <[email protected]> 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 <[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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
