03.06.2025 13:01
StarPilgrim 70 5000 Источник


Казалось бы: сложно отыскать формулу проще, чем нахождение среднего арифметического. Однако код — не формула, вдобавок, если вы пишете на С++, то разного (и в основном неприятного) рода сюрпризы могут ожидать вас где угодно.

Постановка задачи: реализовать функцию uint32_t average(uint32_t a, uint32_t b), не используя типов шире, чем uint32_t, и затем обобщить этот подход на произвольное количество аргументов.

Небольшая преамбула: зачем я этим всем занимаюсь?
Позвольте мне привести здесь небольшой диалог (приписываемый Давиду Гилберту):

Математик Давид Гилберт отвечает на вопросы:
— Какая задача сейчас для науки наиболее важна?
— Поймать муху на обратной стороне Луны!
— А кому это надо?
— Это никому не надо. Но подумайте над тем, сколько важных сложнейших задач надо решить, чтобы это осуществить!


Два значения


Сразу оговорюсь: всюду под средним будет пониматься результат деления суммы аргументов нацело на их количество, иначе говоря, average(1, 1) это 1, и average(1, 2) это тоже 1, потому что$ 3 / 2$ будет 1 — то есть округляем всегда вниз.

Итак, сначала рассмотрим вариант наивный и, очевидно, неверный:

uint32_t average(uint32_t a, uint32_t b)
{
    return (a + b) / 2;
}

К сожалению или нет, но такое буквальное переложение школьной формулы в код будет очень часто давать неверный ответ, например: average(0x80000000, 0x80000000) будет равно нулю, а должно быть равно 0x80000000 — это происходит из-за переполнения uint32_t при сложении a + b, при этом важно заметить, что и аргументы, и конечный результат во всех случаях влезают в тип uint32_t . Таким образом, задача-то вполне корректна, в отличие от кода.

Почему бы не рассмотреть всё то же самое, но с типом uint8_t
Это подход, который я исповедовал в своих предыдущих статьях об алгоритмах деления: тут и тут. В данном случае он не сработает в своей наивной форме, так как компилятор неявно использует int для промежуточного значения. Для деталей можно обратиться к секции integral promotions.

Первая пришедшая мне в голову идея была основана лишь на интуиции и заключалась в следующем исправлении:

uint32_t average(uint32_t a, uint32_t b)
{
    return a / 2 + b / 2;
}

Проблемы с переполнением тут, конечно, быть не может, потому что a /2 и b /2 не превосходят половины от numeric_limits<uint32_t >::max(), но проблема с неправильными ответами остаётся актуальной: average(3, 3) будет равен...2, а не 3.

Несложно догадаться, если оба аргумента нечётны, при делении нацело на два отбрасывается два раза по половинке от единицы, поправим это:

uint32_t average(uint32_t a, uint32_t b)
{
    return a / 2 + b / 2 + (a & b & 1);
}

Этот вариант — верный, но методически бесполезный: для обобщения его даже для трёх аргументов придётся внести правки, чем мы сейчас и займёмся.

Для самых дотошных
Конечно, это не все способы найти среднее двух чисел, а именно: есть вариант избавиться от одного деления, но он может страдать от underflow, что потребует кода сравнения и перестановки двух чисел: $a + (b - a) / 2$.

А ещё есть способ избавиться от обоих делений, используя немного битовой магии: 
(a & b) + ((a ^ b) >> 1).

Однако обобщить эти способы на большее количество чисел не представляется возможным.

Три значения


Прежде чем идти дальше, повторим материальную часть: для пары натуральных чисел a и b (b не равно нулю) существует единственное представление вида:

$a = qb + r$

Где

$q \ge 0, r\ge0\ и\ r < b$

Здесь q — частное, r — остаток, а процесс нахождения чисел q и r, собственно говоря, и называется делением.

Если мы запишем все три значения в вышеприведённом виде, учтя, что b = 3, затем перегруппируем их, а уже потом разделим, то, во-первых, очевидно, ничего не изменится (от перестановки мест слагаемых сумма не меняется), а, во-вторых, получится следующее:

uint32_t average(uint32_t x1, uint32_t x2, uint32_t x3)
{
    return x1 / 3 + x2 / 3 + x3 / 3  + (x1 % 3 + x2 % 3 + x3 % 3) / 3;
}

Проговорим алгоритм словами: сначала сложим все частные, потом посмотрим: «добежали ли» остатки до целого значения или нет.

Выглядит неплохо, но может ли здесь быть переполнение? Короткий ответ — нет.

Действительно: x1 / 3 + x2 / 3 + x3 / 3 не превосходит максимального значения numeric_limits<uint32_t >::max(), а если быть ещё точнее: это будет максимальное из чисел, делимых на три и не превосходящих при этом numeric_limits<uint32_t >::max(). Пожалуй, я его посчитаю:

 cout << dec << numeric_limits<uint32_t>::max() - numeric_limits<uint32_t>::max() % 3 << ' ' << numeric_limits<uint32_t>::max() << endl;

Вывод:

4294967295 4294967295

То есть numeric_limits<uint32_t>::max() делится на 3 без остатка (если не верите — сосчитайте сумму его цифр и убедитесь, что она делится на 3), x1 / 3 + x2 / 3 + x3 / 3 будет равно исходному числу, а вторая часть с остатками будет нулевой. Случай, если один или более элементов меньше максимального значения, — довольно технический и проверяемый такими же рассуждениями — не будем тратить на это время.

N значений. Первая попытка


Обобщая код из нашего последнего примера, получаем:

uint32_t average(const vector<uint32_t>& nums)
{
    uint32_t  res = 0;
    uint32_t  rem = 0;
    uint32_t  size = nums.size();

    if (!size)
    {
        return 0;
    }

    for (const auto& x: nums)
    {
        res += x / size;
    }

    for (const auto& x: nums)
    {
        rem += x % size;
    }

    return res + rem / size;
}

Отлично, код выглядит, прямо скажем, незамысловато! А вот работает ли?

 cout  << average({1, 2, 3, 4, 5, 6, 7, 8, 9}) << endl;

Эта строчка предсказуемо выведет 5. Попробуем другой пример:

 cout  << hex <<  average(vector<uint32_t>(0x10001, 0x10000)) << endl;

Напомню, что первый аргумент в конструкторе вектора — это количество элементов, и второй — значение этих элементов, вывод будет:

0

Похоже, мы опять столкнулись с переполнением, но ведь выше мы разбирали, почему переполнения возникнуть не может? Или может?

Переполнение не может возникнуть здесь:

    for (const auto& x: nums)
    {
        res += x / size;
    }

И переполнение не может возникнуть здесь:

 return res + rem / size;

При условии, что rem сам по себе посчитан корректно.

Но оно может возникнуть и возникает здесь:

    for (const auto& x: nums)
    {
        rem += x % size;
    }

Проанализируем работу функции с данным вектором:

x / size равно 0, x % size равно самому x т.е. 0x10000, в то же время 0x10000 * 0x10001 = (0x10000 * 0x10000) + 0x10000 — первое слагаемое не влезает в 4 байта и даёт 0 — значит итоговый rem будет 0x10000 и при делении на 0x10001 мы получим 0.

N значений. Чиним алгоритм


В предыдущем абзаце была выявлена проблема с циклом накопления остатка rem — рассмотрим его подробнее. Например, не утруждаясь оперированием большими числами, возьмём вектор из трёх элементов — пусть каждый элемент будет равен 8, тогда x % size равно 2. А есть ли вообще смысл в накоплении суммарного остатка? Нет. Достаточно факта, что остаток превышает или равен модулю (модуль — он же размер вектора в данном контексте) и накопления остатка уже взятого по модулю. Так, на первом шаге мы получим rem = 2, на втором шаге мы не получим 4, вместо этого rem = 1, и инкрементация частного (quotient++).

Воплотим идею в код:

uint32_t average(const vector<uint32_t>& nums)
{
    if (!nums.size())
    {
        return 0;
    }
    
    uint32_t size = nums.size();
    uint32_t quotient = 0;
    uint32_t reminder = 0;
    
    for (const auto& x: nums)
    {
        quotient += x / size;
        uint32_t rem = x % size;
        
        if ((size - reminder) > rem)
        {
            reminder += rem;
        }
        else
        {
            quotient++;
            reminder += rem - size;
        }
    }
    return quotient;
}

Здесь в if мы контролируем переполнение, но не переполнение uint32_t, а переполнение нашего модуля (size). Если его нет, то просто накапливаем остаток — иначе пересчитываем остаток уже по модулю (size) и инкрементируем частное (quotient). Тут нужно понимать, что за одну итерацию частное (quotient) может увеличиться не больше чем на 1, потому что и reminder, и rem оба меньше модуля (size) — следовательно, их сумма меньше 2 * size.

Можно убедиться, что предыдущий пример отработает теперь верно, выведя 0x10000:

 cout  << hex <<  average(vector<uint32_t>(0x10001, 0x10000)) << endl;

Анализ алгоритма и замеры


В терминах О-большого полученный алгоритм ничем не отличается от своей наивной и страдающей от переполнений версии:

uint32_t naive_average(const vector<uint32_t>& nums)
{
    uint32_t  sum = 0;
    
    for (const auto& x: nums)
    {
        sum += x;
    }
    
    return sum / nums.size();
}

В обоих случаях количество итераций равно размеру вектора, и в каждой итерации выполняется конечное, не зависящее от размера вектора, число операций — то есть это линейная сложность O(n). Однако в реальном мире чистогана и наживы, где процессорные такты превращаются в секунды выполнения — те секунды, которые пользователи проведут в ожидании результата, — в этом мире эти два алгоритма существенно отличаются. Почему? Потому что деление довольно медленная операция, и, если в naive_average на весь алгоритм у нас одно деление, то в алгоритме без переполнений — столько, сколько элементов в векторе.

Однако на данный момент это всего лишь гипотеза — нужно подкрепить её результатами измерений.

#include <iostream>
#include <vector>
#include <chrono>
#include <cstdint>
#include <random>

using namespace std;
using namespace std::chrono;

uint32_t average(const vector<uint32_t>& nums) {
    if (nums.empty()) {
        return 0;
    }
    
    uint32_t size = nums.size();
    uint32_t quotient = 0;
    uint32_t reminder = 0;
    
    for (const auto& x : nums) {
        quotient += x / size;
        uint32_t rem = x % size;
        
        if ((size - reminder) > rem) {
            reminder += rem;
        } else {
            quotient++;
            reminder += rem - size;
        }
    }
    return quotient;
}

uint32_t naive_average(const vector<uint32_t>& nums) {
    uint32_t sum = 0;
    for (const auto& x : nums) {
        sum += x;
    }
    return sum / nums.size();
}

vector<uint32_t> generate_test_data(size_t size) {
    vector<uint32_t> data;
    data.reserve(size);
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<uint32_t> dist(0, UINT32_MAX);
    for (size_t i = 0; i < size; ++i) {
        data.push_back(dist(gen));
    }
    return data;
}

template<typename Func>
long long measure_time(Func func, const vector<uint32_t>& data, uint32_t& result) {
    auto start = high_resolution_clock::now();
    result = func(data);
    auto end = high_resolution_clock::now();
    return duration_cast<milliseconds>(end - start).count();
}

int main() {
    vector<size_t> sizes = {100'000, 200'000, 400'000, 800'000, 1'600'000};
    
    cout << "Testing different vector sizes:\n";
    for (size_t size : sizes) {
        auto data = generate_test_data(size);
        uint32_t res_opt, res_naive;
        
        auto time_opt = measure_time(average, data, res_opt);
        auto time_naive = measure_time(naive_average, data, res_naive);
        
        cout << "Size: " << size << endl;
        cout << "  Optimized average:  " << time_opt << " ms\t Result: " << res_opt << endl;
        cout << "  Naive average:      " << time_naive << " ms\t Result: " << res_naive << endl;
        cout << "----------------------------------------\n";
    }
    
    return 0;
}

Собрав этот код с флагами -O3 в релизе, получим следующие результаты:

Testing different vector sizes:
Size: 10000000
Optimized Average: 14 ms Result: 2147686718
Naive average: 2 ms Result: 348
— Size: 20000000
Optimized Average: 25 ms Result: 2147422219
Naive average: 3 ms Result: 203
— Size: 40000000
Optimized Average: 49 ms Result: 2147451718
Naive average: 6 ms Result: 67
— Size: 80000000
Optimized Average: 103 ms Result: 2147364889
Naive average: 13 ms Result: 50
— Size: 160000000
Optimized Average: 200 ms Result: 2147464194
Naive average: 31 ms Result: 8
—

Видно, что версия алгоритма, учитывающая переполнение, медленнее в 7-8 раз наивного алгоритма. Может показаться, что разница весьма внушительна, но на самом деле такая разница вызывает вопросы, потому что деление обычно более чем в 10 раз медленнее сложения.
Железо, на котором запускали тесты: 13th Gen Intel® Core(TM) i7-13700H, 32 Гб ОЗУ.

Если посмотреть, как компилятор оптимизировал naive_average, например, в godbolt, то можно заметить, что компилятор использовал в ней SIMD-инструкции, в то время как в average — нет. В свете этого не столь большая разница в их времени выполнения становится ещё более загадочной, тем не менее — оставим исследование этого феномена до следующего раза (или до ответа в комментариях).





Выводы


Даже простые формулы и привычные математические операции часто утрачивают свои аксиоматические свойства, будучи реализованными на реальном «железе».

Несмотря на это, удалось найти элегантный алгоритм решения исходной задачи. Как это часто бывает, изменение одного из свойств алгоритма, в данном случае расширение области, где он корректен, привело к ухудшению его другой характеристики — времени выполнения.

Ссылки



© 2025 ООО «МТ ФИНАНС»

Telegram-канал со скидками, розыгрышами призов и новостями IT ?

Комментарии (70)


  1. kovserg
    03.06.2025 13:34
    #28389910

    А кто мешает использовать для суммы большую разрядность?

    uint32_t naive_average(const vector<uint32_t>& nums) {
    uint64_t sum = 0;
    for (const auto& x : nums) sum += x;
    return sum / nums.size();
}


    1. Daemonis
      03.06.2025 13:34
      #28389990

      А кто мешает использовать для суммы большую разрядность?

      Условие задачи?


      1. middle
        03.06.2025 13:34
        #28390690

        Тогда это задача ради задачи.


        1. CBET_TbMbI
          03.06.2025 13:34
          #28391868

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


          1. Kahelman
            03.06.2025 13:34
            #28392366

            Для этого рекомендую читать классиков. Дональд Кнут: Искусство программирования для ЭВМ. Том 2 . Получисленные алгоритмы .

            Как всегда Гугл засрали спамеры но ЧатГПТ все помнит:

            Ты, вероятно, имеешь в виду алгоритм Кнута для скользящего (инкрементального) среднего, также известный как online mean или running mean.
            Он позволяет не хранить все значения, а пересчитывать среднее на каждом шаге при поступлении нового элемента.

            Вот алгоритм:

            Пусть:
            • n — количество уже обработанных элементов (сначала n = 0)
            • \mu_n — текущее среднее после n элементов
            • x_{n+1} — новый поступающий элемент

            Обновление среднего:

            \mu_{n+1} = \mu_n + \frac{x_{n+1} - \mu_n}{n+1}

            n = 0
            mu = 0.0

            for x in stream_of_values:
            n += 1
            mu += (x - mu) / n

            print("Mean =", mu)


            1. kukovik
              03.06.2025 13:34
              #28393556

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


            1. wataru
              03.06.2025 13:34
              #28394308

              Вот что это за мода пошла лениться и просто перепечатывать выхлоп из нейросетей? Во-первых, они галлюционируют. Их вывод надо проверять и осозновать. Если вы его проверили и переварили, то уже можно своими словами одно предложнение скинуть.
              Во-вторых, если кому-то хочется вывод чатажпт почитать, они у него сами спросят.

              Далее, проблема автора - не онлайн или ограничения по памяти, а переполнение целочисленной переменной. Обратите внимание в перепечатоном вами бездумно ответе нейросетки ни слова о переполнении нет.

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


          1. dyadyaSerezha
            03.06.2025 13:34
            #28392910

            Сдаётся мне, что чтение этих фиглиардов с диска или инета будет занимать на порядки больше времени, чем само вычисление.


        1. Tuxman
          03.06.2025 13:34
          #28392068

          Меня такое на интервью спросили кстати.


        1. wataru
          03.06.2025 13:34
          #28394284

          Нет, если у вас в задаче уже куча uint64_t, например. Или процессор 32-битный (микроконтроллеры какие-нибудь). У вас просто тупо нет большей разрядности.


    1. Serge78rus
      03.06.2025 13:34
      #28390010

      В данном случае мешает условие

      Постановка задачи: реализовать функцию uint32_t average(uint32_t a, uint32_t b), не используя типов шире, чем uint32_t...

      В реальной жизни надо провести замеры времени исполнения и сравнить с полученными автором для его алгоритма. Естественно, сама задача актуальна для архитектуры, не имеющей аппаратной реализации операций с 64-битными числами.


      1. middle
        03.06.2025 13:34
        #28390694

        ... и не имеющей аппаратной реализации сложения с переносом?


        1. Serge78rus
          03.06.2025 13:34
          #28391012

          Там еще придется поделить число двойной длинны, правда только один раз.


      1. kovserg
        03.06.2025 13:34
        #28395180

        А какая разница есть апаратная реализация или нет. Использовать большую разрядность никто не запрещает. Даже если компилятор умеет auto, но вдруг почему-то не умеет uint64_t, то разве это может остановить?
        Ведь c++ универсальный язык и не запрещает реализовывать всё что хочется:

        ext::div
        namespace ext {
	typedef ptrdiff_t aint;
	template<aint n> void ld0(uint32_t (&r)[n]) { for(aint k=0;k<n;k++) r[k]=0; }
	template<aint n> void mov(uint32_t (&r)[n],uint32_t (&a)[n]) { for(aint k=0;k<n;k++) r[k]=a[k]; }
	template<aint n> void dec(uint32_t (&r)[n],uint32_t (&a)[n]) { char c=0; for(aint k=0;k<n;k++) { uint32_t p=r[k]-a[k]; if (c) c=--p>=r[k]; else c=p>r[k]; r[k]=p; } }
	template<aint n> void shl(uint32_t (&r)[n],aint s=1) {
		if (s<=0) { return; } aint m=s>>5; s&=31;
		if (m>0) { for(aint k=n-1;k>=m;--k) r[k]=r[k-m]; for(aint k=0;k<m;k++) r[k]=0; }
	 	if (s>0) { m++; for(aint k=n-1;k>=m;--k) r[k]=(r[k]<<s)|(r[k-1]>>(32-s)); r[0]<<=s; }
	}
	template<aint n> void shr(uint32_t (&r)[n]) { for(aint k=0;k<n-1;k++) r[k]=(r[k]>>1)|(r[k+1]<<31); r[n-1]>>=1; }
	template<aint n> void setbit(uint32_t (&r)[n],aint k) { if (k>=0 || k<n*32) { aint m=k>>5; k&=31; r[m]|=1<<k; } }
	template<aint n> int  cmp(uint32_t (&a)[n],uint32_t (&b)[n]) { for(aint k=n-1;k>=0;--k) if (a[k]!=b[k]) return a[k]<b[k] ? -1 : 1; return 0; }
	template<aint n> bool is0(uint32_t (&a)[n]) { for(aint k=0;k<n;k++) if (a[k]) return false; return true; }
	static inline int lzbc(uint32_t x) {
		if (x==0) return 32; //           0 1 2 3 4 5 6 7 8 9 A B C D E F
		int r=0; static const int t[16]={ 4,3,2,2,1,1,1,1,0,0,0,0,0,0,0,0 };
		if (x&0xFFFF0000) x>>=16; else r+=16;
		if (x&0xFF00) x>>=8; else r+=8;
		if (x&0xF0) x>>=4; else r+=4;
		return r+t[x];
	}
	template<aint n> aint lzbc(uint32_t (&a)[n]) { aint r=0; for(aint k=n-1;k>=0;--k) { int z=lzbc(a[k]); r+=z; if (z!=32) break; } return r; }
	template<aint n> int  div(uint32_t (&d)[n],uint32_t (&r)[n],uint32_t (&a)[n],uint32_t (&b)[n]) {
		ld0(d); mov(r,a); if (is0(b)) return 1;
		aint s=lzbc(b)-lzbc(a); if (s<0 || cmp(a,b)<0) return 0;
		uint32_t w[n]; mov(w,b); shl(w,s);
		while(s>=0) { if (cmp(r,w)>=0) { setbit(d,s); dec(r,w); } shr(w); s--; }
		return 0;
	}
} // namespace ext

        uint32_t naive_average_0(const vector<uint32_t>& nums) {
    uint64_t sum = 0;
    for (const auto& x : nums) sum += x;
    return sum / nums.size();
}

uint32_t naive_average_1(const vector<uint32_t>& nums) {
	uint32_t s[2]={0,0}, d[2], r[2], p;
	for(const auto& x : nums) { p=s[0]; s[0]+=x; s[1]+=s[0]<p; }
	uint32_t n[2]={ (uint32_t)nums.size(),(uint32_t)((nums.size()>>16)>>16) };
	ext::div(d,r,s,n); return d[0];
}

uint32_t naive_average_2(const vector<uint32_t>& nums,bool round=false) {
	uint32_t p,s[2]={0,0}, n=(uint32_t)nums.size();
	for (const auto& x : nums) { p=s[0]; s[0]+=x; s[1]+=s[0]<p; }
	if (s[1]) {
		uint32_t r1=s[1], r2=0; 
		for(int i=0;i<32;i++) { r1<<=1; r2<<=1; if (r1>=n) { r2++; r1-=n; } }
		p=s[0]; s[0]+=r1; if (s[0]<p) { r2++; s[0]-=n; }
		if (round) { p=s[0]; s[0]+=n/2; if (s[0]<p) { r2++; s[0]-=n; } }
		return r2+s[0]/n;
	}
	return n ? s[0]/n : 0;
}


        1. wataru
          03.06.2025 13:34
          #28395348

          Это называется длинная арифметика. И у автора фактически ровно это и реализовано. Только весьма частный случай: в системе основания с базой size и с оптимизацией, что мы знаем, что нам надо будет выдать обычное целочисленное значение цифр, кроме младшей и оно помещается в uint32_t - так что вместо старших цифр можно сразу хранить их значение в десятичной системе в одной переменной.


  1. koldyr
    03.06.2025 13:34
    #28390092

    Del


  1. tenzink
    03.06.2025 13:34
    #28390546

    Похоже, что не работает корректно для больших массивов, т.е. таких, у которых size не помещается в uint32


    1. StarPilgrim Автор
      03.06.2025 13:34
      #28390750

      так, такого и не заявлено


      1. tenzink
        03.06.2025 13:34
        #28390972

        А как же `и затем обобщить этот подход на произвольное количество аргументов` и тесты с std::vector?

        С другой стороны понятно, что это уже задача со звёздочкой


        1. StarPilgrim Автор
          03.06.2025 13:34
          #28390992

          тут я бы сам своё условие нарушил: раз сам размер не влезает в 32 бита, пришлось бы использовать uint64_t


          1. tenzink
            03.06.2025 13:34
            #28391044

            Можно попробовать придумать алгоритм, где не будет явно использоваться размер, а вектор обрабатывать чанками по 2**32. Range-based-for все 64bit-указатели прячет под капотом


  1. sci_nov
    03.06.2025 13:34
    #28391108

    Можно просто суммировать и накапливать количество переполнений.


    1. haqreu
      03.06.2025 13:34
      #28391420

      Два чая. В кои-то веки можно переполнять переменную без UB :)

      И по факту это является вариантом суммирования в переменную большей разрядности, не выходя за рамки задачи не использовать ничего, кроме uint32_t.


      1. sci_nov
        03.06.2025 13:34
        #28391486

        А что значит два чая?


        1. haqreu
          03.06.2025 13:34
          #28391494

          Плохая калька от «I second this», использование которой не выставляет меня в лучшем свете :)


          1. sci_nov
            03.06.2025 13:34
            #28391502

            Хм. Имеется ввиду "да .. вашу МАТЬ"? Понял)


            1. haqreu
              03.06.2025 13:34
              #28391514

              Хм. Нет, просто «поддерживаю».


          1. AlexSky
            03.06.2025 13:34
            #28393478

            Вот и выросло поколение...

            Это выражение поддержки, пришедшее с имиджборды 2ch (двач). Изначально звучало как "двачую", потом переродилось в "два чая [этому господину]".


            1. haqreu
              03.06.2025 13:34
              #28393672

              Ну да, а «двачую» это искажённое «дваждую», которое является дурацкой калькой с «I second». Я вырос чуть раньше 2ch :)


              1. sci_nov
                03.06.2025 13:34
                #28395748

                Брр. Ничего не понимаю... Надо гуглить).


                1. haqreu
                  03.06.2025 13:34
                  #28395752

                  Не надо, оно умерло уже пятнадцать лет как. Зачем вам стылый подростковый юмор? :)


                  1. sci_nov
                    03.06.2025 13:34
                    #28395758

                    И то верно.


                  1. sci_nov
                    03.06.2025 13:34
                    #28395788

                    В рот меня компотом )


    1. Damiryh
      03.06.2025 13:34
      #28391538

      Велосипедить сложение с переносом?


      1. sci_nov
        03.06.2025 13:34
        #28391548

        Нет. У ЦПУ есть флаг переноса.


        1. kipar
          03.06.2025 13:34
          #28392140

          а как к нему обратиться на C++? Ведь целевая плафторма может быть какой-нибудь wasm.


          1. sci_nov
            03.06.2025 13:34
            #28392200

            Да можно просто использовать сравнение суммы с наибольшим из слагаемых. Если сумма меньше, значит был перенос.


            1. kipar
              03.06.2025 13:34
              #28392202

              Это и есть "велосипедить сложение с переносом".


              1. sci_nov
                03.06.2025 13:34
                #28392254

                Да, но это лучше чем вычислять остаток от деления на новое число


          1. haqreu
            03.06.2025 13:34
            #28392680

            А что мешает сделать ассемблерную вставку при сильной необходимости?

            (Впрочем, оптимизатор скорее всего велосипед со сравнением превратит ровно в тот ассемблер, что был бы написан руками)


        1. punzik
          03.06.2025 13:34
          #28393218

          Не у всякого. Например, у MIPS и RISC-V нет флагов. Но можно, конечно, просто сравнить результат с операндами - если он меньше любого, то случилось переполнение.


          1. sci_nov
            03.06.2025 13:34
            #28397906

            Интересно. Даже физически нету?


            1. punzik
              03.06.2025 13:34
              #28398694

              Физически может быть, например, триггер между стадиями конвейера (а может и не быть). Но это исключительно внутренняя кухня.


  1. pnmv
    03.06.2025 13:34
    #28391582

    читая о целочисленных преобразованиях (назовем их так), невольно, думаешь о делении сдвигами на два, с накоплением результата.

    не удивлюсь, если я где-нибудь промахнулся, но, вот такое "поверхностное представление".


    1. StarPilgrim Автор
      03.06.2025 13:34
      #28402900

      я вот не совсем понял, что конкретно вы имеете в виду, но я писал о чём-то схожем до этого https://habr.com/ru/articles/833470/


  1. Tuxman
    03.06.2025 13:34
    #28392208

    Всё хорошо, но формул для вычисления средних очень много.
    Вот у тебя, Хабра читатель, есть машина? Она показывает среднюю скорость, средний расход? А как она это делает, никогда не задумывался?


    1. StarPilgrim Автор
      03.06.2025 13:34
      #28402904

      Очевидно, что речь идёт о среднем арифметическом, а не о среднем геометрическом или о среднем гармоническом


  1. nsmcan
    03.06.2025 13:34
    #28392234

    У меня нарисовался такой алгоритм. Пардон, что без форматирования. Прошу сильно не пенять.

    Считаем ближайшую степень двойки, большую количества элементов:

    2**k >= n

    m = 2**k. m всегда >= n

    (A1+A2+...+An)/n = (A1+A2+...+An) × 2**k / n × 2**k = (A1+A2+...+An+0+0+...+0m) / 2**k × 2**k / n

    Здесь мы добиваем нулям, чтобы общее количество элементов стало m.

    Выражение S = (A1+A2+...+An+0+0+...+0m) / 2**k обсчитывется рекурсивным разбиением на пары и сдвигом вправо на 1 бит. Придётся учитывать теряемый бит нечётных чисел.

    После чего имеем S × 2**k / n

    Это, по идее, можно просчитать без вылета за границы величин.

    Я алгоритм не тестировал. Так что если вкралась ошибка, то прошу не серчать


  1. Panzerschrek
    03.06.2025 13:34
    #28392360

    Деления и ветвления на каждой итерации предсказуемо медленны. Проще было бы реализовать сложение с учётом переполнение (с записью старших битов в отдельную переменную) с финальным делением с учётом этих битов. А можно даже этим не заниматься и использовать 64-битные переменные - компиляторы достаточно умны, чтобы выдать аналогичный код на системе без 64-битных инструкций.

    https://godbolt.org/z/zzbjqrv3T


    1. StarPilgrim Автор
      03.06.2025 13:34
      #28402910

      а вот представьте, что у вас уже 64-битные переменные в аргументах - какие числа вам использовать тогда?


  1. dx-77
    03.06.2025 13:34
    #28392980

    Небольшая поправка

    натуральных чисел a и b (b не равно нулю)

    Натуральные числа они по определению больше нуля


    1. Vytian
      03.06.2025 13:34
      #28393056

      По Бурбаки ноль тоже натуральный, потому что мощности множеств, а не индексы нумерации существующих объектов. По ISO

      \mathbb{N}

      с нулем. А вот \mathbb{N}^* без нуля.


      1. dx-77
        03.06.2025 13:34
        #28393244

        Ну да, а в России общепринято, что N это 1, 2, 3... Как говорится "у ней особенная стать"

        Группа Бурбаки в 20 веке решила ввести свою аксиоматику у которой есть как сторонники, так и противники. Но имхо, она идет в разрез с этимологией слова "натуральные" ну и самим способом их появления идущим ещё со времен до н.э. А так да, удобно в теории множеств считать число 0 натуральным. Как по мне французы заоверрайдили этот термин по-своему, но пора прекращать холиварный оффтоп)


        1. StjarnornasFred
          03.06.2025 13:34
          #28393466

          По определению, натуральные числа - это целые положительные числа. То есть это числа, которые строго больше нуля.


          1. haqreu
            03.06.2025 13:34
            #28393680

            Ха, определения очень сильно зависят от школы, в которой вы учились. Знаете ли вы, что для французов «nombre positif» означает «большее либо равное нулю»?


            1. StarPilgrim Автор
              03.06.2025 13:34
              #28402916

              офигенный холивар порадил нечайно я. Никогда не прикапывался к тому входит ноль или нет в натуральные числа - всегда следовал нотациям и аксиоматике источника.


  1. vk6677
    03.06.2025 13:34
    #28393144

    На счёт 2-х чисел. Видимо настолько частая была ошибка с переполнением, что в стандарт ввели std::midpoint.


    1. sci_nov
      03.06.2025 13:34
      #28395268

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


      1. vk6677
        03.06.2025 13:34
        #28395320

        Согласен. Классическая формула a + (b - a) /2. Оформленная в виде шаблона.


        1. Tuxman
          03.06.2025 13:34
          #28395352

          a + (b - a) /2 тоже переполняется, если b > a.
          Если вам по классике, тогда вот так auto avg = (a & b) + ((a ^ b) >> 1);


          1. vk6677
            03.06.2025 13:34
            #28395366

            В реализации GCC есть эта проверка на условие. Видимо что-бы работало с числами с плавающей запятой. Приведённое Вами решение только для целых чисел.

            И скорее переполнение будет если b < a.


          1. wataru
            03.06.2025 13:34
            #28395726

            Нет, не переполнится (в беззнаковых числах, как в статье). Ответ влезает, потому что это среднее. Разность влезает, потому что худший вариант - это MAX_UINT - 0 = MAX_UINT.

            Со знаковыми числами, да - может переполниться.


        1. sci_nov
          03.06.2025 13:34
          #28395754

          std::midpoint() не округляет вниз, она работает как round.


  1. KarmaCraft
    03.06.2025 13:34
    #28393502

    Хорошая статья, вскрывает вопрос понимания конкретной архитектуры!


  1. WASD1
    03.06.2025 13:34
    #28394134

    <pedant mode>
    Я понимаю "горячий" заголовок, но дистрибутивность - это закон согласования ДВУХ бинарных операций.
    </pedenat mode>


    1. StarPilgrim Автор
      03.06.2025 13:34
      #28394408

      Их две: сложение (это 1) и деление (это два). Правильно посчитал до двух ?


      1. WASD1
        03.06.2025 13:34
        #28394688

        Это случай, когда надо объяснять, что значат "тэги" <pedant mode>?

        Really?


        1. StarPilgrim Автор
          03.06.2025 13:34
          #28402924

          видимо, баг в реализации pedantic-mode у меня в созании:)


  1. wataru
    03.06.2025 13:34
    #28394258

    Тоже первая мысль была считать отдельно частные и остатки.

    Умный алгоритм работает так быстро из-за пайплайна в процессоре. Да, одно деление выполняется в 10 раз медленнее одного умножения. Но если у вас куча делений подряд, то они выполняются лишь немного медленнее кучи сложений, потому что куча микроопераций выполняется параллельно и самое медленное - чтение из памяти.


    1. StarPilgrim Автор
      03.06.2025 13:34
      #28402928

      о, отлично - и этот ответ в итоге. общими усилями, нашли. Спасибо!