CODEWITHSUNDEEP
cfloating-pointintdfixed-point
Core Xii
Core Xii

Reputation: 6441

Integer type with floating point semantics for C or D

I'm looking for an existing implementation for C or D, or advice in implementing, signed and/or unsigned integer types with floating point semantics.

That is to say, an integer type that behaves as floating point types do when doing arithmetic: Overflow produces infinity (-infinity for signed underflow) rather than wrapping around or having undefined behavior, undefined operations produce NaN, etc.

In essence, a version of floating point where the distribution of presentable numbers falls evenly on the number line, instead of conglomerating around 0.

In addition, all operations should be deterministic; any given two's complement 32-bit architecture should produce the exact same result for the same computation, regardless of its implementation (whereas floating point may, and often will, produce slightly differing results).

Finally, performance is a concern, which has me worried about potential "bignum" (arbitrary-precision) solutions.

See also: Fixed-point and saturation arithmetic.

Upvotes: 9

Views: 285

Answers (4)

Mike Sherrill 'Cat Recall'
Mike Sherrill 'Cat Recall'

Reputation: 95562

One solution might be to implement multiple-precision arithmetic with abstract data types. The book C Interfaces and Implementations by David Hanson has a chapter (interface and implementation) of MP arithmetic.

Doing calculations using scaled integers is also a possibility. You might be able to use his arbitrary-precision arithmetic, although I believe this implementation can't overflow. You could run out of memory, but that's a different problem.

In either case, you might need to tweak the code to return exactly what you want on overflow and such.

Source code (MIT license)

That page also has a link to buy the book from amazon.com.

Upvotes: 2

Aki Suihkonen
Aki Suihkonen

Reputation: 20027

Half of the requirements are satisfied in saturating arithmetic, which are implemented in e.g. ARM instructions, MMX and SSE.

As also pointed out by Stephen Canon, one needs additional elements to check overflow / NaN. Some instruction sets (Atmel at least) btw have a sticking flag to test for overflows (could be used to differentiate inf from max_int). And perhaps "Q" + 0 could mark for NaN.

Upvotes: 0

Stephen Canon
Stephen Canon

Reputation: 106167

Saturating arithmetic does what you want except for the part where undefined operations produce NaN; this is going to turn out to be problematic, because most saturating implementations use the full number range, and so there are not values left over to reserve for NaN. Thus, you probably can't easily build this on the back of saturating hardware instructions unless you have an additional "is this value NaN" field, which is rather wasteful.

Assuming that you're wedded to the idea of NaN values, all of the edge case detection will probably need to happen in software. For most integer operations, this is pretty straightforward, especially if you have a wider type available (let's assume long long is strictly larger than whatever integer type underlies myType):

myType add(myType x, myType y) {
    if (x == positiveInfinity && y == negativeInfinity ||
        x == negativeInfinity && y == positiveInfinity)
        return notANumber;
    long long wideResult = x + y;
    if (wideResult >= positiveInfinity) return positiveInfinity;
    if (wideResult <= negativeInfinity) return negativeInfinity;
    return (myType)wideResult;
}

Upvotes: 2

user438034
user438034

Reputation:

I do not know of any existing implementations of this.

But I would imagine implementing it would be a matter of (in D):

enum CheckedIntState : ubyte
{
    ok,
    overflow,
    underflow,
    nan,
}

struct CheckedInt(T)
    if (isIntegral!T)
{
    private T _value;
    private CheckedIntState _state;

    // Constructors, getters, conversion helper methods, etc.

    // And a bunch of operator overloads that check the
    // result on every operation and yield a CheckedInt!T
    // with an appropriate state.

    // You'll also want to overload opEquals and opCmp and
    // make them check the state of the operands so that
    // NaNs compare equal and so on.
}

Upvotes: 3

Related Questions