range_conversion_test.cpp

// Description: Brute-force test for range conversion
// Documentation: range.txt

// A brute force program to test
// for numerical conversion errors when
// converting between p-bit signed integers and [-1, 1] real range.
// The formulas are from my paper 
// "Converting between an integer range and a real range".
// This is a test suite to confirm the results.
// With real arithmetic, there should be no errors (except the intentional 
// -2^(p - 1) to -2^(p - 1) - 1 conversion, but we don't count that).
// However, conversion errors result from round-off errors when
// using floating point arithmetic. The test is to convert an integer to a 
// real and back to an integer. Then we test for equality.
// This is tested on every p-bit integer.
// (c) Kalle Rutanen, 3.3.2009.

// On my computer, using double precision, there
// were no errors when p is in the range [2, 32].

#include <iostream>
#include <cmath>
#include <string>
#include <cassert>

typedef int integer;
typedef double real;

template <typename Type>
class NoDeduction
{
public:
    typedef Type Result;
};

template <typename Type>
Type clamp(const Type& x,
           const typename NoDeduction<Type>::Result& xMin,
           const typename NoDeduction<Type>::Result& xMax)
{
    if (x < xMin)
    {
        return xMin;
    }

    if (x > xMax)
    {
        return xMax;
    }

    return x;
}

template <int P>
real dequantizeSigned(integer i)
{
    enum
    {
        N = (1 << (P - 1)) - 1
    };

    return clamp(i / ((real)N + 0.5), -1, 1);
}

template <int P>
integer quantizeSigned(real x)
{
    enum
    {
        N = (1 << (P - 1)) - 1
    };

    const real sign = (x >= 0) ? 0.5 : -0.5;

    return (integer)clamp(x * ((real)N + 0.5) + sign, -N, N);
}

template <int P>
void testBasicProperties()
{
    enum
    {
        N = (1 << (P - 1)) - 1
    };

    std::cout << P << "-bit" << std::endl;

    if (dequantizeSigned<P>(0) != 0 ||
        quantizeSigned<P>(0) != 0 ||
        quantizeSigned<P>(-1) != -N ||
        quantizeSigned<P>(1) != N)
    {
        std::cout << "Basic property violated." << std::endl;
    }
}

template <int P>
void testBruteForce()
{
    enum
    {
        N = (1 << (P - 1)) - 1
    };

    testBasicProperties<P>();

    integer failed = 0;
    for (integer i = -N;i <= N && i != -N - 1;++i)
    {
        const integer a = i;
        const real x = dequantizeSigned<P>(a);
        const integer b = quantizeSigned<P>(x);

        if (a != b)
        {
            ++failed;
        }
    }

    if (failed > 0)
    {
        std::cout << "Errors found = " << failed << std::endl;
    }
}

int main()
{
    std::cout << "Testing for conversion errors..." << std::endl;

    testBruteForce<2>();
    testBruteForce<3>();
    testBruteForce<4>();
    testBruteForce<5>();
    testBruteForce<6>();
    testBruteForce<7>();
    testBruteForce<8>();
    testBruteForce<9>();
    testBruteForce<10>();
    testBruteForce<11>();
    testBruteForce<12>();
    testBruteForce<13>();
    testBruteForce<14>();
    testBruteForce<15>();
    testBruteForce<16>();
    testBruteForce<17>();
    testBruteForce<18>();
    testBruteForce<19>();
    testBruteForce<20>();
    testBruteForce<21>();
    testBruteForce<22>();
    testBruteForce<23>();
    testBruteForce<24>();
    testBruteForce<25>();
    testBruteForce<26>();
    testBruteForce<27>();
    testBruteForce<28>();
    testBruteForce<29>();
    testBruteForce<30>();
    testBruteForce<31>();
    testBruteForce<32>();

    std::cout << "Done!" << std::endl;

    std::string tmp;
    std::getline(std::cin, tmp);

    return 0;
}