Sent from my iPad

Right, these issues were discussed when the proposal was introduced and

reviewed three times. In brief, what was once proposed as `Integer` was

renamed `BinaryInteger` to avoid confusion in name between `Integer` and

`Int`. It was also found to better reflect the semantics of the protocol,

as certain functions treated the value not merely as an integer but

operated specifically on its binary representation (for instance, the

bitwise operators).

Do not confuse integers from their representation. Integers have no

intrinsic radix and all integers have a binary representation. This is

distinct from floating-point protocols, because many real values

representable exactly as a decimal floating-point value cannot be

represented exactly as a binary floating-point value.

Abstractly, integers have representations in nearly all real radixes. But

mandating base-2 properties for a numeric type that uses something else

(ternary, negadecimal, non-radix, etc.) in its storage is definitely

non-trivial. Hence the request for intermediate protocols that peel off the

binary requirements.

Not only binary properties, but specifically two’s-complement binary

properties. You are correct that some operations require thought for

implementation if your type uses ternary storage, or for any type that does

not specifically use two’s-complement representation internally, but having

actually implemented them I can assure you it is not difficult to do

correctly without even a CS degree.

Again, one must distinguish between the actual representation in storage

and semantics, which is what Swift protocols guarantee. The protocols are

totally agnostic to the internal storage representation. The trade-off for

supporting ternary _semantics_ is an additional set of protocols which

complicates understanding and use in generic algorithms. I am not aware of

tritwise operations being sufficiently in demand.

To your specific question about bitwise operators: their semantics are

with respect to the two's-complement binary representation of the integer

regardless of the actual internal representation. `~` returns the one's

complement of the two's-complement binary representation of the integer.

FWIW, this is exactly what `mpn_com()` does in GNU MP for

arbitrary-precision integers.

To continue your own analogy, integers by themselves don’t have radix (or

reduced-radix) complements. The complements depend on a fixed width, since

they’re based on Radix ** Width modulo arithmetic (or Radix ** Width - 1

for the reduced-radix complement).

15 has a two’s complement under a binary representation with N bits (where

N is at least 4). It has a ones’ complement too. Doing any complement of 15

without an N is non-sensical; the result effectively would have an infinite

number of ones at its beginning. I guess GNU-MP is stopping at the width of

the original number’s storage, but that doesn’t make it right (although

it’s more practical). That’s why complements should be under the

fixed-width protocols, not the general integer ones.

The two’s-complement representation of a negative number contains an

infinite number of leading zeros when the bit width is infinite. Bitwise

operators have consistent semantics with this definition. Neither GNU MP,

nor a conformant sign-magnitude arbitrary-width type in Swift, performs

actual bitwise operations on the internal storage, but returns the result

that would be obtained by performing those operations on the notionally

infinite two’s-complement binary representation of the integer, which is

not the internal storage representation.

The binary representation of 15 is 0b1111. For an infinite-width type, the

one’s complement is 0b1...10000. That is the binary representation of -16.

So, `~15 as BigInt == -16`.

Again, one must distinguish semantics from representation. The bitwise

operators have two’s-complement semantics independent of internal

representation.

The very existence of BinaryInteger is proof of allowing protocols for

types that don’t exist in the Standard Library (yet). (In other words, if

protocols had to be justified with a current algorithm or type to be in the

SL, then BinaryInteger should be purged since there’s no current type that

uses it without using FixedWidthInteger too.) I just think the hierarchy

needs a little more tweaking.

Yes, it’s meant to allow for an arbitrary-width integer type, a prototype

of which exists in the Swift repository. It is very much possible to write

such a type that conforms to all the requirements of BinaryInteger.

## ···

On Wed, Nov 1, 2017 at 07:24 Daryle Walker <darylew@mac.com> wrote:

On Oct 31, 2017, at 10:55 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

On Tue, Oct 31, 2017 at 7:23 PM, Max Moiseev via swift-evolution < > swift-evolution@swift.org> wrote:

Just for the reference. There was a lengthy discussion here in the

mailing list back when the proposal was introduced:

https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20170109/thread.html#30191

Max

On Oct 31, 2017, at 5:15 PM, Daryle Walker via swift-evolution < >> swift-evolution@swift.org> wrote:

Looking at Apple’s Swift (4) docs at their SDK site, shouldn’t there be

an “Integer” protocol between Numeric and BinaryInteger? Without that,

there’s no solution for Integer types that are either a non-binary radix or

a non-radix system (besides being over-broad with Numeric).

What would move there are: isSigned, quotientAndRemainder, signum, %, %=,

/, and /=.

Also, how is ~ supposed to work in a BinaryInteger that is not a

FixedWidthInteger? Extend the high bits to infinity? Maybe that operator

should move to the derived protocol.

Oh, why can’t a non-binary Integer type be fixed-width? FixedWidthInteger

should be renamed “FixedWidthBinaryInteger,” which derives from

BinaryInteger and a new version of FixedWidthInteger. The new version peels

off: max, min, addingReportingOverflow, dividedReportingOverflow,

dividingFullWidth, multipliedFullWidth, multipliedReportingOverflow,

remainderReportingOverflow, and subtractingReportingOverflow. There’s also

a “digitWidth” type property, analogous to “bitWidth”.

Sent from my iPad

_______________________________________________

swift-evolution mailing list

swift-evolution@swift.org

https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________

swift-evolution mailing list

swift-evolution@swift.org

https://lists.swift.org/mailman/listinfo/swift-evolution