GSoC #6: Round Modes and Their Behavior


#1

The original blog post is here.


In @cfelton 's implementation of fixbv, there are some kinds of round modes implemented in _resize.py, as in the source code:

                  # round    :
ROUND_MODES = (   # towards  :
    'ceil',       # +infinity: always round up
    'fix',        # 0        : always down
    'floor',      # -infinity: truncate, always round down
    'nearest',    # nearest  : tie towards largest absolute value
    'round',      # nearest  : ties to +infinity
    'convergent', # nearest  : tie to closest even (round_even)
    'round_even', # nearest  : tie to closest even (convergent)
    )

The behavior of ceil, fix and floor is quite clear in this case. Whatever fractional part is, it will be rounded to the integer towards +inf, 0, or -inf.

But it seems not quite clear for the last four modes.

OK, let’s see the source code in _resize.py first:

def _round(val, fmt, round_mode):
    """Round the initial value if needed"""
    # Scale the value to the integer range (the underlying representation)

    assert is_round_mode(round_mode)
    assert isinstance(fmt, tuple)
    wl,iwl,fwl = fmt
    _val = val
    val = val * 2.0**fwl
    #print("    [rsz][rnd]: %f %f, %s" % (val, _val, fmt))

    if round_mode == 'ceil':
        retval = math.ceil(val)

    elif round_mode == 'fix':
        if val > 0:
            retval = math.floor(val)
        else:
            retval = math.ceil(val)

    elif round_mode == 'floor':
        retval = math.floor(val)

    elif round_mode == 'nearest':
        fval,ival = math.modf(val)
        if fval == .5:
            retval = int(val+1) if val > 0 else int(val-1)
        else:
            retval = round(val)

    elif round_mode == 'round':
        retval = round(val)
        
    elif round_mode == 'round_even' or round_mode == 'convergent':
        fval,ival = math.modf(val)
        abs_ival = int(abs(ival))
        sign = -1 if ival < 0 else 1

        if (abs(fval) - 0.5) == 0.0:
            if abs_ival%2 == 0:
                retval = abs_ival * sign
            else:
                retval = (abs_ival + 1) * sign
        else:
            retval = round(val)

    else:
        raise TypeError("invalid round mode!" % self.round_mode)

    return int(retval)

To read the last 4 kinds of resolution, it is necessary to know the behavior of Python’s built-in round function.

Here we assume we do not provide ndigits parameter to round function.

Python’s document says that round will round the numbers to the nearest integer. However, if the fractional part is 0.5, round will round to the nearest even number. That is to say, round(2.5) will be 2, but round(3.5) will be 4.

So, I guess that the behavior of round modes round, round_even, and convergent are the same.

Finally, nearest will be the same as the above three round modes in negative values, but for positive values, it will be different. If the fractional part is 0.5, it will advance to the larger integer, otherwise round to the nearest.

To verify this, I wrote a small program for it. The rounding code is copied from corresponding function in _resize.py.

import math
import csv

                  # round    :
ROUND_MODES = (   # towards  :
    'ceil',       # +infinity: always round up
    'fix',        # 0        : always down
    'floor',      # -infinity: truncate, always round down
    'nearest',    # nearest  : tie towards largest absolute value
    'round',      # nearest  : ties to +infinity
    'convergent', # nearest  : tie to closest even (round_even)
    'round_even', # nearest  : tie to closest even (convergent)
    )

def _round(val, round_mode):
    if round_mode == 'ceil':
        retval = math.ceil(val)

    elif round_mode == 'fix':
        if val > 0:
            retval = math.floor(val)
        else:
            retval = math.ceil(val)

    elif round_mode == 'floor':
        retval = math.floor(val)

    elif round_mode == 'nearest':
        fval,ival = math.modf(val)
        if fval == .5:
            retval = int(val+1) if val > 0 else int(val-1)
        else:
            retval = round(val)

    elif round_mode == 'round':
        retval = round(val)

    elif round_mode == 'round_even' or round_mode == 'convergent':
        fval,ival = math.modf(val)
        abs_ival = int(abs(ival))
        sign = -1 if ival < 0 else 1

        if (abs(fval) - 0.5) == 0.0:
            if abs_ival%2 == 0:
                retval = abs_ival * sign
            else:
                retval = (abs_ival + 1) * sign
        else:
            retval = round(val)

    else:
        raise TypeError("invalid round mode!" % self.round_mode)

    return int(retval)

values = [-3.5, -3.14, -3., -2.718, -2.5, -2., -1.618, -1.5, -1., -.618, -.5,
          0., .5, .618, 1., 1.5, 1.618, 2., 2.5, 2.718, 3., 3.14, 3.5]

with open('round_test.csv', 'w', newline='') as csvfile:
    wr = csv.writer(csvfile)
    wr.writerow([''] + values)

    for round_mode in ROUND_MODES:
        rounded_values = [_round(val, round_mode) for val in values]
        wr.writerow([round_mode] + rounded_values)

It tests different values for different round modes.

Here is the result:


EDIT: The code of “nearest” rounding did not handle the case of negative values, so the condition case should be:

if fval == .5 or fval == -.5:

And its behavior when the fractional part is 0.5 (either positive or negative) should be rounding away from 0.


GSoC #7: Overflow Modes
#2

I have three remarks:

  1. In Python, integers can have arbitrary length. I believe strongly, this property should be maintained by fixbv, especially because there is no reason why it cannot be done.
    In your code you write “val = val * 2.0**fwl”. By doing this, you convert your number into a double-precision floating point number and therefore limit the possible accuracy to the mantissa length (52 bit) and introduce extra rounding errors. Eventhough it might be sufficient in most situations, it is not mathematically correct.

  2. The round function in python rounds ties to +infinity for positive numbers and to -infinity for negative numbers. Therefore your comment is not correct and matches better with the comment of ‘nearest’.

  3. The nearest function is mostly implemented in a more straight forward way (without if-statement):
    retval = math.floor(val+0.5)
    It should round integers to the nearest integer and ties to +infinity (matches comment with ‘round’)
    Given the comment in 1, you should avoid converting to floating point number at all, so the implementation in fixbv should be a little different, but the concept should remain. There is no if-statement needed.

I hope this helps.

/offtopic
You describe problems in GSoC #4, #5, #6 and #7. I’ve solved these problems and infinite precision issues in the newest version of the myhdl-branch from Imec (“https://github.com/imec-myhdl/myhdl.git”). I’ve added testcases as well. I only noticed your updates now, otherwise I would have let you know sooner. It is a waste of energy to maintain two branches. I’d be happy to discuss a way forward to merge our work.


#3

Thanks for your detailed reply. We could discuss on how to merge our work together. Can you join our gitter or our IRC for further discussion?

By the way, I think my description on round function is true according to Python documentation.


#4

Ah, I see now that python 2.x and python 3.x behave in a different way.

Python 2.x rounds positive ties to +infinity and negative ties to -infinity, whereas Python 3.x rounds ties to the nearest even number. So if you rely on this property, please check (or make sure) Python 3.x is used.


#5

Python 2.7 must be supported too.