Re: [boost] Algebraic abstractions related to (big) integers in C++

Subject: Re: [boost] Algebraic abstractions related to (big) integers in C++
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2011-03-29 15:09:32

pavel wrote:
> honestly i didn't get the _whole_ point of this message but i have
> some comments on it

I liked your comments. I didn't expect anybody to even try to "get the _whole_ point of this message". I realized that the things I don't like about integers in C++ (signed to unsigned promotion, the behavior of the modulo operator for negative numbers, the missing "standard library" functions for "add_with_carry" and "multiply_full_result") couldn't be changed anyway, no matter how convincingly I would prove that they are unfortunate. And with respect to the two's complement representation, I realized that I also didn't know the answer to the question that was bothering me. So I could just as well be honest and tell about my actual algebraic thoughts (and their origin), even knowing that "practical arguments would resonate more deeply with this list".


>  Thomas wrote on Sunday, March 27, 2011 at 3:21:04:
> > ...However, XInt and other bigint libraries
> > took the opposite decision, so there is strong circumstantial
> > evidence against using two's complement representation for (iii)...
> 
> i wondered myself why chad didn't use two's complement because it
> seemed straightforward to me but i didn't ever mentioned it
> 
> eventually chad stated that sign-magnituted implementation suits
> better for non-trivial operations and i have no point to protest

I guess many of us wondered, but we were all not really sure whether the two's complement representation would be really better than the sign magnitude representation. It would have been just an implementation detail, but some people requested separation of algorithms and data representation, including actual access to the underlying representation. I initially thought that the two's complement representation would be the better representation, but I changed my mind during writing the message (because I finally took a deeper look at XInt and related libraries, and read some blogs and articles from Wikipedia). I'm not yet sure whether the two's complement representation must actually be avoided, like for the floating point numbers.


> > ...So I tried to write the Quaternion group (the one
> > with the 8 elements 1, -1, i, -i, j, -j, k, -k) as a semi-direct
> > product. This didn't work, because the Quaternion group is not a
> > semi-direct product...
> 
> perhaps you ment octonions since quaternions have {1, i, j, k}
> elements in contrast to what you mentioned

I mean the "quaternion group", not the quaternions: "In group theory, the quaternion group is a non-abelian group of order 8, isomorphic to a certain eight-element subset of the quaternions under multiplication."


> > ...This is also one
> > of the reasons why the two's complement representation should be
> > avoided for floating point numbers, because the relevant metric in
> > this case is the normal metric of the real numbers.
> 
> afaik IEEE 754 / ISO/IEC 60559 standards describe just that
> sign-magnitude representation which is widely used in the majority of
> computer processors

Isn't it nice that at least some things are done right? You may ask what's the purpose of theory then, because when the practice got it right, it can't deliver anything new, and when practice got it wrong, you have to live with it anyway. But I very much prefer the situations where theory can't deliver anything new over the situations where you have to live with it anyway.
 

> what i understood is that you suggest to carefully think of
> signed/unsigned behavior of integers when one develops an integer
> algebra library
> 
> but i think that in C++ we have no choice but to follow the
> historical tradition and to treat integers like our parents did

I'm not so sure. We happily accept the compile errors of std::min and std::max when mixing signed and unsigned numbers. The problem is that "1", "23" have the concrete type "int", which forces the "signed to unsigned promotion" upon us. If we would be able to solve this problem (like Haskell did with the help of its powerful type system), we could think about fixing the "signed to unsigned promotion".


> otherwise, such way may introduce confusion to users and render well
> known idioms unappliable

You can always cast explicitly (but of course you don't want to be forced to do it too often).


> however i do not object to begin treating integers in semantically
> more correct way even if it can cause consequences

The introduction of some of the missing "standard library" functions like "modulo", "add_with_carry" or "multiply_full_result" would be a good start, and would cause nearly no harm. Of course it would only make sense if it would really enable to write fast bigint libraries in a portable way without falling back to assembler.

Regards,
Thomas