Comments 84
А кто мешает использовать для суммы большую разрядность?
uint32_t naive_average(const vector<uint32_t>& nums) {
uint64_t sum = 0;
for (const auto& x : nums) sum += x;
return sum / nums.size();
}
А кто мешает использовать для суммы большую разрядность?
Условие задачи?
Тогда это задача ради задачи.
Возможно, это приобретает практический смысл, когда нужно посчитать среднее из фиглиардов чисел.
Для этого рекомендую читать классиков. Дональд Кнут: Искусство программирования для ЭВМ. Том 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)
Тут очевидно, что быстрее не будет. Ибо на каждый чих то самое деление, которое и у автора статьи. Плюс надо как-то решать проблему с потерями от округления.
Вот что это за мода пошла лениться и просто перепечатывать выхлоп из нейросетей? Во-первых, они галлюционируют. Их вывод надо проверять и осозновать. Если вы его проверили и переварили, то уже можно своими словами одно предложнение скинуть.
Во-вторых, если кому-то хочется вывод чатажпт почитать, они у него сами спросят.
Далее, проблема автора - не онлайн или ограничения по памяти, а переполнение целочисленной переменной. Обратите внимание в перепечатоном вами бездумно ответе нейросетки ни слова о переполнении нет.
Вам тут очень повезло, и в этом алгоритме действительно нет переполнения.
Здесь нет переполнения не потому что мне повезло, а потому что у Кнута правильный алгоритм описан. Я бы вам скинул ссылку на страницу или ее фото, но у чата гпт проще спросить
Кстати, на второй взгляд, переполнение тут есть. Например, если ему дать числа {4294967295, 0}, то оно вообще никак не подсчитает 2147483647. Плюс, тут округление может быть как вверх, так и вниз при вычислении среднего в зависимости от порядка переданных чисел, что тоже не всегда хорошо и совсем не удовлетворяет поставленным автором условиям.
Сдаётся мне, что чтение этих фиглиардов с диска или инета будет занимать на порядки больше времени, чем само вычисление.
Меня такое на интервью спросили кстати.
Нет, если у вас в задаче уже куча uint64_t, например. Или процессор 32-битный (микроконтроллеры какие-нибудь). У вас просто тупо нет большей разрядности.
В данном случае мешает условие
Постановка задачи: реализовать функцию uint32_t average(uint32_t a, uint32_t b), не используя типов шире, чем uint32_t...
В реальной жизни надо провести замеры времени исполнения и сравнить с полученными автором для его алгоритма. Естественно, сама задача актуальна для архитектуры, не имеющей аппаратной реализации операций с 64-битными числами.
... и не имеющей аппаратной реализации сложения с переносом?
А какая разница есть апаратная реализация или нет. Использовать большую разрядность никто не запрещает. Даже если компилятор умеет 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;
}
Это называется длинная арифметика. И у автора фактически ровно это и реализовано. Только весьма частный случай: в системе основания с базой size и с оптимизацией, что мы знаем, что нам надо будет выдать обычное целочисленное значение цифр, кроме младшей и оно помещается в uint32_t - так что вместо старших цифр можно сразу хранить их значение в десятичной системе в одной переменной.
Del
Похоже, что не работает корректно для больших массивов, т.е. таких, у которых size не помещается в uint32
Можно просто суммировать и накапливать количество переполнений.
Два чая. В кои-то веки можно переполнять переменную без UB :)
И по факту это является вариантом суммирования в переменную большей разрядности, не выходя за рамки задачи не использовать ничего, кроме uint32_t.
А что значит два чая?
Плохая калька от «I second this», использование которой не выставляет меня в лучшем свете :)
Хм. Имеется ввиду "да .. вашу МАТЬ"? Понял)
Вот и выросло поколение...
Это выражение поддержки, пришедшее с имиджборды 2ch (двач). Изначально звучало как "двачую", потом переродилось в "два чая [этому господину]".
Ну да, а «двачую» это искажённое «дваждую», которое является дурацкой калькой с «I second». Я вырос чуть раньше 2ch :)
Не все подряд сидели на дваче. (мне, например, не до этого было, поэтому про "двачую"->"два чая [этому господину]" прочел только здесь, хотя, чисто интуитивно, и распознавал эти два выражения в одобрительном ключе)
Автор использует unsigned, переполнение которых не вызывает UB.
Велосипедить сложение с переносом?
Нет. У ЦПУ есть флаг переноса.
а как к нему обратиться на C++? Ведь целевая плафторма может быть какой-нибудь wasm.
Не у всякого. Например, у MIPS и RISC-V нет флагов. Но можно, конечно, просто сравнить результат с операндами - если он меньше любого, то случилось переполнение.
читая о целочисленных преобразованиях (назовем их так), невольно, думаешь о делении сдвигами на два, с накоплением результата.
не удивлюсь, если я где-нибудь промахнулся, но, вот такое "поверхностное представление".
я вот не совсем понял, что конкретно вы имеете в виду, но я писал о чём-то схожем до этого https://habr.com/ru/articles/833470/
Всё хорошо, но формул для вычисления средних очень много.
Вот у тебя, Хабра читатель, есть машина? Она показывает среднюю скорость, средний расход? А как она это делает, никогда не задумывался?
У меня нарисовался такой алгоритм. Пардон, что без форматирования. Прошу сильно не пенять.
Считаем ближайшую степень двойки, большую количества элементов:
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
Это, по идее, можно просчитать без вылета за границы величин.
Я алгоритм не тестировал. Так что если вкралась ошибка, то прошу не серчать
Деления и ветвления на каждой итерации предсказуемо медленны. Проще было бы реализовать сложение с учётом переполнение (с записью старших битов в отдельную переменную) с финальным делением с учётом этих битов. А можно даже этим не заниматься и использовать 64-битные переменные - компиляторы достаточно умны, чтобы выдать аналогичный код на системе без 64-битных инструкций.
https://godbolt.org/z/zzbjqrv3T
а вот представьте, что у вас уже 64-битные переменные в аргументах - какие числа вам использовать тогда?
128-битные же. Некоторые компиляторы их поддерживают.
А там, где их нету, можно руками складывать пары 64-битных чисел и отдельно учитывать и накапливать перенос.
Небольшая поправка
натуральных чисел a и b (b не равно нулю)
Натуральные числа они по определению больше нуля
По Бурбаки ноль тоже натуральный, потому что мощности множеств, а не индексы нумерации существующих объектов. По ISO
с нулем. А вот \mathbb{N}^* без нуля.
Ну да, а в России общепринято, что N это 1, 2, 3... Как говорится "у ней особенная стать"
Группа Бурбаки в 20 веке решила ввести свою аксиоматику у которой есть как сторонники, так и противники. Но имхо, она идет в разрез с этимологией слова "натуральные" ну и самим способом их появления идущим ещё со времен до н.э. А так да, удобно в теории множеств считать число 0 натуральным. Как по мне французы заоверрайдили этот термин по-своему, но пора прекращать холиварный оффтоп)
По определению, натуральные числа - это целые положительные числа. То есть это числа, которые строго больше нуля.
Ха, определения очень сильно зависят от школы, в которой вы учились. Знаете ли вы, что для французов «nombre positif» означает «большее либо равное нулю»?
На счёт 2-х чисел. Видимо настолько частая была ошибка с переполнением, что в стандарт ввели std::midpoint.
Эта функция несколько отличается от той, если бы мы усредняли, используя более широкие регистры.
Согласен. Классическая формула a + (b - a) /2. Оформленная в виде шаблона.
a + (b - a) /2 тоже переполняется, если b > a.
Если вам по классике, тогда вот так auto avg = (a & b) + ((a ^ b) >> 1);
В реализации GCC есть эта проверка на условие. Видимо что-бы работало с числами с плавающей запятой. Приведённое Вами решение только для целых чисел.
И скорее переполнение будет если b < a.
Нет, не переполнится (в беззнаковых числах, как в статье). Ответ влезает, потому что это среднее. Разность влезает, потому что худший вариант - это MAX_UINT - 0 = MAX_UINT.
Со знаковыми числами, да - может переполниться.
std::midpoint() не округляет вниз, она работает как round.
Хорошая статья, вскрывает вопрос понимания конкретной архитектуры!
<pedant mode>
Я понимаю "горячий" заголовок, но дистрибутивность - это закон согласования ДВУХ бинарных операций.
</pedenat mode>
Тоже первая мысль была считать отдельно частные и остатки.
Умный алгоритм работает так быстро из-за пайплайна в процессоре. Да, одно деление выполняется в 10 раз медленнее одного умножения. Но если у вас куча делений подряд, то они выполняются лишь немного медленнее кучи сложений, потому что куча микроопераций выполняется параллельно и самое медленное - чтение из памяти.
Обозначу количество за N.
Если N = 0 или 1, тут всё тривиально.
Если N < H, сейчас найдём этот порог, то sum(xi / N) + sum(xi % N) / N работает.
Если больше - то происходит переполнение.
Найдём худший случай: sum(xi % N) < sum(N-1) = (N-1)*N.
То есть, При N = 2**16 мы ещё не получим тут переполнения, а при 2**16 + 1 уже получим.
Отсюда мораль: нужно делать две ветви алгоритма: быстрый, который только компенсирует underflow, и более медленный, который компенсирует overflow в компенсаторе.
Причём медленный работает на больших наборах данных, и значит, надо там как-то поиграться, чтобы делать эту компенсацию не на каждый такт.
Например, можем избавиться от проверки в пользу цикла. (Как, собственно, это сделали с underflow). Решим уравнение (N-1)*P < 2**32. И нарежем весь набор остатков на блоки по P штук. Причём для удобства (и для распараллеливания) можем выбирать P как степень 2. Последний блок будет неполным, конечно.
N <= 2**16 -- P = 2**16
N <= 2**17 -- P = 2**15
...
N <= 2**31 -- P = 2
N <= 2**32 -- P = 1
Что, кстати, как бы намекает нам, что в последних случаях алгоритм выродится - у нас будет сплошное underflow и сплошные компенсации.
Недистрибутивность деления, или Как я считал среднюю величину