избавиться от деления в вычислительном алгоритме
> Может кто-нибуть знает как преобразовать алгоритм?
Да, знает.
Возьми, изучи алгоритм целочисленного деления и разверни его.
---
...Я работаю антинаучным аферистом...
Да, знает.
Возьми, изучи алгоритм целочисленного деления и разверни его.
---
...Я работаю антинаучным аферистом...
такое решение не приемлимо, я думал это понятно.
на самом деле, скорее всего, нужем метод того как произвольную сумму чисел (Bi) преобразовать к фиксированной сумме (например к 256) сделав это целочисленно и без делений, либо получить примерно тот же эффект алгоритма каким-то другим способом.
на самом деле, скорее всего, нужем метод того как произвольную сумму чисел (Bi) преобразовать к фиксированной сумме (например к 256) сделав это целочисленно и без делений, либо получить примерно тот же эффект алгоритма каким-то другим способом.
Я думал, что ты делитель постоянен.
В конце концов, это очевидное условие.
---
...Я работаю антинаучным аферистом...
В конце концов, это очевидное условие.
---
...Я работаю антинаучным аферистом...
скорее всего, нужем метод того как произвольную сумму чисел (Bi) преобразовать к фиксированной сумме (например к 256) сделав это целочисленно и без деленийкак ты представляешь деление, например, на 11, быстрее умножения на заранее посчитанное число 1/11?
насколько хорошей должна быть точность?
насколько хорошей должна быть точность?Алгоритм целочисленный, значит, и деление у нас целочисленное
Раза в два-три на 16 разрядах.
Раз в 8-10 на 32-х.
---
...Я работаю антинаучным аферистом...
Раз в 8-10 на 32-х.
---
...Я работаю антинаучным аферистом...
Числитель - целое число от 0 до 255*10*25, т.е. от 0 до 63750 (<2^16)
Знаменатель - от 0 до 250 (< 2^8)
Результат - от 0 до 255
Число возможных пар <2^24, на каждый достаточно 1 байта.
Т.е. 16 Мб, если хранить таблицу значений "в тупую". Если подумать, то таблицу можно хранить сильно компактнее.
У тебя какие ограничения по памяти?
Знаменатель - от 0 до 250 (< 2^8)
Результат - от 0 до 255
Число возможных пар <2^24, на каждый достаточно 1 байта.
Т.е. 16 Мб, если хранить таблицу значений "в тупую". Если подумать, то таблицу можно хранить сильно компактнее.
У тебя какие ограничения по памяти?
чем меньше используется памяти тем лучше,
вообще, разумный размер таблицы - 256-512 байт
на самом деле, точность того ,что будет в результате не сильно важна, можно в некоторых пределах менять веса Bi, сильно желательно чтобы результат был боле-менее близок к тому, что получается с использованием деления + должно быть выполнено требование: результат >= Min(Ai <= Max(Ai т.е. если, например, все числа одинаковые, то и результат не должен от них отличаться
вообще, разумный размер таблицы - 256-512 байт
на самом деле, точность того ,что будет в результате не сильно важна, можно в некоторых пределах менять веса Bi, сильно желательно чтобы результат был боле-менее близок к тому, что получается с использованием деления + должно быть выполнено требование: результат >= Min(Ai <= Max(Ai т.е. если, например, все числа одинаковые, то и результат не должен от них отличаться
Средневзвешенное можно вычислять по инкрементной схеме.
Надо подумать, что будет в таком случае.
Мне сейчас не до этого, будет возможность --- думай сам.
---
"...Надо учиться --- не напрягаясь!.." Акад. А. А. Бучаченко.
Надо подумать, что будет в таком случае.
Мне сейчас не до этого, будет возможность --- думай сам.
---
"...Надо учиться --- не напрягаясь!.." Акад. А. А. Бучаченко.
Хорошо, тогда так: считаем числитель, считаем знаменатель. Т.к. результат лежит в пределах 0..255 и, взяв наугад число, можно сказать с какой стороны от результата мы находимся, за 8 умножений и сравнений мы найдем искомое среднее.
Такой вариант не устраивает по скорости?
Такой вариант не устраивает по скорости?
Одно деление не стоит 8 умножений.
---
...Я работаю антинаучным аферистом...
---
...Я работаю антинаучным аферистом...
Мб у человека на процессоре вообще нет деления. Тогда стоит.
Тем более, вычисление среднего замедляется при этом всего процентов на 20-30 (остальное время будет занимать суммирование и умножение на веса)
Тем более, вычисление среднего замедляется при этом всего процентов на 20-30 (остальное время будет занимать суммирование и умножение на веса)
И при этом есть умножение?
Бывает, конечно, но тогда надо смотреть скорости.
Если делитель непостоянен, то навряд ли что-либо спасёт.
Достигнешь успехов, сообщи.
---
...Я работаю антинаучным аферистом...
Бывает, конечно, но тогда надо смотреть скорости.
Если делитель непостоянен, то навряд ли что-либо спасёт.
Достигнешь успехов, сообщи.
---
...Я работаю антинаучным аферистом...
> Одно деление не стоит 8 умножений.
В данном случае - можно заменить на сдвиги и сложения, очевидно, поэтому уже проще. Скорее всего действительно, обсуждаются какие-то процессоры из тех, что на смарткартах и тому подобном стоят, поэтому там никаких конвееров и т.п. нет, и оптимизация там - иная, чем в современных x86. А деления действительно может не быть.
В данном случае - можно заменить на сдвиги и сложения, очевидно, поэтому уже проще. Скорее всего действительно, обсуждаются какие-то процессоры из тех, что на смарткартах и тому подобном стоят, поэтому там никаких конвееров и т.п. нет, и оптимизация там - иная, чем в современных x86. А деления действительно может не быть.
деления скорее всего нет, и скорее всего для деления будет вызываться какая-то библиотечная функция, которая реализована хорошо, т.е. как я уже писал выше, задача скорее не в том как реализовать непосредственно само деление (через умножения или через собственную реализацию целочисленного деления а в том, чтобы скорректировать исходный алгоритм нахождения взвешенной суммы таким образом чтобы деление вообще исчезло. На самом деле умножение это тоже довольно дорогая операция, по возможности ее тоже нужно выкинуть, только я пока не могу придумать как
Если разрядность чисел известна, можно попытаться ускорить умножение.
---
...Я работаю антинаучным аферистом...
---
...Я работаю антинаучным аферистом...
Тебе нужно нормировать сумму, или просто взять хеш какой-нибудь от неё? Если первое - то врят ли можно что-то более умное придумать, тем более, что не так уж это и накладно.
Умножение здесь - не нужно. Здесь используется умножение на степени двойки, что есть ни что иное, как сдвиг, и поэтому работать будет достаточно быстро.
оптимизация под какой-то DSP, какой хз, но у них у всех требования примерно одинаковые - делений вообще нет (библиотечные функции использовать их крайне не рекомендуется, умножение - довольно дорого, ветвление - плохо, циклы не определенной длинны невозможны (имеется в виду что нет разумного ограничения сверху память нужно сильно экономить, к данным обращаться локально ну и т.п.
> ветвление - плохо
Я знаю, как можно сделать без ветвления,
но надо знать процессор, от него сильно зависит.
---
...Я работаю антинаучным аферистом...
Я знаю, как можно сделать без ветвления,
но надо знать процессор, от него сильно зависит.
---
...Я работаю антинаучным аферистом...
Откажемся от совсем точного результата и будем делать так:
S = сумма Bn
Av = (B1*A1 + ... + Bn*An)/S = B1*256/S) * A1 + (B2*256/S)*A2 + ... (Bn*256/S)*An)/256,
что приблизительно равно
Av = (round(B1 * 256 / S)*A1 + round(B2*256/S) * A2 + ... round(Bn*256/S)*An) >> 8;
round(Bi*256/S) - вычислять будем c помощью таблицы на 10*250 16-битных элементов (чуть больше 4kb.)
Если все-таки хочется сэкономить память, придется еще пожертвовать точностью. Сделать можно это попробовать примерно так: если у нас S в [9, 16] брать точное значения. Для S из отрезка [17-32] брать значение S+1)>>1)<<1, для S в [33-64] брать значение S+3)>>2)<<2 и т.д. Тогда надо 10*8*5*2 = 800 байт.
Если взять другую схему обрезания S такого типа, можно уместиться и в 512 байт
S = сумма Bn
Av = (B1*A1 + ... + Bn*An)/S = B1*256/S) * A1 + (B2*256/S)*A2 + ... (Bn*256/S)*An)/256,
что приблизительно равно
Av = (round(B1 * 256 / S)*A1 + round(B2*256/S) * A2 + ... round(Bn*256/S)*An) >> 8;
round(Bi*256/S) - вычислять будем c помощью таблицы на 10*250 16-битных элементов (чуть больше 4kb.)
Если все-таки хочется сэкономить память, придется еще пожертвовать точностью. Сделать можно это попробовать примерно так: если у нас S в [9, 16] брать точное значения. Для S из отрезка [17-32] брать значение S+1)>>1)<<1, для S в [33-64] брать значение S+3)>>2)<<2 и т.д. Тогда надо 10*8*5*2 = 800 байт.
Если взять другую схему обрезания S такого типа, можно уместиться и в 512 байт
Плохой способ.
Возможна недопустимая потеря точности.
Лучше поточнее выяснить пределы изменения суммы B.
---
...Я работаю антинаучным аферистом...
Возможна недопустимая потеря точности.
Лучше поточнее выяснить пределы изменения суммы B.
---
...Я работаю антинаучным аферистом...
В первой части алгоритма максимальная ошибка может составить 1 (причем, это можно скорректировать, если все-таки один раз умножить).
Можно, кстати, не мудрить и все-таки заменить деление одним умножением. Для этого 1/S представить в виде дроби k/65536 (табличка на 250 элементов по два байта). Затем умножим числитель на знаменатель (правда, либо придется умножать 2-байтовые целые с получением 4-байтового результата, либо делать такое умножение самостоятельно). После этого сдвинуть на 16 бит вправо и получим результат с точностью до 1.
Оставить комментарий
pulmo
суть алгоритма следующая:для конечного числа величин An (A1, ..., A9 например) вычисляется некоторый вес Bn (B1, ... , B9 после чего находится среднее:
(сумма Ai * Bi) / (сумма Bi например (A1 * B0 + ... + A9 * B9) / (B1 + ... + B9). Нужно избавиться от деления, например, заменить его на сдвиг, алгоритм целочисленный.
числа An: 0..255
числа Bn: 0..10, но их сумма не меньше 10
число n: 9 или 25.
Может кто-нибуть знает как преобразовать алгоритм? или посоветуйте что почитать на подобные темы...