У меня есть 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 #.
источник
long.MinValue
иlong.MaxValue
среди ценностей.BigInteger
илиdecimal
исключается, или это только ради создания этого трудно?Ответы:
Этот код будет работать, но не очень.
Сначала он делит все три значения (он сводит значения к нулю, поэтому вы «теряете» остаток), а затем делит остаток:
Обратите внимание, что приведенный выше пример не всегда работает должным образом при наличии одного или нескольких отрицательных значений.
Как обсуждалось с Улугбеком, поскольку количество комментариев стремительно растет ниже, вот текущее ЛУЧШЕЕ решение как для положительных, так и для отрицательных значений.
Благодаря ответам и комментариям Улугбека Умирова , James S , KevinZ , Marc van Leeuwen , gnasher729 это текущее решение:
источник
(x + y + z) / 3 = x / 3 + y / 3 + z / 3
.f(1,1,2) == 1
в то время какf(-2,-2,8) == 2
(x+y)/3
слишком много.NB - Патрик уже дал отличный ответ . Расширяя это, вы можете сделать общую версию для любого количества целых чисел, например:
источник
long
небольших типов, но обратите внимание, что вторая сумма может переполняться.Патрик Хофман опубликовал отличное решение . Но при необходимости это еще можно реализовать несколькими другими способами. Используя алгоритм здесь, у меня есть другое решение. При тщательном внедрении он может быть быстрее, чем множественные подразделения в системах с медленными аппаратными делителями. Его можно дополнительно оптимизировать, используя технику деления на константы из хакерского восторга.
В C / C ++ на 64-битных платформах с
__int128
источник
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
необходимые корректировки .Вы можете рассчитать среднее значение чисел на основе разницы между числами, а не на основе суммы.
Скажем, x - это максимум, y - это медиана, z - это минимум (как у вас). Мы будем называть их максимальным, средним и минимальным.
Условный чекер добавлен в соответствии с комментарием @UlugbekUmirov:
источник
(double)(2 / 3)
равно 0,0?Поскольку C использует деление по полу, а не евклидово деление, может быть проще вычислить правильно округленное среднее трех значений без знака, чем трех значений со знаком. Просто добавьте 0x8000000000000000UL к каждому числу перед взятием среднего без знака, вычтите его после получения результата и используйте непроверенное приведение к,
Int64
чтобы получить среднее значение со знаком.Чтобы вычислить беззнаковое среднее, вычислите сумму верхних 32 бита трех значений. Затем вычислите сумму нижних 32 бита трех значений, плюс сумму, полученную выше, плюс один [плюс один дает округленный результат]. Среднее значение будет в 0x55555555 раз больше первой суммы плюс одна треть второй.
Производительность на 32-разрядных процессоров может быть повышена за счет получения трех «сумма» значений , каждая из которых имеет длину 32 бита, таким образом , чтобы конечный результат
((0x55555555UL * sumX)<<32) + 0x55555555UL * sumH + sumL/3
; его можно было бы дополнительно улучшить, заменивsumL/3
на((sumL * 0x55555556UL) >> 32)
, хотя последний будет зависеть от JIT-оптимизатора [он может знать, как заменить деление на 3 умножением, и его код может быть более эффективным, чем явная операция умножения].источник
Patching Патрика Хофман «S решения с SUPERCAT коррекция» с, я даю вам следующее:
И случай N элемента:
Это всегда дает нижний предел () среднего и исключает все возможные крайние случаи.
источник
Вы можете использовать тот факт, что вы можете записать каждое из чисел как
y = ax + b
, гдеx
- константа. Каждыйa
будетy / x
(целая часть этого деления). Каждый b будетy % x
(остаток / по модулю этого деления). Если вы выберете эту константу разумным образом, например, выбрав квадратный корень из максимального числа в качестве константы, вы сможете получить среднее значениеx
чисел без проблем с переполнением.Среднее значение произвольного списка чисел можно найти, найдя:
где
%
обозначает по модулю и/
обозначает «целую» часть деления.Программа будет выглядеть примерно так:
источник
Если вы знаете, что у вас есть N значений, можете ли вы просто разделить каждое значение на N и просуммировать их вместе?
источник
Я также попробовал это и нашел более быстрое решение (хотя только примерно в 3/4 раза). Он использует одно деление
где
smallDiv3
деление на 3 с использованием умножения и работает только с небольшими аргументамиВот весь код, включая тест и бенчмарк, результаты не впечатляют.
источник
Эта функция вычисляет результат в двух делениях. Он должен хорошо обобщаться на другие делители и размеры слов.
Он работает, вычисляя результат сложения двойных слов, а затем вычисляя деление.
источник
Математика
Код
источник
{1,2,3}
ответ есть2
, но ваш код вернет1
.double
, поскольку в этом случае мы потеряем точность.Попробуй это:
источник