Opened 11 months ago

Closed 8 weeks ago

#13203 closed bug (fixed)

Implement Bits Natural clearBit

Reported by: dylex Owned by: supersven
Priority: high Milestone: 8.2.2
Component: libraries/base Version: 7.10.1
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Incorrect result at runtime Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

The current Bits Natural implementation says: TODO: setBit, clearBit, complementBit (needs more primitives). The default implementations of setBit and complementBit work fine, but clearBit relies on complement, and so fails. Even if it had to use a conditional complementBit on testBit, it would be better than nothing.

Change History (11)

comment:1 Changed 11 months ago by dylex

Priority: normallowest

comment:2 Changed 10 months ago by vlopez

At least it should be documented that clearBit is undefined.

For implementing clearBit, instead of doing a conditional complementBit on testBit, I suggest doing a complementBit after setBit. This avoids branching entirely.

comment:3 Changed 4 months ago by supersven

Owner: set to supersven

comment:4 Changed 2 months ago by supersven

Hey,

I did a small experiment to check that GHC.Natural behaves as expected.

How to reproduce (that clearBit doesn't work):

[nix-shell:~/src/ghc]$ inplace/bin/ghc-stage2 --interactive
GHCi, version 8.3.20170930: http://www.haskell.org/ghc/  :? for help
Prelude> import GHC.Natural 
Prelude GHC.Natural> import Data.Bits 
Prelude GHC.Natural Data.Bits> clearBit (naturalFromInteger 1) 0
*** Exception: Bits.complement: Natural complement undefined

setBit and complementBit work as expected:

Prelude GHC.Natural Data.Bits> setBit (naturalFromInteger 0) 0
1
Prelude GHC.Natural Data.Bits> setBit  (naturalFromInteger 1) 0
1
Prelude GHC.Natural Data.Bits> complementBit (naturalFromInteger 0) 0
1
Prelude GHC.Natural Data.Bits> complementBit (naturalFromInteger 1) 0
0

Plan

  • Implement clearBit as proposed by vlopez.
  • Remove the todo.
  • Add test.

comment:5 Changed 2 months ago by hvr

*cough* phab:D3415 *cough*

Last edited 2 months ago by hvr (previous) (diff)

comment:6 Changed 2 months ago by supersven

Just a few details if someone else reads this ticket:

phab:D3415 would supersede this ticket as it implements clearBit in a more sophisticated way.

I think under these circumstances it wouldn't make much sense to finish this ticket.

Last edited 2 months ago by supersven (previous) (diff)

comment:7 Changed 8 weeks ago by Herbert Valerio Riedel <hvr@…>

In 5984a698/ghc:

Override default `clearBit` method impl for `Natural`

The default implementation of `clearBit` is in terms of
`complement`. However, `complement` is not well-defined
for `Natural` and this consequently renders the default
implementation of `clearBit` dysfunctional.

This implements `clearBit` in terms of `testBit`
and `setBit` which are both well-defined for `Natural`s.

This addresses #13203

comment:8 Changed 8 weeks ago by Herbert Valerio Riedel <hvr@…>

In 843772b8/ghc:

Enable testing 'Natural' type in TEST=arith011

This now passes thanks to 5984a698fc2974b719365a9647a7cae1bed51eec (re #13203)

comment:9 Changed 8 weeks ago by hvr

Milestone: 8.2.2
Priority: lowesthigh
Status: newmerge
Type of failure: None/UnknownIncorrect result at runtime
Version: 8.0.27.10.1

comment:10 Changed 8 weeks ago by bgamari

An implementation of clearBit for Natural has been merged to ghc-8.2 with 3de07dcf221548e73c3623a085cae99d0b519c8b.

comment:11 Changed 8 weeks ago by bgamari

Resolution: fixed
Status: mergeclosed
Note: See TracTickets for help on using tickets.