Среднее 3 длинных целых

У меня есть 3 очень больших целых числа со знаком.

long x = long.MaxValue;
long y = long.MaxValue - 1;
long z = long.MaxValue - 2;

Я хочу рассчитать их усеченное среднее. Ожидаемое среднее значение long.MaxValue - 1, который 9223372036854775806,

Невозможно рассчитать это как:

long avg = (x + y + z) / 3; // 3074457345618258600

Примечание. Я прочитал все эти вопросы о среднем по 2 числам, но не понимаю, как этот метод можно применить к среднему из 3 чисел.

Это было бы очень легко с использованием BigInteger, но давайте предположим, что я не могу его использовать.

BigInteger bx = new BigInteger(x);
BigInteger by = new BigInteger(y);
BigInteger bz = new BigInteger(z);
BigInteger bavg = (bx + by + bz) / 3; // 9223372036854775806

Если я преобразую в doubleтогда, конечно, я теряю точность

double dx = x;
double dy = y;
double dz = z;
double davg = (dx + dy + dz) / 3; // 9223372036854780000

Если я преобразую в decimal, это работает, но также давайте предположим, что я не могу его использовать.

decimal mx = x;
decimal my = y;
decimal mz = z;
decimal mavg = (mx + my + mz) / 3; // 9223372036854775806

Вопрос: есть ли способ вычислить усеченное среднее из 3 очень больших целых чисел только с использованием long тип? Не рассматривайте этот вопрос как специфичный для C#, просто мне проще предоставить примеры в C#.

12 ответов

Решение

Этот код будет работать, но он не так хорош.

Сначала он делит все три значения (он опускает значения, поэтому вы "теряете" остаток), а затем делит остаток:

long n = x / 3
         + y / 3
         + z / 3
         + ( x % 3
             + y % 3
             + z % 3
           ) / 3

Обратите внимание, что приведенный выше пример не всегда работает должным образом при наличии одного или нескольких отрицательных значений.

Как обсуждалось с Улугбеком, так как количество комментариев растет ниже, вот текущее ЛУЧШЕЕ решение для положительных и отрицательных значений.

Благодаря ответам и комментариям Ulugbek Umirov, James S, KevinZ, Marc van Leeuwen, gnasher729 это текущее решение:

static long CalculateAverage(long x, long y, long z)
{
    return (x % 3 + y % 3 + z % 3 + 6) / 3 - 2
            + x / 3 + y / 3 + z / 3;
}

static long CalculateAverage(params long[] arr)
{
    int count = arr.Length;
    return (arr.Sum(n => n % count) + count * (count - 1)) / count - (count - 1)
           + arr.Sum(n => n / count);
}

NB - Патрик уже дал отличный ответ. Расширяя это, вы можете сделать универсальную версию для любого числа целых чисел, например так:

long x = long.MaxValue;
long y = long.MaxValue - 1;
long z = long.MaxValue - 2;

long[] arr = { x, y, z };
var avg = arr.Select(i => i / arr.Length).Sum() 
        + arr.Select(i => i % arr.Length).Sum() / arr.Length;

Патрик Хофман опубликовал отличное решение. Но при необходимости он все еще может быть реализован несколькими другими способами. Используя алгоритм здесь у меня есть другое решение. При тщательном внедрении это может быть быстрее, чем множественные деления в системах с медленными аппаратными делителями. Это может быть дополнительно оптимизировано с помощью метода деления на константы от удовольствия хакера

public class int128_t {
    private int H;
    private long L;

    public int128_t(int h, long l)
    {
        H = h;
        L = l;
    }

    public int128_t add(int128_t a)
    {
        int128_t s;
        s.L = L + a.L;
        s.H = H + a.H + (s.L < a.L);
        return b;
    }

    private int128_t rshift2()  // right shift 2
    {
        int128_t r;
        r.H = H >> 2;
        r.L = (L >> 2) | ((H & 0x03) << 62);
        return r;
    }

    public int128_t divideby3()
    {
        int128_t sum = {0, 0}, num = new int128_t(H, L);
        while (num.H || num.L > 3)
        {
            int128_t n_sar2 = num.rshift2();
            sum = add(n_sar2, sum);
            num = add(n_sar2, new int128_t(0, num.L & 3));
        }

        if (num.H == 0 && num.L == 3)
        {
            // sum = add(sum, 1);
            sum.L++;
            if (sum.L == 0) sum.H++;
        }
        return sum; 
    }
};

int128_t t = new int128_t(0, x);
t = t.add(new int128_t(0, y));
t = t.add(new int128_t(0, z));
t = t.divideby3();
long average = t.L;

В C/C++ на 64-битных платформах гораздо проще __int128

int64_t average = ((__int128)x + y + z)/3;

Вы можете рассчитать среднее число на основе различий между числами, а не с использованием суммы.

Скажем, x - это максимум, y - это медиана, z - это минимум (как у вас). Мы назовем их Макс, Медиана и Мин.

Условная проверка добавлена ​​согласно комментарию @UlugbekUmirov:

long tmp = median + ((min - median) / 2);            //Average of min 2 values
if (median > 0) tmp = median + ((max - median) / 2); //Average of max 2 values
long mean;
if (min > 0) {
    mean = min + ((tmp - min) * (2.0 / 3)); //Average of all 3 values
} else if (median > 0) {
    mean = min;
    while (mean != tmp) {
        mean += 2;
        tmp--;
    }
} else if (max > 0) {
    mean = max;
    while (mean != tmp) {
        mean--;
        tmp += 2;
    }
} else {
    mean = max + ((tmp - max) * (2.0 / 3));
}

Я supercat решение Patrick Hofman и supercat, я дам вам следующее:

static Int64 Avg3 ( Int64 x, Int64 y, Int64 z )
{
    UInt64 flag = 1ul << 63;
    UInt64 x_ = flag ^ (UInt64) x;
    UInt64 y_ = flag ^ (UInt64) y;
    UInt64 z_ = flag ^ (UInt64) z;
    UInt64 quotient = x_ / 3ul + y_ / 3ul + z_ / 3ul
        + ( x_ % 3ul + y_ % 3ul + z_ % 3ul ) / 3ul;
    return (Int64) (quotient ^ flag);
}

И случай N элемента:

static Int64 AvgN ( params Int64 [ ] args )
{
    UInt64 length = (UInt64) args.Length;
    UInt64 flag = 1ul << 63;
    UInt64 quotient_sum = 0;
    UInt64 remainder_sum = 0;
    foreach ( Int64 item in args )
    {
        UInt64 uitem = flag ^ (UInt64) item;
        quotient_sum += uitem / length;
        remainder_sum += uitem % length;
    }

    return (Int64) ( flag ^ ( quotient_sum + remainder_sum / length ) );
}

Это всегда дает слово () среднего значения и исключает все возможные крайние случаи.

Если вы знаете, что у вас есть N значений, вы можете просто разделить каждое значение на N и сложить их вместе?

long GetAverage(long* arrayVals, int n)
{
    long avg = 0;
    long rem = 0;

    for(int i=0; i<n; ++i)
    {
        avg += arrayVals[i] / n;
        rem += arrayVals[i] % n;
    }

    return avg + (rem / n);
}

Поскольку в С используется деление по этажам, а не евклидово, может быть проще вычислить правильное округленное среднее из трех беззнаковых значений, чем трех знаковых. Просто добавьте 0x8000000000000000UL к каждому числу, прежде чем брать среднее значение без знака, вычтите его после получения результата и используйте непроверенное приведение к Int64 чтобы получить подписанное среднее.

Чтобы вычислить среднее значение без знака, вычислите сумму старших 32 битов из трех значений. Затем вычислите сумму младших 32 битов трех значений, плюс сумму сверху плюс один [плюс один, чтобы получить округленный результат]. Среднее значение будет 0x55555555, умноженное на первую сумму, плюс треть от второй.

Производительность на 32-битных процессорах может быть повышена путем создания трех "суммированных" значений, каждое из которых имеет длину 32 бита, так что конечный результат ((0x55555555UL * sumX)<<32) + 0x55555555UL * sumH + sumL/3; это может быть еще более улучшено путем замены sumL/3 с ((sumL * 0x55555556UL) >> 32)хотя последний будет зависеть от оптимизатора JIT [он может знать, как заменить деление на 3 умножением, и его код может фактически быть более эффективным, чем явная операция умножения].

Вы можете использовать тот факт, что вы можете написать каждое из чисел как y = ax + b, где x постоянная каждый a было бы y / x (целочисленная часть этого деления). Каждый б будет y % x (остальное / по модулю этого подразделения). Если вы выберете эту константу разумным способом, например, выбрав квадратный корень из максимального числа в качестве константы, вы можете получить среднее значение x числа без проблем с переполнением.

Среднее произвольного списка чисел можно найти, найдя:

( ( sum( all A's ) / length ) * constant ) + 
( ( sum( all A's ) % length ) * constant / length) +
( ( sum( all B's ) / length )

где % обозначает по модулю и / обозначает "целую" часть деления.

Программа будет выглядеть примерно так:

class Program
{
    static void Main()
    {
        List<long> list = new List<long>();
        list.Add( long.MaxValue );
        list.Add( long.MaxValue - 1 );
        list.Add( long.MaxValue - 2 );

        long sumA = 0, sumB = 0;
        long res1, res2, res3;
        //You should calculate the following dynamically
        long constant = 1753413056;

        foreach (long num in list)
        {
            sumA += num / constant;
            sumB += num % constant;
        }

        res1 = (sumA / list.Count) * constant;
        res2 = ((sumA % list.Count) * constant) / list.Count;
        res3 = sumB / list.Count;

        Console.WriteLine( res1 + res2 + res3 );
    }
}

Я также попробовал это и придумал более быстрое решение (хотя только в 3/4 раза). Он использует одно деление

public static long avg(long a, long b, long c) {
    final long quarterSum = (a>>2) + (b>>2) + (c>>2);
    final long lowSum = (a&3) + (b&3) + (c&3);
    final long twelfth = quarterSum / 3;
    final long quarterRemainder = quarterSum - 3*twelfth;
    final long adjustment = smallDiv3(lowSum + 4*quarterRemainder);
    return 4*twelfth + adjustment;
}

где smallDiv3 деление на 3 с использованием умножения и работает только для небольших аргументов

private static long smallDiv3(long n) {
    assert -30 <= n && n <= 30;
    // Constants found rather experimentally.
    return (64/3*n + 10) >> 6;
}

Вот весь код, включая тест и тест, результаты не так впечатляют.

Эта функция вычисляет результат в двух делениях. Он должен быть хорошо обобщен на другие делители и размеры слов.

Он работает путем вычисления результата сложения двойных слов, а затем вырабатывает деление.

Int64 average(Int64 a, Int64 b, Int64 c) {
    // constants: 0x10000000000000000 div/mod 3
    const Int64 hdiv3 = UInt64(-3) / 3 + 1;
    const Int64 hmod3 = UInt64(-3) % 3;

    // compute the signed double-word addition result in hi:lo
    UInt64 lo = a; Int64 hi = a>=0 ? 0 : -1;
    lo += b; hi += b>=0 ? lo<b : -(lo>=UInt64(b));
    lo += c; hi += c>=0 ? lo<c : -(lo>=UInt64(c));

    // divide, do a correction when high/low modulos add up
    return hi>=0 ? lo/3 + hi*hdiv3 + (lo%3 + hi*hmod3)/3
                 : lo/3+1 + hi*hdiv3 + Int64(lo%3-3 + hi*hmod3)/3;
}

математический

(x + y + z) / 3 = x/3 + y/3 + z/3

(a[1] + a[2] + .. + a[k]) / k = a[1]/k + a[2]/k + .. + a[k]/k

Код

long calculateAverage (long a [])
{
    double average = 0;

    foreach (long x in a)
        average += (Convert.ToDouble(x)/Convert.ToDouble(a.Length));

    return Convert.ToInt64(Math.Round(average));
}

long calculateAverage_Safe (long a [])
{
    double average = 0;
    double b = 0;

    foreach (long x in a)
    {
        b = (Convert.ToDouble(x)/Convert.ToDouble(a.Length));

        if (b >= (Convert.ToDouble(long.MaxValue)-average))
            throw new OverflowException ();

        average += b;
    }

    return Convert.ToInt64(Math.Round(average));
}

Попробуй это:

long n = Array.ConvertAll(new[]{x,y,z},v=>v/3).Sum()
     +  (Array.ConvertAll(new[]{x,y,z},v=>v%3).Sum() / 3);
Другие вопросы по тегам