#9818: Add `Natural` number type to `base` -------------------------------------+------------------------------------- Reporter: hvr | Owner: hvr Type: feature | Status: new request | Milestone: 7.10.1 Priority: normal | Version: Component: Core | Keywords: base natural Libraries | Architecture: Unknown/Multiple Resolution: | Difficulty: Unknown Operating System: | Blocked By: Unknown/Multiple | Related Tickets: #3650 Type of failure: | None/Unknown | Test Case: | Blocking: | Differential Revisions: Phab:D473 | -------------------------------------+------------------------------------- Comment (by Herbert Valerio Riedel ): In [changeset:"8a8cdbbfd855015049526c7945cbe9ccbb152f1e/ghc"]: {{{ #!CommitTicketReference repository="ghc" revision="8a8cdbbfd855015049526c7945cbe9ccbb152f1e" Implement `Natural` number type (re #9818) This implements a `Natural` type for representing unsigned arbitrary precision integers. When available, `integer-gmp>=1.0.0`'s `BigNat` type is used as building-block to construct `Natural` as an algebraic data-type. Otherwise, `Natural` falls back being a `newtype`-wrapper around `Integer` (as is done in Edward Kmett's `nats` package). The `GHC.Natural` module exposes an internal GHC-specific API, while `Numeric.Natural` provides the official & portable API. Reviewed By: austin, ekmett Differential Revision: https://phabricator.haskell.org/D473 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9818#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9818: Add `Natural` number type to `base` -------------------------------------+------------------------------------- Reporter: hvr | Owner: hvr Type: feature | Status: new request | Milestone: 7.10.1 Priority: normal | Version: Component: Core | Keywords: base natural Libraries | Architecture: Unknown/Multiple Resolution: | Difficulty: Unknown Operating System: | Blocked By: Unknown/Multiple | Related Tickets: #3650 Type of failure: | None/Unknown | Test Case: | Blocking: | Differential Revisions: Phab:D473 | -------------------------------------+------------------------------------- Comment (by Herbert Valerio Riedel ): In [changeset:"b836139099fc203a8b94849655d7dfb95dd80f4a/ghc"]: {{{ #!CommitTicketReference repository="ghc" revision="b836139099fc203a8b94849655d7dfb95dd80f4a" Fix `fromInteger` constructing invalid `Natural` This fixes a case where `isValidNatural . fromInteger` would be `False`. Re #9818 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9818#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9818: Add `Natural` number type to `base` -------------------------------------+------------------------------------- Reporter: hvr | Owner: hvr Type: feature | Status: new request | Milestone: 7.10.1 Priority: normal | Version: Component: Core | Keywords: base natural Libraries | Architecture: Unknown/Multiple Resolution: | Difficulty: Unknown Operating System: | Blocked By: Unknown/Multiple | Related Tickets: #3650 Type of failure: | None/Unknown | Test Case: | Blocking: | Differential Revisions: Phab:D473 | -------------------------------------+------------------------------------- Comment (by Herbert Valerio Riedel ): In [changeset:"96d29b5403bd8a6465a65a39da861f5b9610fc89/ghc"]: {{{ #!CommitTicketReference repository="ghc" revision="96d29b5403bd8a6465a65a39da861f5b9610fc89" Call `popCountBigNat` directly (#9818) This calls the `popCountBigNat` primitive directly instead of going through `Integer`'s `popCount`. }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9818#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9818: Add `Natural` number type to `base` -------------------------------------+------------------------------------- Reporter: hvr | Owner: hvr Type: feature | Status: new request | Milestone: 7.10.1 Priority: normal | Version: Component: Core | Keywords: base natural Libraries | Architecture: Unknown/Multiple Resolution: | Difficulty: Unknown Operating System: | Blocked By: Unknown/Multiple | Related Tickets: #3650 Type of failure: | None/Unknown | Test Case: | Blocking: | Differential Revisions: Phab:D473 | -------------------------------------+------------------------------------- Comment (by Herbert Valerio Riedel ): In [changeset:"859680f6fe952ecbef3395fa4f299530d0f10c58/ghc"]: {{{ #!CommitTicketReference repository="ghc" revision="859680f6fe952ecbef3395fa4f299530d0f10c58" Implement `GHC.Natural.powModNatural` (#9818) This makes use of the `powMod*` primitives provided by `integer-gmp-1.0.0`. This is the `Natural`-version of the related `GHC.Integer.GMP.Internals.powModInteger` operation. The fallback implementation uses a square and multiply algorithm, compared to which the optimized GMP-based implementation needs much less allocations due to in-place mutation during the computation. }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9818#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9818: Add `Natural` number type to `base` -------------------------------------+------------------------------------- Reporter: hvr | Owner: hvr Type: feature | Status: closed request | Milestone: 7.10.1 Priority: normal | Version: Component: Core | Keywords: base natural Libraries | Architecture: Unknown/Multiple Resolution: fixed | Difficulty: Unknown Operating System: | Blocked By: Unknown/Multiple | Related Tickets: #3650 #9281 Type of failure: | None/Unknown | Test Case: | Blocking: | Differential Revisions: Phab:D473 | -------------------------------------+------------------------------------- Comment (by thomie): The comment about @Natural@ in `libraries/base/Data/Word.hs` can be deleted or changed to point to this new module. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9818#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9818: Add `Natural` number type to `base` -------------------------------------+------------------------------------- Reporter: hvr | Owner: hvr Type: feature | Status: closed request | Milestone: 7.10.1 Priority: normal | Version: Component: Core | Keywords: base natural Libraries | Architecture: Unknown/Multiple Resolution: fixed | Difficulty: Unknown Operating System: | Blocked By: Unknown/Multiple | Related Tickets: #3650 #9281 Type of failure: | None/Unknown | Test Case: | Blocking: | Differential Revisions: Phab:D473 | -------------------------------------+------------------------------------- Comment (by Herbert Valerio Riedel ): In [changeset:"6b063ef2a1f68290b51778a38e9b89b6fec5e170/ghc"]: {{{ #!CommitTicketReference repository="ghc" revision="6b063ef2a1f68290b51778a38e9b89b6fec5e170" Make Natural's (.|.) really an OR operation (#9818) Currently it's an AND when at least one of the operands is big. Reviewed By: hvr Differential Revision: https://phabricator.haskell.org/D549 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9818#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler