W C # chcę zaokrąglić podwajając do niższej precyzji, dzięki czemu mogę przechowywać je w segmentach o różnej wielkości w tablicy asocjacyjnej. W przeciwieństwie do zwykłego zaokrąglania, chcę zaokrąglić do kilku znaczących bitów. Tak więc duże liczby będą się zmieniać w wartościach bezwzględnych znacznie więcej niż małe liczby, ale będą się one zmieniać proporcjonalnie. Więc jeśli chcę zaokrąglić do 10 cyfr binarnych, znajduję dziesięć najważniejszych bitów i zeruję wszystkie niższe bity, ewentualnie dodając małą liczbę do zaokrąglenia w górę.

Wolę zaokrąglać liczby w połowie.

Gdyby był typem całkowitym, tutaj byłby możliwy algorytm:

  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.

Problem polega na znalezieniu skutecznego sposobu znalezienia najwyższego zestawu bitów. Gdybym używał liczb całkowitych, są fajne hacki bitowe do znalezienia MSB. Nie chcę dzwonić do Rundy (Log2 (x)), jeśli mogę na to pomóc. Ta funkcja zostanie wywołana wiele milionów razy.

Uwaga: przeczytałem to pytanie SO:

Jaki jest dobry sposób na zaokrąglenie wartości podwójnej precyzji do (nieco) niższej precyzji?

Działa dla C ++. Używam C #.

AKTUALIZACJA:

To jest kod (zmodyfikowany od tego, co dostarczył odpowiadający), gdy go używam:

/// <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;
}

AKTUALIZACJA 2: Algorytm Dekkera

Wyprowadziłem to z algorytmu Dekkera, dzięki drugiemu respondentowi. Zaokrągla do najbliższej wartości, zamiast obcinania, jak to robi powyższy kod, i używa tylko bezpiecznego kodu:

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

Przeprowadziłem test i stwierdziłem, że algorytm Dekkera jest lepszy niż DWA razy szybszy!

Liczba testowanych połączeń: 100 000 000
Niebezpieczny czas = 1,922 (s)
Czas bezpieczny = 0,799 (s)