<div>On Wed, Nov 1, 2017 at 07:24 Daryle Walker <<a href="mailto:darylew@mac.com">darylew@mac.com</a>> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto"><br><br><div id="m_-8561303898083529502AppleMailSignature">Sent from my iPad</div></div><div dir="auto"><div><br>On Oct 31, 2017, at 10:55 PM, Xiaodi Wu <<a href="mailto:xiaodi.wu@gmail.com" target="_blank">xiaodi.wu@gmail.com</a>> wrote:<br><br></div><blockquote type="cite"><div><div><div>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).</div><div><br></div><div>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.</div></div></div></blockquote><div><br></div></div><div dir="auto"><div>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. </div></div></blockquote><div dir="auto"><br></div><div dir="auto">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.</div><div dir="auto"><br></div><div dir="auto">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.</div><div dir="auto"><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto"><br><blockquote type="cite"><div><div><div>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.</div></div></div></blockquote><div><br></div></div><div dir="auto"><div>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). </div><div><br></div><div>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. </div></div></blockquote><div dir="auto"><br></div><div dir="auto">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.</div><div dir="auto"><br></div><div dir="auto">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`.</div><div dir="auto"><br></div><div dir="auto">Again, one must distinguish semantics from representation. The bitwise operators have two’s-complement semantics independent of internal representation.</div><div dir="auto"><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto"><div></div><div>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. </div></div></blockquote><div dir="auto"><br></div><div dir="auto">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.</div><div dir="auto"><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto"><div></div></div><div dir="auto"><blockquote type="cite"><div><div><div><br></div>On Tue, Oct 31, 2017 at 7:23 PM, Max Moiseev via swift-evolution <span><<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word;line-break:after-white-space">Just for the reference. There was a lengthy discussion here in the mailing list back when the proposal was introduced:<div><a href="https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20170109/thread.html#30191" target="_blank">https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20170109/thread.html#30191</a></div><div><br></div><div>Max</div><div><div class="m_-8561303898083529502h5"><div><br></div><div><div><blockquote type="cite"><div>On Oct 31, 2017, at 5:15 PM, Daryle Walker via swift-evolution <<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>> wrote:</div><br class="m_-8561303898083529502m_6876455343630890721Apple-interchange-newline"><div><div>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).<br><br>What would move there are: isSigned, quotientAndRemainder, signum, %, %=, /, and /=.<br><br>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.<br><br>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”.<br><br>Sent from my iPad<br>_______________________________________________<br>swift-evolution mailing list<br><a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a><br><a href="https://lists.swift.org/mailman/listinfo/swift-evolution" target="_blank">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br></div></div></blockquote></div><br></div></div></div></div><br>_______________________________________________<br>
swift-evolution mailing list<br>
<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a><br>
<a href="https://lists.swift.org/mailman/listinfo/swift-evolution" rel="noreferrer" target="_blank">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br>
<br></blockquote></div><br></div></div>
</div></blockquote></div></blockquote></div></div>