Opened 10 years ago

Closed 9 years ago

# gcd is specialised only for Int

Reported by: Owned by: dons dons@… normal 6.12.1 libraries/base 6.8.2 rules, performance, double, gcd Unknown/Multiple Unknown/Multiple None/Unknown

### Description

We have the general:

```gcd             :: (Integral a) => a -> a -> a
gcd 0 0         =  error "Prelude.gcd: gcd 0 0 is undefined"
gcd x y         =  gcd' (abs x) (abs y)
where gcd' a 0  =  a
gcd' a b  =  gcd' b (a `rem` b)
```

And a specialisation for Int only:

```{-# RULES
"gcd/Int->Int->Int"             gcd = gcdInt
#-}

gcdInt (I# a) (I# b) = g a b
where g 0# 0# = error "GHC.Base.gcdInt: gcd 0 0 is undefined"
g 0# _  = I# absB
g _  0# = I# absA
g _  _  = I# (gcdInt# absA absB

```

Thanks to the gcdInt# primop.

If we use Word here, or other Int types, we get the slow version (which is only 10x slower, surprisingly):

```main = print . sumU
. mapU (gcd 2)
\$ enumFromToU 0 (100000000 :: Word)

```

Comes out as:

``` time ./henning
150000002
./henning  25.73s user 0.05s system 99% cpu 25.936 total

```

Versus:

```\$ time ./henning
150000002
./henning  2.33s user 0.00s system 99% cpu 2.334 tota

```

So there are two things we can do here to improve the situation:

## Step 1: Add rules for getting from the other Int* types to gcdInt#

```{-# RULES

"gcd/Int32->Int32->Int32" gcd = gcdInt32

#-}

gcdInt32 :: Int32 -> Int32 -> Int32
gcdInt32 x y = fromIntegral ((gcd :: Int -> Int -> Int) (fromIntegral x) (fromIntegral y))

```

For example, takes the running time from 28 seconds to 2.4seconds, for:

```main = print . sumU
. mapU (gcd 2)
\$ enumFromToU 0 (100000000 :: Int32)

```

## Step 2: optionally add a gcdWord#

We could then also add a gcdWord# primop,or perhaps just following fromIntegral, and test for negative first, then conditionally dispatch to gcdInt.

What do people think?

### comment:1 Changed 10 years ago by igloo

difficulty: → Unknown → 6.10.1

### comment:2 Changed 10 years ago by igloo

Component: Compiler → libraries/base

### comment:3 Changed 10 years ago by guest

Cc: rules performance double gcd removed rules performance double gcd added

### comment:4 Changed 10 years ago by simonmar

Architecture: Unknown → Unknown/Multiple

### comment:5 Changed 10 years ago by simonmar

Operating System: Unknown → Unknown/Multiple

### comment:6 Changed 10 years ago by igloo

Milestone: 6.10.1 → 6.10.2

### comment:7 Changed 9 years ago by igloo

Milestone: 6.10.2 → 6.12.1

### comment:8 Changed 9 years ago by igloo

Resolution: → duplicate new → closed

Closing, as this ticket is subsumed by #3055.

Note: See TracTickets for help on using tickets.