What is the fastest way to discretize double in C#?

Question

I have a double between -1 and 1.

I need to discretize it by N steps it really, really fast. If N is 5 my end values would be one of these:

-1,-0.8,-0.6,-0.4,-0.2,0,0.2,0.4,0.6,0.8,1

I need a function:

double discretize(double value)

so that for example:

discretize(0.091231) = 0
discretize(0.192312) = 0.2

I wonder if there's any trick with the mantissa/exponent, to make it discrete with bit shifts etc... without making any floating-point arithmetics.

If you need to hack some code to do it really really fast you really really should not pick values that are totally not a powers of 2 as it is really really unlikely any dirty hack bitwise would be able to handle powers of 5... (What you really really should do is try and measure... converting double to long would likely take more time than just divide and round) — Alexei Levenkov, Jun 30 '20 at 21:54
@AlexeiLevenkov - It's amazing what people think take time to compute these days. The worst offender is always out of cache memory access, worst than calculating square roots etc. So unless you profile your code, doing micro-optimizations is always a bad idea as it obfuscates the purpose of the code. — John Alexiou, Jun 30 '20 at 23:27

John Alexiou · Answer 1 · 2020-07-01T18:52:35.080

1

Sounds like a rounding operation.

static class Program
{
    static readonly Random rng = new Random();
    static void Main(string[] args)
    {
        for (int i = 0; i < 15; i++)
        {
            var x = rng.NextDouble();
            Debug.WriteLine($"{x,-15} = {x.Quantize(5)}");
        }
    }

    public static double Quantize(this double x, int steps)
    {
        return Math.Round(x*steps)/steps;
    }
}

with the program output

0.45652442819277 = 0.4
0.649511796259094 = 0.6
0.605691870490877 = 0.6
0.685007393679119 = 0.6
0.489223629929695 = 0.4
0.496371834304357 = 0.4
0.153276258685289 = 0.2
0.212714763457288 = 0.2
0.0338650732458872 = 0
0.0612733452866195 = 0
0.258718123314305 = 0.2
0.906546349593693 = 1
0.39698489727312 = 0.4
0.728462797928817 = 0.8
0.140497107589849 = 0.2

PS. Since you are doing division after the round it might better to use the ToEven option

Math.Round(x*steps, MidpointRounding.ToEven)/steps

If you want fast speed then switch from double to float and use the functions in System.Numerics to load multiple values in vectors.

Also decorate the functions with aggressive inlining which in turn has a better chance to produce vectorized code by the JIT.

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static double Quantize(this double x, int steps)
    {
        return Math.Round(x*steps)/steps;
    }

Finally, consider doing this math processing with C++ or even better Fortran (maybe even Julia) using a library.

edited Jul 01 '20 at 18:52

answered Jun 30 '20 at 23:20

John Alexiou

28,472
11
77
133

Thank you! This is great. Could we further optimize this somehow? I'd like to avoid floating point division, it's the slowest. This will run like billion times per second. Maybe casting to int to have an index and having a lookup array with precalculated values? – Rob The Quant Jul 01 '20 at 12:37
Do you _know_ division is a bottle neck. usually memory access is many times slower than math operations which are handled by the `x87` co-processor. – John Alexiou Jul 01 '20 at 18:45
1

If `n` is a power of two, then you can use bit-shifting maybe. – John Alexiou Jul 01 '20 at 18:46
yes, n can be the power of two and I'd like to do bit shifting. this is for ML project where I'll run it a billion times per second so yes speed is super important. and yes all my other functions are super optimized too. – Rob The Quant Jul 01 '20 at 21:20
I tried using [this answer](https://stackoverflow.com/questions/389993/extracting-mantissa-and-exponent-from-double-in-c-sharp) and then bit shifting the mantissa, but it didn't work. – John Alexiou Jul 02 '20 at 00:07
Thanks for trying! I think this would be much faster than round: Math.Floor(0.5+x*steps)/steps; – Rob The Quant Jul 02 '20 at 01:27
`Math.Floor()` and `Math.Round()` should be about the same, since they both rely on similar code. [Source code here](https://github.com/dotnet/runtime/blob/1387cec8555dfd75b528b8871e7e931f220836cb/src/coreclr/src/jit/utils.cpp) for both. Look for `double FloatingPointUtils::round(double x)` – John Alexiou Jul 02 '20 at 03:24
or [math.cpp](https://github.com/dotnet/runtime/blob/4f9ae42d861fcb4be2fcd5d3d55d5f227d30e723/src/coreclr/src/pal/src/cruntime/math.cpp) – John Alexiou Jul 02 '20 at 03:35
I have coded it with IL like this, so far it's fast. Unless someone can think of a way to make it faster :) public static MethodInfo MathRound = typeof(Math).GetMethod("Round", new Type[] { typeof(double) }); static unsafe void Quantize(ILGenerator il) { //must have r8 on stack il.Emit(OpCodes.Ldc_R8, DISCRETIZE_STEP); il.Emit(OpCodes.Mul); il.Emit(OpCodes.Call, MathRound); il.Emit(OpCodes.Ldc_R8, DISCRETIZE_STEP); il.Emit(OpCodes.Div); } – Rob The Quant Jul 02 '20 at 15:41
@RobTheQuant - don't post that in the comments. Add an answer with the code. Yes, you can answer your own question. – John Alexiou Jul 02 '20 at 20:20
For shits and giggles try also `Math.Round((float)x*steps)/steps`. Maybe the `float` round is faster. – John Alexiou Jul 02 '20 at 20:22

score 0 · Accepted Answer · answered Oct 15 '20 at 19:32

0

Fastest method so far:

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static double Quantize(this double x, int steps)
{
    return ((double)((int)(x*steps+0.5)))/steps;
}

answered Oct 15 '20 at 19:32

Rob The Quant

347
3
15

What is the fastest way to discretize double in C#?

2 Answers2