About
foo=: 3 : '*/p^<.y^.~p=.p:i._1 p:y'
Because _1 p: y gives # primes less than y, one should use:
foo=: 3 : '*/p^<.y^.~p=.p:i._1 p:y+1'
((*./\)-:foo&>) 1+i.23
1
A.G
On 12-03-19 12:59, R.E. Boss wrote:
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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
