Здравствуйте, ilnar, Вы писали: I>потому что топикстартер хочет попроще, о десятичном логарифме и так знает.
М... ну а выигрышь в скорости от реализации будет на порядок?
I>встречный вопрос: зачем из пушки стрелять в воробья???
шоб картечью всю стаю накрыло!
Здравствуйте, loknalori, Вы писали:
L>Здравствуйте, ilnar, Вы писали: I>>потому что топикстартер хочет попроще, о десятичном логарифме и так знает. L>М... ну а выигрышь в скорости от реализации будет на порядок?
ожидаю, что будет. Все же нужно проверить. может завтра скажу.
I>>встречный вопрос: зачем из пушки стрелять в воробья??? L>шоб картечью всю стаю накрыло!
это смотря чем начинять
Re[2]: количество чисел в представлении целого числа
Здравствуйте, ilnar, Вы писали:
I>Провел исследование. I>Возьмем индекс самого старшего установленного бита, idx, отсчет от нуля I>Переходы на следующий символ происходят при ((idx % 10) % 3)==0 -- это верно хотя бы до 64битных чисел. для больших может появится изменение начиная с некоторого бита будет условие (((idx-1) % 10) % 3)==0, это связано с 2^10=1024 (цифры 10 и 3 отсюда), тенденцию может поменять 24 на хвосте I>При этом на переход влияют установленность битов idx-1 и idx-2 -- если любой из них установлен, то происходит переход
I>алгоритм для числа num: I>1. получить idx для num I>2. len = idx/10*3 I>3. if (((idx % 10) % 3)==0 && (num>>(idx-2))) ++len; I>4. вернуть len
I>для Intel 80x86 есть команда процессора, котрый дает idx по num, называется bsr (bit scan reverse)
Операция взятия "самого старшего установленного бита" — это двоичный логарифм. По сути, вы пытаетесь осуществить преобразование по широко известной схеме изменения основания логарифма — lg(x) = lb(x) / lb(10). Если подойти к проблеме с пониманием того, что это действительно так, то для UInt32 получаем:
function IntLog10(number: Cardinal): Cardinal;
const
powers: array[0..9] of Cardinal =
(
1, 10, 100, 1000, 10000, 100000, 1000000, 10000000,
100000000, 1000000000
);
function IntLog2(number: Cardinal): Cardinal;
asm
bsr EAX, EAX
end;
begin
Result := ((IntLog2(number) + 1) * 1233) shr 12;
if number >= powers[Result] then
begin
Inc(Result);
end;
end;
"+ 1" — компенсация за округление вниз. "* 1233) shr 12" — приближённое вычисление lg(x) = lb(x) / lb(10) = lb(x) * lb(10)^-1 ~ lb(x) * 1233/4096, что даёт ошибку только в шестом знаке после запятой, но этого не достаточно, т.к. используется целочисленный двоичный логарифм, "if number >=" — компенсирует эти неточности. Чтобы получить максимальную скорость надо избавиться от условного перехода. Это не составит труда, если переписать на ассемблере — cmp + setxx + add. Плюс, ещё заинлайнить IntLog2. Например вот так:
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, stab, Вы писали:
S>>Операция взятия "самого старшего установленного бита" — это двоичный логарифм.
А>В общем как ни крути, а без логарифма не обойтись А>Можно прямо вычислять, можно на 10 в цикле делить, или умножать. А>Можно через двоичный логарифм
логически -- да. но не забываем про представление чисел в компьютере.
да и челочисленный логарифм быстрее чем с плавающей запятой.
как ни крути, специализированный вариант лучше.
Re[3]: количество чисел в представлении целого числа
17.6 битовое сканирование
-------------------------
BSF и BSR — самые плохо оптимизированные инструкции на Pentium, беря на
исполнение 11 + 2*n тактов, где n — число пропущенных нулей.
(на поздних процессорах берут только 1 или 2)
Следующий код эмулирует BSR ECX,EAX:
TEST EAX,EAX
JZ SHORT BS1
MOV DWORD PTR [TEMP],EAX
MOV DWORD PTR [TEMP+4],0
FILD QWORD PTR [TEMP]
FSTP QWORD PTR [TEMP]
WAIT ; для совместимости с ранними процессорами
MOV ECX, DWORD PTR [TEMP+4]
SHR ECX,20
SUB ECX,3FFH
TEST EAX,EAX ; сбрасываем флаг нуля
BS1:
Кто может уточнить сколько на P4 и K8?
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[4]: количество чисел в представлении целого числа
Здравствуйте, VEAPUK, Вы писали:
VEA>17.6 битовое сканирование VEA>------------------------- VEA>BSF и BSR — самые плохо оптимизированные инструкции на Pentium, беря на VEA>исполнение 11 + 2*n тактов, где n — число пропущенных нулей. VEA>(на поздних процессорах берут только 1 или 2)
VEA>
VEA>Следующий код эмулирует BSR ECX,EAX:
VEA> TEST EAX,EAX
VEA> JZ SHORT BS1
VEA> MOV DWORD PTR [TEMP],EAX
VEA> MOV DWORD PTR [TEMP+4],0
VEA> FILD QWORD PTR [TEMP]
VEA> FSTP QWORD PTR [TEMP]
VEA> WAIT ; для совместимости с ранними процессорами
VEA> MOV ECX, DWORD PTR [TEMP+4]
VEA> SHR ECX,20
VEA> SUB ECX,3FFH
VEA> TEST EAX,EAX ; сбрасываем флаг нуля
VEA>BS1:
VEA>
VEA>Кто может уточнить сколько на P4 и K8?
На P4E (не Core) для bsr в случае регистр + непосредственный операнд latency всегда 8, для K8 всегда 2. Что удивительно старые P4 (до Presler) имели latency всего 6 и исполняли bsr на mmx юните, а новые на alu. Для Core1\2 нет информации.
В общем, если даже предположить что в приведённом коде все инструкции имеют latency 1, то получаем 11. Если учесть что FILD и FSTP имеют latency порядка 10 и на P4 и P4E и на K8, то он совсем не эффективен.
Re[5]: количество чисел в представлении целого числа
Здравствуйте, stab, Вы писали:
S>На P4E (не Core) для bsr в случае регистр + непосредственный операнд latency всегда 8, для K8 всегда 2. Что удивительно старые P4 (до Presler) имели latency всего 6 и исполняли bsr на mmx юните, а новые на alu. Для Core1\2 нет информации.
S>В общем, если даже предположить что в приведённом коде все инструкции имеют latency 1, то получаем 11. Если учесть что FILD и FSTP имеют latency порядка 10 и на P4 и P4E и на K8, то он совсем не эффективен.
Это был код оптимизированный под первый/про пень...
Раз дела обстоят хорошо, то к меня есть идея, как избавится (с помощью 2-х массивов вместо одного) от умножени и сдвига.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[6]: количество чисел в представлении целого числа
Здравствуйте, VEAPUK, Вы писали:
VEA>Это был код оптимизированный под первый/про пень... VEA>Раз дела обстоят хорошо, то к меня есть идея, как избавится (с помощью 2-х массивов вместо одного) от умножени и сдвига.
Да понятно дело, можно в таблицу забить значения lb(x) / lb(10), только это будет уже две таблицы, одна на 10 значений, друга на 32, а это уже многовато. А ежели потребуется для 64-ёх битов, то тут таблицы в одну полоску кэша при всём желании не уместить, даже если пожертвовать выравниванием данных. Нужен хороший баланс между обращениями к памяти и вычислениями, каждое обращение к памяти может стоить нескольких сотен холостых тактов. Если много пользоваться таблицами, часто наблюдается парадоксальная ситуация — на тестах всё ок, но в реальном проекте резкое падение производительности из-за того что возникают постоянные промахи в кэше, ладно если это L1, но когда забивается L2, дела совсем плохи становятся. В общем как всегда, всё зависит от контекста использования.
Re[7]: количество чисел в представлении целого числа
Здравствуйте, stab, Вы писали:
S>Да понятно дело, можно в таблицу забить значения lb(x) / lb(10), только это будет уже две таблицы, одна на 10 значений, друга на 32, а это уже многовато.
Немного не так. i:0-31 — 10^int(lg(2^i+1)), если не попадает в разрядную сетку, то MAX_UINT
второй массив байтов из 33-х, в котором уже само кол-во символом, можно и с учётом '\0'.
33-ий для 2^32-1. S> А ежели потребуется для 64-ёх битов, то тут таблицы в одну полоску кэша при всём желании не уместить, даже если пожертвовать выравниванием данных. Нужен хороший баланс между обращениями к памяти и вычислениями, каждое обращение к памяти может стоить нескольких сотен холостых тактов. Если много пользоваться таблицами, часто наблюдается парадоксальная ситуация — на тестах всё ок, но в реальном проекте резкое падение производительности из-за того что возникают постоянные промахи в кэше, ладно если это L1, но когда забивается L2, дела совсем плохи становятся. В общем как всегда, всё зависит от контекста использования.
Если не так часто используется то ну нафиг такие извраты...
