Банальнейшее среднее арифметическое? Ан нет! Как вычислить без потери точности?

@Ukstuies · Регистрация: 01.02.2016

Author24 — интернет-сервис помощи студентам

Среднее арифметическое вычисляется просто:

(1+2+3+4)/4 =2.5

В коде это будет тоже просто:

C++

char array[4]={1,2,3,4};
 
char i=0;
float summ = 0;
float result = 0;
 
for(i=0;i<4;++i){
    summ += array[i];
}
 
result = summ/4;

Всё становится непросто, когда количество элементов в массиве переваливает за 2 млрд и значения уже далеко не char.

Основная проблема это число summ. Оно должно вмещать в себя сумму всех 2 млрд значений. Получается крайне большое число. Работать с ним без потери точности невозможно.

Появилась идея вычислять среднее в цикле по мере поступления новых элементов. Ведь result это всегда маленькое число:

C++

1
2
3

for(i=0;i<fizeof_very_big_array;++i){
    result = ... very_big_array[i] ...
}

Наверняка я не первый, кто задался таким вопросом. Подскажите, пожалуйста, как это правильно сделать с точки зрения математики. Моих знаний предмета недостаточно для самостоятельной реализации.

Заранее спасибо.

@MLPMan · 06.06.2016, 23:47

Можно вынести за скобки и удолить n (посмотрел, 2млрд даже помещаются в 4 байта), но это будут потеря точности, да? Тогда, думаю, остаётся только сделать/взять модуль для работы с большими цифрами.

@Ukstuies · 07.06.2016, 09:20 **[ТС]**

MLPMan, спасибо за интерес к теме, но, к сожалению, я ничего не понял из Вашего ответа. Можно другими словами?

Сообщение от MLPMan

2млрд даже помещаются в 4 байта

Сумма всех двух млрд. элементов массива double поместится в 4 байта?! Даже для unsigned char уже не поместится.

@Sindbad_M · 07.06.2016, 10:04

Ukstuies, можно так https://ru.wikipedia.org/wiki/... 0.B5.D0.B5
Или сделать для себя переменные необходимой точности https://ru.wikipedia.org/wiki/... 0%BA%D0%B0 (но очень сильно может упасть скорость вычислений!)

@Ukstuies · 07.06.2016, 11:45 **[ТС]**

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

@wingblack · 07.06.2016, 12:29

Можно разбить массив на равные участки в которых не будет существенной потери точности, считать среднее на каждом из них, потом найти среднее из найденных средних.

@Ukstuies · 07.06.2016, 13:13 **[ТС]**

wingblack, разумно, эффективно, но много рекурсивных операций. Интересно было бы использовать математические методы и сократить вычисления. Неужели такой велосипед ещё не изобрели до нас?

echs · 07.06.2016, 14:42

Ukstuies
Есть два основных способа
1. Поскольку потеря точности идет за счет того, что
суммируются числа разных размеров, то по возможности
числа предварительно сортируются.
В идеале к меньшему числу прибавляется большее и тд.
То есть суммирование начинается с меньших чисел.
2. Если подобное невозможно, то что вам мешает пересчитывать
среднее арифметическое при каждом новом числе.
Количество чисел естественно при этом запоминается.
Пусть
S_n - среднее арифметическое n чисел
S_n+1 - среднее арифметическое n +1 чисел
A_n+1 - новое число
Тогда
$https://www.cyberforum.ru/cgi-bin/latex.cgi?S_{n+1}=S_{n}*\frac {n}{n+1}+\frac {A_{n+1}}{n+1}$
Вас устраивает такой пересчет?

@Ukstuies · 07.06.2016, 16:53 **[ТС]**

Сообщение от geh

Вас устраивает такой пересчет?

ЗдОрово! Кажется, то, что нужно. Сейчас попробую это превратить в код.

Добавлено через 42 минуты
geh, в формуле что-то не так. Я проверил подстановкой чисел. Не получается:

Пусть даны числа:
{1,2,3,4}

Среднее первого числа = 1.

Подставим в формулу значения для полученного среднего и второе число. В результате получаем 2.5.

В действительности, среднее первых двух чисел должно получиться (1+2)/2=1.5

echs · 07.06.2016, 17:11

Ukstuies
Вы неправильно используете формулу.
Вот ваш пример.
(1+2+3)/3=2
(1+2+3+4)/4=2,5
Теперь проверяйте
2*(3/4)+4/4=2,5 (!!) Что не так?

@Ukstuies · 07.06.2016, 20:25 **[ТС]**

geh, мой глючный код меня запутал. Благодарю за разъяснение и огромное спасибо за формулу. Всё получилось!

Вот отлично работающий результат в виде кода c++. Ищет среднее арифметическое без суммирования всех элементов массива. Экономично по памяти, без потери точности и с максимально возможной производительностью:

C++

#include <iostream>
#include <iomanip>
 
using namespace std;
 
int main(void){
 
    double array[]={1,2,3,4,258,3521,8,16,15,1,0.1};
 
    size_t i = 0;
    size_t array_size = sizeof(array)/sizeof(double);
 
    double a = 0;
    double b = 0;
    double c = 0;
    double mid = 0;
 
    cout << fixed << setprecision(2);
 
    for(i=0;i < array_size;i++){
        a = i;
        b = i+1;
        c = array[i];
        mid = (mid * (a/b)) + (c/b);
        cout << mid << endl;
    }
}

@Shamil1 · 07.06.2016, 20:46

Если числа int32, то для суммы 2 млрд хватит int64. Ответ без потери точности.
Если числа double, то сначала сортируем, а потом складываем. Потери точности невелики. Чтобы потери точности были ещё меньше, нужно использовать очередь с приоритетом. Брать из очереди два минимальных числа, сумму добавлять в очередь.

@Ukstuies · 07.06.2016, 21:23 **[ТС]**

Сообщение от Shamil1

Потери точности невелики

Ответ достойный разработчика платёжной системы на вопрос клиента: "Хде бабло?"

Шучу.

Сообщение от Shamil1

нужно использовать очередь с приоритетом

Поясните, пожалуйста, примером, если несложно. С кодом понять гораздо проще.

@Shamil1 · 07.06.2016, 21:37

В платёжной системе нельзя использовать double (для хранения денег)

Добавлено через 3 минуты

Код

x = numbers.remove_min()
y = numbers.remove_min()
numbers.add(x + y)

@Ukstuies · 08.06.2016, 11:19 **[ТС]**

Сообщение от Shamil1

Нельзя просто так взять и использовать в платёжной системе double

Из альтернатив крайне непопулярная Intel Decimal Floating-Point Math Library или тормознутая (в силу архитектурных особенностей) libgmp.

Если есть что-нибудь достойное (быстрое и без потерь), то поделитесь, пожалуйста, информацией.

Банальнейшее среднее арифметическое? Ан нет! Как вычислить без потери точности?

@Shamil1 · 08.06.2016, 15:20

можно самому написать за полчаса для decimal(20,4)

@ShkrylAndrei · 09.06.2016, 11:43

Среднее арифметическое вычисляется просто:

(1+2+3+4)/4 =2.5

Выделяешь память для временных результатов, производишь сначала операцию сложения, например отдельными
блоками для 1000 элементов, можно даже распаралелить вычисления, потому объединяешь отдельные блоки в единую сумму, и производишь операцию деления, можно спуститься в самый низ, и использовать для арифметических операций Ассемблер,время при большом объеме сократиться,но нужно смотреть,что ты используешь компилятор или интерпритатор.

Добавлено через 3 минуты
Я нашел два поста тебе в помощь:
https://www.cyberforum.ru/asse... 65034.html
https://www.cyberforum.ru/asse... 98459.html
По экономии времени не могу сказать, но по логике, когда ты работаешь напрямую с процессором, то количество операций
сокращается, и экономия времени возрастает.

@Thor · 16.07.2016, 17:41

Самый простой и быстрый путь - создать массив, записывать в него среднее по каждой, например, 1000 значений. Затем посчитать среднее значение уже по этому массиву. При этом для последнего элемента массива учитываешь, что его вес равен не 1, а числу элементов, по которому оно получено, делённому на 1000.

@Thor 2 / 2 / 0 Регистрация: 12.12.2014 Сообщений: 87
	16.07.2016, 17:41	18
	Самый простой и быстрый путь - создать массив, записывать в него среднее по каждой, например, 1000 значений. Затем посчитать среднее значение уже по этому массиву. При этом для последнего элемента массива учитываешь, что его вес равен не 1, а числу элементов, по которому оно получено, делённому на 1000. 0

@MLPMan Кандёхаем веселее! 296 / 330 / 76 Регистрация: 02.10.2012 Сообщений: 2,175
	06.06.2016, 23:47	2
	Можно вынести за скобки и удолить n (посмотрел, 2млрд даже помещаются в 4 байта), но это будут потеря точности, да? Тогда, думаю, остаётся только сделать/взять модуль для работы с большими цифрами. 0

@Ukstuies 0 / 0 / 0 Регистрация: 01.02.2016 Сообщений: 19
	07.06.2016, 09:20 [ТС]	3
	MLPMan, спасибо за интерес к теме, но, к сожалению, я ничего не понял из Вашего ответа. Можно другими словами? Сообщение от MLPMan 2млрд даже помещаются в 4 байта Сумма всех двух млрд. элементов массива double поместится в 4 байта?! Даже для unsigned char уже не поместится. 0

@Sindbad_M 466 / 393 / 122 Регистрация: 23.05.2016 Сообщений: 1,574
	07.06.2016, 10:04	4
	Ukstuies, можно так https://ru.wikipedia.org/wiki/... 0.B5.D0.B5 Или сделать для себя переменные необходимой точности https://ru.wikipedia.org/wiki/... 0%BA%D0%B0 (но очень сильно может упасть скорость вычислений!) 1

@Ukstuies 0 / 0 / 0 Регистрация: 01.02.2016 Сообщений: 19
	07.06.2016, 11:45 [ТС]	5
	Sindbad_M, спасибо за интересные ссылки на теорию. По материалам можно сделать вывод, что скользящее среднее базируется на заранее заданных интервалах и не совсем применимо в рамках моей задачи. Хотя да, проще вычислить среднее на интервале, чем на всём диапазоне исходных данных. Но эти результаты сформируют новый массив из средних, с которыми тоже нужно что-то делать... 0

@wingblack 294 / 265 / 48 Регистрация: 09.04.2013 Сообщений: 1,037
	07.06.2016, 12:29	6
	Можно разбить массив на равные участки в которых не будет существенной потери точности, считать среднее на каждом из них, потом найти среднее из найденных средних. 1

@Ukstuies 0 / 0 / 0 Регистрация: 01.02.2016 Сообщений: 19
	07.06.2016, 13:13 [ТС]	7
	wingblack, разумно, эффективно, но много рекурсивных операций. Интересно было бы использовать математические методы и сократить вычисления. Неужели такой велосипед ещё не изобрели до нас? 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	07.06.2016, 14:42	8
	Сообщение было отмечено Ukstuies как решение Решение Ukstuies Есть два основных способа 1. Поскольку потеря точности идет за счет того, что суммируются числа разных размеров, то по возможности числа предварительно сортируются. В идеале к меньшему числу прибавляется большее и тд. То есть суммирование начинается с меньших чисел. 2. Если подобное невозможно, то что вам мешает пересчитывать среднее арифметическое при каждом новом числе. Количество чисел естественно при этом запоминается. Пусть S_n - среднее арифметическое n чисел S_n+1 - среднее арифметическое n +1 чисел A_n+1 - новое число Тогда $https://www.cyberforum.ru/cgi-bin/latex.cgi?S_{n+1}=S_{n}*\frac {n}{n+1}+\frac {A_{n+1}}{n+1}$ Вас устраивает такой пересчет? 2

@Ukstuies 0 / 0 / 0 Регистрация: 01.02.2016 Сообщений: 19
	07.06.2016, 16:53 [ТС]	9
	Сообщение от geh Вас устраивает такой пересчет? ЗдОрово! Кажется, то, что нужно. Сейчас попробую это превратить в код. Добавлено через 42 минуты geh, в формуле что-то не так. Я проверил подстановкой чисел. Не получается: Пусть даны числа: {1,2,3,4} Среднее первого числа = 1. Подставим в формулу значения для полученного среднего и второе число. В результате получаем 2.5. В действительности, среднее первых двух чисел должно получиться (1+2)/2=1.5 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	07.06.2016, 17:11	10
	Ukstuies Вы неправильно используете формулу. Вот ваш пример. (1+2+3)/3=2 (1+2+3+4)/4=2,5 Теперь проверяйте 2*(3/4)+4/4=2,5 (!!) Что не так? 1

@Shamil1 Модератор 3077 / 2226 / 462 Регистрация: 26.03.2015 Сообщений: 8,627
	07.06.2016, 20:46	12
	Если числа int32, то для суммы 2 млрд хватит int64. Ответ без потери точности. Если числа double, то сначала сортируем, а потом складываем. Потери точности невелики. Чтобы потери точности были ещё меньше, нужно использовать очередь с приоритетом. Брать из очереди два минимальных числа, сумму добавлять в очередь. 1

@Ukstuies 0 / 0 / 0 Регистрация: 01.02.2016 Сообщений: 19
	07.06.2016, 21:23 [ТС]	13
	Сообщение от Shamil1 Потери точности невелики Ответ достойный разработчика платёжной системы на вопрос клиента: "Хде бабло?" Шучу. Сообщение от Shamil1 нужно использовать очередь с приоритетом Поясните, пожалуйста, примером, если несложно. С кодом понять гораздо проще. 0

@Shamil1 Модератор 3077 / 2226 / 462 Регистрация: 26.03.2015 Сообщений: 8,627
	07.06.2016, 21:37	14
	В платёжной системе нельзя использовать double (для хранения денег) Добавлено через 3 минуты Код x = numbers.remove_min() y = numbers.remove_min() numbers.add(x + y) 0

@Ukstuies 0 / 0 / 0 Регистрация: 01.02.2016 Сообщений: 19
	08.06.2016, 11:19 [ТС]	15
	Сообщение от Shamil1 Нельзя просто так взять и использовать в платёжной системе double Из альтернатив крайне непопулярная Intel Decimal Floating-Point Math Library или тормознутая (в силу архитектурных особенностей) libgmp. Если есть что-нибудь достойное (быстрое и без потерь), то поделитесь, пожалуйста, информацией. 0

@Shamil1 Модератор 3077 / 2226 / 462 Регистрация: 26.03.2015 Сообщений: 8,627
	08.06.2016, 15:20	16
	можно самому написать за полчаса для decimal(20,4) 0

@ShkrylAndrei 14 / 14 / 1 Регистрация: 26.01.2015 Сообщений: 77
	09.06.2016, 11:43	17
	Среднее арифметическое вычисляется просто: (1+2+3+4)/4 =2.5 Выделяешь память для временных результатов, производишь сначала операцию сложения, например отдельными блоками для 1000 элементов, можно даже распаралелить вычисления, потому объединяешь отдельные блоки в единую сумму, и производишь операцию деления, можно спуститься в самый низ, и использовать для арифметических операций Ассемблер,время при большом объеме сократиться,но нужно смотреть,что ты используешь компилятор или интерпритатор. Добавлено через 3 минуты Я нашел два поста тебе в помощь: https://www.cyberforum.ru/asse... 65034.html https://www.cyberforum.ru/asse... 98459.html По экономии времени не могу сказать, но по логике, когда ты работаешь напрямую с процессором, то количество операций сокращается, и экономия времени возрастает. 0

Банальнейшее среднее арифметическое? Ан нет! Как вычислить без потери точности?

Решение