On Wed, Nov 1, 2017 at 07:24 Daryle Walker <dary...@mac.com> wrote: > > > Sent from my iPad > > On Oct 31, 2017, at 10:55 PM, Xiaodi Wu <xiaodi...@gmail.com> wrote: > > 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 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 >> >> >
_______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution