Среднее значение 3 длинных целых чисел

103

У меня есть 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

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

Улугбек Умиров
источник
1
почему бы не рассчитать общую среднюю разницу и не вычесть ее из максимальной?
Андреас Нидермайр
6
@AndreasNiedermair Не сработает, если у меня есть long.MinValueи long.MaxValueсреди ценностей.
Улугбек Умиров
действительно хороший улов :)
Андреас Нидермайр
Вы уверены, что нам нужно об этом беспокоиться, разве это не должно быть решено фреймворком?
Болу
11
Есть ли фактическая причина того, что BigIntegerили decimalисключается, или это только ради создания этого трудно?
jpmc26

Ответы:

142

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

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

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

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

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

Благодаря ответам и комментариям Улугбека Умирова , 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);
}
Патрик Хофман
источник
3
@DavidG Нет. По математике (x + y + z) / 3 = x / 3 + y / 3 + z / 3.
Крис Вандермоттен
4
Я использовал Z3, чтобы доказать, что это верно для всех значений числа переменных от 1 до 5.
usr
5
Конечно, кажется, что это работает, но способ работы с усечением целых чисел может вас запутать. f(1,1,2) == 1в то время какf(-2,-2,8) == 2
KevinZ
11
Обратите внимание, что из-за поврежденной мозгом семантики операции по модулю это может дать результат, отличный от единицы, а именно округление в большую, а не в меньшую сторону, если разрешены отрицательные значения для переменных. Например, если x, y кратны 3, а z равно -2, вы получите (x+y)/3слишком много.
Марк ван Леувен
6
@KevinZ: ... чей эффект затем должен быть отменен программистом, который вообще никогда не хотел такого особого поведения. Позволить программисту указать модуль вместо того, чтобы выводить его из остатка, который компилятор мог получить из модуля, может показаться полезным.
supercat
26

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;
Джеймс С.
источник
1
Этого не произойдет для longнебольших типов, но обратите внимание, что вторая сумма может переполняться.
user541686
7

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

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;
Phuclv
источник
2
Я бы предположил, что хороший способ разделить 32-битное беззнаковое значение на 3 - это умножить на 0x55555555L, добавить 0x55555555 и сдвинуть вправо на 32. Для сравнения, ваш метод diverby3 выглядит так, как будто он потребует множества дискретных шагов.
supercat
@supercat да, я знаю этот метод. Метод от радости хакера даже более правильный, но я займусь реализацией в другой раз
phuclv
Я не уверен, что значит «правильнее». Взаимное умножение может во многих случаях давать точные значения напрямую или же давать значения, которые можно уточнить за один или два шага. Кстати, я думаю, что мне следовало предложить умножение на 0x55555556, которое затем дало бы точные результаты без необходимости «сложения». Кроме того, правильно ли ваше условие цикла? Что изменяет H и L в петле?
supercat
Между прочим, даже если у вас нет аппаратного умножения, можно быстро аппроксимировать беззнаковое переходное x=y/3отверстие x=y>>2; x+=x>>2; x+=x>>4; x+=x>>8; x+=x>>16; x+=x>>32;. Результат будет очень близок к x, и его можно будет уточнить, вычислив delta=y-x-x-x;и применив xнеобходимые корректировки .
supercat
1
@ gnasher729 Мне интересно, может ли он использовать эту оптимизацию на 32-битных компьютерах, поскольку он часто не может выполнять 64x64 → 128-битное умножение
phuclv
7

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

Скажем, 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));
}
La-comadreja
источник
2
См. Комментарий @ UlugbekUmirov: Не сработает, если у меня будут long.MinValue и long.MaxValue среди значений
Болу
@Bolu комментарий применим только к long.MinValue. Поэтому я добавил это условие, чтобы оно работало в нашем случае.
La-comadreja
Как можно использовать медиану, если она не инициализирована?
phuclv
@ LưuVĩnhPhúc, медиана - это значение между минимумом и максимумом.
La-comadreja
1
не (double)(2 / 3)равно 0,0?
phuclv
5

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

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

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

суперкар
источник
После добавления 0x8000000000000000UL переполнение не влияет на результат?
phuclv
@ LưuVĩnhPhúc Переполнения нет. Перейдите к моему ответу за реализацией. Однако в разделении на 2 32-битных int не было необходимости.
KevinZ
@KevinZ: Разделение каждого значения на верхнюю и нижнюю 32-битные части выполняется быстрее, чем разделение на частное и остаток деления на три.
supercat
1
@ LưuVĩnhPhúc: в отличие от значений со знаком, которые ведут себя семантически как числа и не допускают переполнения в законной программе C, значения без знака обычно ведут себя как члены абстрактного алгебраического кольца оболочки, поэтому семантика упаковки хорошо определена.
supercat
1
Кортеж представляет -3, -2, -1. После добавления 0x8000U к каждому значению, значения должны быть разделены пополам: 7F + FF 7F + FE 7F + FD. Складываем верхнюю и нижнюю половинки, получая 17D + 2FA. Добавьте сумму верхней половины к сумме нижней половины, получив 477. Умножьте 17D на 55, получив 7E81. Разделите 477 на три, получим 17D. Добавьте 7E81 к 17D, получив 7FFE. Вычтите из этого 8000 и получите -2.
supercat
5

Patching Патрика Хофман «S решения с 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 ) );
}

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

KevinZ
источник
1
Я перевел AvgN в код Z3 и доказал, что это правильно для всех разумных размеров ввода (например, 1 <= args.Length <= 5 и размер битового вектора 6). Это правильный ответ.
usr
Замечательный ответ Кевин. Спасибо за ваш вклад! meta.stackoverflow.com/a/303292/993547
Патрик Хофман,
4

Вы можете использовать тот факт, что вы можете записать каждое из чисел как y = ax + b, где x- константа. Каждый aбудет y / x(целая часть этого деления). Каждый b будет 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 );
    }
}
Сумурай8
источник
4

Если вы знаете, что у вас есть 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);
}
абеленки
источник
это то же самое, что и решение Патрика Хофмана, если не менее правильное, чем окончательная версия
phuclv
2

Я также попробовал это и нашел более быстрое решение (хотя только примерно в 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;
}

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

мааартинус
источник
1

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

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

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;
}
Rřola
источник
0

Математика

(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));
}
Халед К.
источник
для набора {1,2,3}ответ есть 2, но ваш код вернет 1.
Улугбек Умиров
Исправлен код @UlugbekUmirov, для обработки должны использоваться двойные типы
Khaled.K 04
1
Вот чего я хочу избежать - использования double, поскольку в этом случае мы потеряем точность.
Улугбек Умиров
0

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

long n = Array.ConvertAll(new[]{x,y,z},v=>v/3).Sum()
     +  (Array.ConvertAll(new[]{x,y,z},v=>v%3).Sum() / 3);
trinalbadger587
источник