In C # möchte ich Doubles auf eine niedrigere Genauigkeit runden, damit ich sie in Buckets unterschiedlicher Größe in einem assoziativen Array speichern kann. Im Gegensatz zur üblichen Rundung möchte ich auf eine Reihe von signifikanten Bits runden. Somit ändern sich große Zahlen in absoluten Zahlen viel mehr als kleine Zahlen, aber sie ändern sich tendenziell proportional. Wenn ich also auf 10 Binärziffern runden möchte, finde ich die zehn höchstwertigen Bits und ziehe alle unteren Bits auf Null, wobei ich möglicherweise eine kleine Zahl zum Aufrunden hinzufüge.

Ich bevorzuge die Aufrundung von "halben" Zahlen.

Wenn es ein ganzzahliger Typ wäre, wäre hier ein möglicher Algorithmus:

  1. Find: zero-based index of the most significant binary digit set H.
  2. Compute: B = H - P, 
       where P is the number of significant digits of precision to round
       and B is the binary digit to start rounding, where B = 0 is the ones place, 
       B = 1 is the twos place, etc. 
  3. Add: x = x + 2^B 
       This will force a carry if necessary (we round halfway values up).
  4. Zero out: x = x mod 2^(B+1). 
       This clears the B place and all lower digits.

Das Problem besteht darin, einen effizienten Weg zu finden, um die höchste Bitmenge zu finden. Wenn ich Ganzzahlen verwende, gibt es coole Bit-Hacks, um das MSB zu finden. Ich möchte Round (Log2 (x)) nicht anrufen, wenn ich helfen kann. Diese Funktion wird viele Millionen Male aufgerufen.

Hinweis: Ich habe diese SO-Frage gelesen:

Was ist ein guter Weg, um Werte mit doppelter Genauigkeit auf eine (etwas) niedrigere Genauigkeit zu runden?

Es funktioniert für C ++. Ich benutze C #.

AKTUALISIEREN:

Dies ist der Code (geändert von dem, was der Antwortende angegeben hat), während ich ihn verwende:

/// <summary>
/// Round numbers to a specified number of significant binary digits.
/// 
/// For example, to 3 places, numbers from zero to seven are unchanged, because they only require 3 binary digits,
/// but larger numbers lose precision:
/// 
///      8    1000 => 1000   8
///      9    1001 => 1010  10
///     10    1010 => 1010  10
///     11    1011 => 1100  12
///     12    1100 => 1100  12
///     13    1101 => 1110  14
///     14    1110 => 1110  14
///     15    1111 =>10000  16
///     16   10000 =>10000  16
///     
/// This is different from rounding in that we are specifying the place where rounding occurs as the distance to the right
/// in binary digits from the highest bit set, not the distance to the left from the zero bit.
/// </summary>
/// <param name="d">Number to be rounded.</param>
/// <param name="digits">Number of binary digits of precision to preserve. </param>
public static double AdjustPrecision(this double d, int digits)
{
    // TODO: Not sure if this will work for both normalized and denormalized doubles. Needs more research.
    var shift = 53 - digits; // IEEE 754 doubles have 53 bits of significand, but one bit is "implied" and not stored.
    ulong significandMask = (0xffffffffffffffffUL >> shift) << shift;
    var local_d = d;
    unsafe
    {
        // double -> fixed point (sorta)
        ulong toLong = *(ulong*)(&local_d);
        // mask off your least-sig bits
        var modLong = toLong & significandMask;
        // fixed point -> float (sorta)
        local_d = *(double*)(&modLong);
    }
    return local_d;
}

UPDATE 2: Dekkers Algorithmus

Ich habe dies dank des anderen Befragten aus Dekkers Algorithmus abgeleitet. Es wird auf den nächsten Wert gerundet, anstatt wie im obigen Code abgeschnitten zu werden, und es wird nur sicherer Code verwendet:

private static double[] PowersOfTwoPlusOne;

static NumericalAlgorithms()
{
    PowersOfTwoPlusOne = new double[54];
    for (var i = 0; i < PowersOfTwoPlusOne.Length; i++)
    {
        if (i == 0)
            PowersOfTwoPlusOne[i] = 1; // Special case.
        else
        {
            long two_to_i_plus_one = (1L << i) + 1L;
            PowersOfTwoPlusOne[i] = (double)two_to_i_plus_one;
        }
    }
}

public static double AdjustPrecisionSafely(this double d, int digits)
{
    double t = d * PowersOfTwoPlusOne[53 - digits];
    double adjusted = t - (t - d);
    return adjusted;
}

UPDATE 2: TIMINGS

Ich habe einen Test durchgeführt und festgestellt, dass Dekkers Algorithmus besser als ZWEIMAL so schnell ist!

Anzahl der Anrufe im Test: 100.000.000
Unsichere Zeit = 1,922 (Sek.)
Sichere Zeit = 0,799 (Sek.)