Re: [boost] New Boost.XInt Library, request preliminary review

Subject: Re: [boost] New Boost.XInt Library, request preliminary review
From: DE (satan66613_at_[hidden])
Date: 2010-04-07 14:30:03

on 07.04.2010 at 21:04
 Chad Nelson wrote :
>> by the way you could store the sign in the MSB of the most
>> significant digit

> Maybe I'm mistaken, but I thought that's what two's-complement meant.
a number is stored in two's complement in the following way:
if it is positive -- MSB is 0 an values is encoded straightforwardly
if it is negative -- it is encoded as 'radix^digits - value'
e.g. for 32 bit binary ints it is '2^32 - value'

or simply put

if 'v' is positive or negative number to encode and
'm' is some modulo (such as 2^32)
then a number is encoded as

  (m - v)%m

the advantage is that addition and subtraction works straightforward
with no special care about the signs of operands
e.g.

  a + b == (m + a + b)%m
or
  a - b == (m + a - b)%m

i may misunderstand all this so better see e.g.
http://en.wikipedia.org/wiki/Two's_complement

>> though i didn't dig the implementation and not sure you have a
>> distinct bool for the sign

> Yes, I do.

i suggest to pack the sign in the MSB of the most significant digit to
get rid of the bool
it still would be a sign-magnitude representation

so retrievel would be like

  digits[n_digits - 1]&(1<<15)/*==0*/

but perhaps you would need to set that bit to 0 during some operations
which involves some additional overhead

-- 
Pavel
P.S.
if you notice a grammar mistake or weird phrasing in my message
please point it out