Implement {set,clear,complement}BitBigNat primitives
ClosedPublic

Authored by hvr on Apr 4 2017, 1:53 AM.

Details

Summary

This implements the missing {set,clear,complement}BitBigNat primitives
and hooks them up to Natural's Bits instance.

This doesn't yet benefit Integer, as we still need "negative" BigNat
variants for that.

Test Plan

This patch enables test-coverage via arith011. I've additionally externally stress-tested the new operations against a QuickCheck based testsuite comparing against a reference implementation based on a custom fixed-length Word4096 type (see P158).

Diff Detail

Repository
rGHC Glasgow Haskell Compiler
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.
hvr created this revision.Apr 4 2017, 1:53 AM
hvr updated this revision to Diff 11992.Apr 4 2017, 9:22 AM
  • Silence -Wunbanged-strict-patterns
bgamari edited edge metadata.Apr 4 2017, 12:14 PM

I just found this patch again I wrote about a year ago. I think this fixed an actual numeric miscalculation bug as a side-effect but I need to reverse engineer which one... ;-)

Once you find it be sure to add a testcase.

rwbarton requested changes to this revision.Apr 4 2017, 4:24 PM
rwbarton added inline comments.
libraries/base/GHC/Natural.hs
356

Doesn't it need to be complementBit not setBit?

360

Isn't it done now, just above?

libraries/integer-gmp/src/GHC/Integer/Type.hs
2168

I suspect it's better to match on bn here, since as written this function is not strict in bn and I think you want it to worker/wrapper.

This revision now requires changes to proceed.Apr 4 2017, 4:24 PM
hvr updated this revision to Diff 14337.Oct 14 2017, 2:46 AM

Rebase & address @rwbarton's concerns

hvr marked 3 inline comments as done.Oct 14 2017, 2:47 AM
hvr planned changes to this revision.Oct 14 2017, 2:50 AM
hvr updated this revision to Diff 14339.Oct 14 2017, 1:39 PM
  • Enable testing 'Natural' type in TEST=arith011
hvr edited the test plan for this revision. (Show Details)Oct 16 2017, 12:17 PM
hvr edited the summary of this revision. (Show Details)Oct 16 2017, 12:19 PM
hvr updated the Trac tickets for this revision.
bgamari accepted this revision.Oct 16 2017, 1:14 PM

Yep, this looks right to me. Thanks, @hvr!

This revision was automatically updated to reflect the committed changes.
hvr updated the Trac tickets for this revision.Oct 16 2017, 3:39 PM