Wow, so the formatting died somehow..
gcd :: (Integral a) => a -> a -> a
{-# NOINLINE [1] gcd #-}
gcd x y = gcd' (abs x) (abs y)
where gcd' a 0 = a
gcd' a b = gcd' b (a `rem` b)
-- | @'lcm' x y@ is the smallest positive integer that both @x@ and @y@ divide.
lcm :: (Integral a) => a -> a -> a
{-# SPECIALISE lcm :: Int -> Int -> Int #-}
{-# SPECIALISE lcm :: Word -> Word -> Word #-}
{-# NOINLINE [1] lcm #-}
lcm _ 0 = 0
lcm 0 _ = 0
lcm x y = abs ((x `quot` (gcd x y)) * y)
________________________________
From: Programming <[email protected]> on behalf of james
faure <[email protected]>
Sent: Sunday, March 10, 2019 11:42 PM
To: [email protected]
Subject: Re: [Jprogramming] LCM performance
For reference, the haskell implementation doesn't have any special magic to it,
besides the lazy list handling:
gcd ::
(Integral<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#Integral>
a<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#local-6989586621679043702>)
=>
a<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#local-6989586621679043702>
->
a<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#local-6989586621679043702>
->
a<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#local-6989586621679043702>
{-# NOINLINE [1] gcd #-}
gcd<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#gcd>
x<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#local-6989586621679043774>
y<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#local-6989586621679043775>
=
gcd'<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#local-6989586621679043776>
(abs<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Num.html#abs>
x<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#local-6989586621679043774>)
(abs<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Num.html#abs>
y<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#local-6989586621679043775>)
where
gcd'<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#local-6989586621679043776>
a<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#local-6989586621679043777>
0 =
a<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#local-6989586621679043777>
gcd'
a<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#local-6989586621679043778>
b<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#local-6989586621679043779>
=
gcd'<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#local-6989586621679043776>
b<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#local-6989586621679043779>
(a<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#local-6989586621679043778>
`rem<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#rem>`
b<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#local-6989586621679043779>)
-- | @'lcm' x y@ is the smallest positive integer that both @x@ and @y@ divide.
lcm ::
(Integral<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#Integral>
a<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#local-6989586621679043701>)
=>
a<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#local-6989586621679043701>
->
a<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#local-6989586621679043701>
->
a<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#local-6989586621679043701>
{-# SPECIALISE lcm :: Int -> Int -> Int #-}
{-# SPECIALISE lcm :: Word -> Word -> Word #-}
{-# NOINLINE [1] lcm #-}
lcm<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#lcm>
_ 0 = 0
lcm 0 _ = 0
lcm
x<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#local-6989586621679043780>
y<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#local-6989586621679043781>
=
abs<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Num.html#abs>
((x<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#local-6989586621679043780>
`quot<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#quot>`
(gcd<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#gcd>
x<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#local-6989586621679043780>
y<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#local-6989586621679043781>))
*<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Num.html#%2A>
y<http://hackage.haskell.org/package/base-4.12.0.0/docs/src/GHC.Real.html#local-6989586621679043781>)
________________________________
From: Programming <[email protected]> on behalf of Raul
Miller <[email protected]>
Sent: Sunday, March 10, 2019 10:38 PM
To: Programming forum
Subject: Re: [Jprogramming] LCM performance
P.S. the english describing this problem here should be fixed.
The smallest positive number which divides 1+i.n evenly is 1 and a 1:
would be a verb to compute that value.
The number being computed here is the smallest positive number which
1+i.n divides (with an integer result).
(If we allowed negative or fractional values we would... have other issues ...)
Sometimes the words matter, I am not sure if this is one of those
cases, but it's still pretty easy to fix here.
Thanks,
--
Raul
On Sun, Mar 10, 2019 at 4:00 PM Eugene Nonko <[email protected]> wrote:
>
> 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
