[GiNaC-list] Possible size issue in test in numeric.cpp

[Richard B. Kreckel]

Hi!

Jens Vollinga wrote:

> Pierangelo Masarati schrieb:
>
>> Jens Vollinga writes:
>>
>>> @Richy:
>>> You wondered why the other ctor for unsigned int doesn't raise such 
>>> a warning. After looking at the code I now wonder whether the code 
>>> there is optimal. The argument is compared against 
>>> 2^(cl_value_len-1) and not 2^(cl_value_len)-1 as one might expect. 
>>> Maybe this should be changed? Could you comment on this soon, 
>>> because I'd like to roll the release this evening?
>>
>>
>> I agree it should be
>>       i < ((1UL << cl_value_len)-1)
>
>
> well, I have to correct myself: it should be
>        i < (1UL << cl_value_len)
> I guess.
>
>> In this case, a fix similar to the "int" case on 64 bit architectires 
>> would apply, since a "unsigned" will always be less than 2^32.  A 
>> patch is available at
>> <http://mbdyn.aero.polimi.it/~masarati/Download/mbdyn/ginac-numeric-uint.pat 
>> ch>
>
>
> thanks, but I've already done that :-)
>
> But still I want to wait for Richy's response before I put it in CVS, 
> because it could be that CLN uses a signed data representation for 
> small integers internally (crazy idea, but conceivable ... ;-)) so 
> that the original if clause might be correct.


For small integers, CLN uses immediate types (no heap allocation). They 
occupy cl_value_len bits. (Not all bits inside a word can be used, 
because some bits must be reserved for tagging heap-allocated objects.) 
Now, these integers of cl_value_len bits are signed: 
2^(cl_value_len-1)...2^(cl_value_len-1)-1. The GiNaC code we are 
discussing uses different ctors, one from int and one from unsigned int, 
which both result in the same immediate type. There is no unsigned 
immediate type! For large numbers it must use some ctor that is not 
prone to rollover errors. (For reasons of performance, such rollover 
errors were deemed acceptable in CLN for int types, since when coding 
with ints, one has to be aware of these rollover errors anyway. In 
GiNaC, I didn't want to incur such behavior. Hence, the if statement.)

The current code is correct.

In the ctor from int, we can test that the undesired rollover starts at 
(1L << (cl_value_len-1)) and below -(1L << (cl_value_len-1))). Actual 
numbers are from a 32-bit system where cl_value_len is 30. They might be 
different on other machines.
    int i;
    cl_I X;
    i = (1L << (cl_value_len-1));
    X = i;
    cout << i << " and " << X << endl;  // bad: 536870912 and -536870912
    i = i - 1;
    X = i;
    cout << i << " and " << X << endl;  // good: 536870911 and 536870911
    i = -(1L << (cl_value_len-1));
    X = i;
    cout << i << " and " << X << endl;  // good: -536870912 and -536870912
    i = i - 1;
    X = i;
    cout << i << " and " << X << endl;  // bad: -536870913 and 536870911

In the ctor from unsigned, we can verify that the undesired rollover is 
at the same point:
    unsigned i;
    cl_I X;
    i = (1UL << (cl_value_len-1));
    X = i;
    cout << i << " and " << X << endl;  // bad: 536870912 and -536870912
    i = i - 1;
    X = i;
    cout << i << " and " << X << endl;  // good: 536870911 and 536870911

Now, you seem to be suggesting to test against twice that value, i < 
(1UL << cl_value_len). This is going to lead to undesired behavior:
    unsigned i;
    cl_I X;
    i = (1UL << cl_value_len) - 1;
    X = i;
    cout << i << " and " << X << endl;  // bad: 1073741823 and -1

HTH
  -richy.

-- 
Richard B. Kreckel
<http://www.ginac.de/~kreckel/>