Существует ли в природе алгоритм нахождения средненего арифметического
3-х целых беззнаковых чисел без использования такой медленной операции,
как деление?
А двух? И почему целочисленное деление — медленная операция? Боюсь соврать, но уже Pentium'ы делали это за такт.
AD>Существует ли в природе алгоритм нахождения средненего арифметического AD>3-х целых беззнаковых чисел без использования такой медленной операции, AD>как деление?
XZ>А двух? И почему целочисленное деление — медленная операция? Боюсь соврать, но уже Pentium'ы делали это за такт.
Для двух — это битовый сдвиг (: А Pentium'ы делили целые дворды за 41 такт.
[offtopic]
Пользуясь случаем, хочу выразить своё мнение по поводу Flaredance Screensaver:
1) Как пользователь — я очень падок до всяких фейерверков, и сам когда-то писал, но flaredance мне не понравился. одинаковые выстрелы, мало блюра, не похоже на реальный. Из плюсов — очень понравилось освещение горизонта, сполохи
2) Как программист — это хорошо, что вы там чем-то запаковали программу, софтайс плохо с ней дружит (: Но бряки на виндовые сообщения проходят нормально, и это плохо. для вас.
Здравствуйте, _gc, Вы писали:
XZ>>А двух? И почему целочисленное деление — медленная операция? Боюсь соврать, но уже Pentium'ы делали это за такт.
_gc>Для двух — это битовый сдвиг (: А Pentium'ы делили целые дворды за 41 такт.
Жуть какая. Не знал. Мои познания — справочник по системе команд. Сейчас полезу освежу.
_gc>[offtopic] _gc>Пользуясь случаем, хочу выразить своё мнение по поводу Flaredance Screensaver:
Спасибо! _gc>1) Как пользователь — я очень падок до всяких фейерверков, и сам когда-то писал, но flaredance мне не понравился. одинаковые выстрелы, мало блюра, не похоже на реальный. Из плюсов — очень понравилось освещение горизонта, сполохи
Всё впереди — было желание попробовать тормознуть и пораньше выпустить первую версию. _gc>2) Как программист — это хорошо, что вы там чем-то запаковали программу, софтайс плохо с ней дружит (: Но бряки на виндовые сообщения проходят нормально, и это плохо. для вас.
Зелёный зверёк с крокодиловой кожей. За два года (другие сэйверы на том же движке с той же защитой) ещё не отломали (ТТТ) — и это уже хорошо.
Здравствуйте, ArtDenis, Вы писали:
>> И почему целочисленное деление — медленная операция? Боюсь соврать, но уже Pentium'ы делали это за такт. AD>Просто код пишется не для пентиума.
Ага. Тогда — сумма трех чисел с последующим делением сдвигами.
Здравствуйте, ArtDenis, Вы писали:
AD>Существует ли в природе алгоритм нахождения средненего арифметического AD>3-х целых беззнаковых чисел без использования такой медленной операции, AD>как деление?
В книге Генри Уоррена младшего "Алгоритмические трюки для программистов" приводится такой код (страница 157):
li M, 0xAAAAAAAB ; загрузка магическго числа (2^32 + 1) / 3
mulhu q, M, n ; q = floor(M * n / 2^32)
shri q, q, 1 ;
muli t, q, 3 ; вычисляем остаток по формуле
sub r, n, t ; r = n - q * 3
здесь:
n — входное целое число (числитель)
M — сюда загружается "магическое число"
t — временный регистр
q — в нём будет размещено частное
r — в нём будет размещён остаток
------------------------------------
li RT,I — загружает I в RT
mulhu RT,RA,RB — загружает в RT старшие 32 бита произведения RA и RB
shri RT,RA,I — RT <- RA сдвиг вправо на I
muli RT,RA,I — RT <- RA * I
sub RT,RA,RB — RT <- RA — RB
В этой книжке так же рассказано как вычислять магические числа и для не 32-ух битных машин.
K> li M, 0xAAAAAAAB ; загрузка магическго числа (2^32 + 1) / 3
K> mulhu q, M, n ; q = floor(M * n / 2^32)
K> shri q, q, 1 ;
K> muli t, q, 3 ; вычисляем остаток по формуле
K> sub r, n, t ; r = n - q * 3
K>
Я это и имел ввиду, говоря про умножение на 1/3 в первом посте. Только вот:
1) как ваша программа себя поведёт при n, не кратном 3?
2) зачем здесь сдвиг вправо?
Здравствуйте, ArtDenis, Вы писали:
AD>Существует ли в природе алгоритм нахождения средненего арифметического AD>3-х целых беззнаковых чисел без использования такой медленной операции, AD>как деление?
А чем не подходит такое?
(((a + b) >> 1) + c) >> 1
Здесь, конечно, возникает некоторая дополнительная погрешность в нижнюю сторону, но ее можно попытаться скомпенсировать добавлением единицы в одну из сумм.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
korzhik пишет: > В книге Генри Уоррена младшего "Алгоритмические трюки для программистов" приводится такой код (страница 157):
Спасибо, сейчас буду пробовать.
Здравствуйте, _gc, Вы писали:
_gc>Здравствуйте, korzhik, Вы писали:
K>>
K>> li M, 0xAAAAAAAB ; загрузка магическго числа (2^32 + 1) / 3
K>> mulhu q, M, n ; q = floor(M * n / 2^32)
K>> shri q, q, 1 ;
K>> muli t, q, 3 ; вычисляем остаток по формуле
K>> sub r, n, t ; r = n - q * 3
K>>
_gc>Я это и имел ввиду, говоря про умножение на 1/3 в первом посте. Только вот: _gc>1) как ваша программа себя поведёт при n, не кратном 3?
Вариант хороший, но удалось реализовать деление без использования явного
умножения (хоть и с погрешностью). Но, оказалось, что даже небольшая
погрешность меня устраивает...
Здравствуйте, ArtDenis, Вы писали:
AD>ArtDenis пишет: >> Но этот код даёт достаточно большие погрешности когда summa превышает >> 256...
AD>Оказалось, что эта погрешность довольно хорошо компенсируется AD>добавлением ещё одного слогаемого: (summa >> 4)
AD>В результате получается AD>
AD>Хоть результат получился с небольшой погрешностью, но можно сказать, что AD>вопрос решён
Мдя!!!
Енто будет работать на intel архитектуре как минимум в 3 раза дольше чем (a+b+c)/3
Во первых целочисленное умножение внутри проца уже давно реализуется за счет вещественного.
Во вторых и целочисленное и вещественное оба работают максимум за 1 такт.
В третих, как заметили выше, деление на константу всегда можно осуществить умножением на обратную к ней константу
и последующим сдвигом, а любой нормальный компилер прекрасно об этом осведомлен.
Так что лучше чем (a+b+c)/3 не напишешь.
Здравствуйте, Аноним, Вы писали:
А>Мдя!!! А>Енто будет работать на intel архитектуре как минимум в 3 раза дольше чем (a+b+c)/3 А>Во первых целочисленное умножение внутри проца уже давно реализуется за счет вещественного. А>Во вторых и целочисленное и вещественное оба работают максимум за 1 такт. А>В третих, как заметили выше, деление на константу всегда можно осуществить умножением на обратную к ней константу А>и последующим сдвигом, а любой нормальный компилер прекрасно об этом осведомлен. А>Так что лучше чем (a+b+c)/3 не напишешь.
Уважаемый Аноним, прежде чем высказывать подобную ахинею, не мешало бы просто взять и проверить. Деление у него за один такт работает. С плавающей точкой. Ага, шас.
А>целочисленное умножение внутри проца уже давно реализуется за счет вещественного
Ссылки в студию!
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Здравствуйте, korzhik, Вы писали:
K>В книге Генри Уоррена младшего "Алгоритмические трюки для программистов" приводится такой код (страница 157):
[]
K>В этой книжке так же рассказано как вычислять магические числа и для не 32-ух битных машин.
Звёзды мне говорят, что компилятор сделает то же самое
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
