VEA>Можно забабахать массивчик степеней 10-ки и по нему двоичным поиском. Хотя всё зависит от распределения чисел.
int f(int i)
{
int l = 0;
if (i < 0)
{
++l;
i *= -1;
}
if ( i < 10*10*10*10*10*10 )
if ( i < 10*10*10 )
if ( i < 10*10 )
if ( i < 10 )
l += 1;
else
l += 2;
else
l += 3;
else
if ( i < 10*10*10*10*10 )
if ( i < 10*10*10*10 )
l += 4;
else
l += 5;
else
l += 6;
else
if ( i < 10*10*10*10*10*10*10*10 )
if ( i < 10*10*10*10*10*10*10 )
l += 7;
else
l += 8;
else
if ( i < 10*10*10*10*10*10*10*10*10*10 )
if ( i < 10*10*10*10*10*10*10*10*10 )
l += 9;
else
l += 10;
else
l += 11;
return l;
}
надеюсь отсутствие скобок не помешает правильной работе , вроде как все по правилам
Re[5]: количество чисел в представлении целого числа
I>>int f(int i)
a18>...
I>> if ( i < 10*10*10*10*10*10 )
a18>...
I>>
a18>Может, не очень изящно, но зато шустро — быстрее, наверное, получится только при использовании здоровых Lookup-таблиц, да и то не факт.
имхо, точно не факт. тут максимум 4 сравнения, если предугадывание в среднем ошибется 2 раза, то результат получите за 2-3 длины конвейера процессора. даже если всегда ошибется, то за 4-5, пусть длина равна 20, результат в руках за 100 тактов.
за это время можно достучаться только до кеша (разных уровней, приблизительно), а там памяти маловато будет ((
смотря какие лукапы делать
a18>Кстати, ИМХО лучше перебалансировать дерево, взяв первое сравнение не 10^6, а 10^4 — всё-таки, по жизни небольшие числа встречаются гораздо чаще.
пока данные не увидешь, приходится считать их равномерно распределенными.
все зависит от цели.
пусть есть 2 лифта. всего 15 этажей. один лифт на 10 этаже. другой на 15. стоит ли последний спустить куда нибудь?
если цель в минимизации затрат, то не стоит. если цель скорости обслуживания, то стоит спустить на 4-й этаж.
BT>Не подскажет кто как можно в С быстренько определить сколько нужных символов (char), чтобы хранить целое число. BT>Например, есть число 12. Результат должен быть 2. Для 4 — результат 1. И т.д. BT>Ничего кроме десятичного логарифма в голову не приходит! Че-то туплю. Почти уверен, что можно как-то совсем просто!!!
Здравствуйте, 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. Например вот так:
Здравствуйте, bin-tm, Вы писали:
BT>Не подскажет кто как можно в С быстренько определить сколько нужных символов (char), чтобы хранить целое число.
BT>Например, есть число 12. Результат должен быть 2. Для 4 — результат 1. И т.д.
BT>Ничего кроме десятичного логарифма в голову не приходит! Че-то туплю. Почти уверен, что можно как-то совсем просто!!!
BT>itoa и прочие извраты типа strlen не предлагать
BT>Спасибо!
Легкий оффтоп, но афайк у числа "12" char длиной 3, а не два.. ибо в конце \0. Хотя я могу ошибаться
Re: количество чисел в представлении целого числа
От:
Аноним
Дата:
11.11.07 10:59
Оценка:
Здравствуйте, bin-tm, Вы писали:
BT>Ничего кроме десятичного логарифма в голову не приходит!
А что может быть проще десятичного логарифма?
Ну можешь еще сам цикл сделать и в нем на 10 делить.
Re[2]: количество чисел в представлении целого числа
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, bin-tm, Вы писали:
BT>>Ничего кроме десятичного логарифма в голову не приходит!
А>А что может быть проще десятичного логарифма?
А>Ну можешь еще сам цикл сделать и в нем на 10 делить.
Это и есть простейшая реализация целочисленного десятичного логарифма. Хотя чаще используют умножение на 10 — возводят десять поледовательно в степени 1, 2, 3, т.д., и проверяют на больше. Умножение быстрее просто.
Здравствуйте, bin-tm, Вы писали:
BT>Не подскажет кто как можно в С быстренько определить сколько нужных символов (char), чтобы хранить целое число. BT>itoa и прочие извраты типа strlen не предлагать
А нафик вообще считать, сколько char нужно? И почему не TCHAR, например? И кто знает, может вы число прописью хотите, тогда попутно возникает вопрос: на каком языке пропись выводить и в какой кодировке, скажем.
По теме же: для четырехбайтового числа имхо char[11] хватит, учитывая завершающий нуль. Это навскидку, мог ошибиться, но не сильно.
Re[2]: количество чисел в представлении целого числа
Здравствуйте, Flamer, Вы писали:
F>А нафик вообще считать, сколько char нужно? И почему не TCHAR, например? И кто знает, может вы число прописью хотите, тогда попутно возникает вопрос: на каком языке пропись выводить и в какой кодировке, скажем.
Пусть сам решает.
F>По теме же: для четырехбайтового числа имхо char[11] хватит, учитывая завершающий нуль. Это навскидку, мог ошибиться, но не сильно.
ИМХО. Самый рациональный путь. Т.е. всё равно в строку переводить придётся. А уж потом можно выделить ровно столько сколько надо и туда скопировать.
Вообще было обсуждение подобного вопроса на просторах КЫВТа, найдите, кто помнит.
Сам думал о BSR, но эта сабака сама по себе тормознутая.
Только не надо умножений, и, тем более, делений...
Можно забабахать массивчик степеней 10-ки и по нему двоичным поиском. Хотя всё зависит от распределения чисел.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[3]: количество чисел в представлении целого числа
F>>По теме же: для четырехбайтового числа имхо char[11] хватит, учитывая завершающий нуль. Это навскидку, мог ошибиться, но не сильно.
I>для отрицательного не хватит. -2^31
Я ж говорил, что навскидку Знак забыл.
<< Не присоединяйся к нашему миру наркоманов: нас много, а наркоты мало. >>
Re[4]: количество чисел в представлении целого числа
Здравствуйте, Flamer, Вы писали:
F>Здравствуйте, ilnar, Вы писали:
F>>>По теме же: для четырехбайтового числа имхо char[11] хватит, учитывая завершающий нуль. Это навскидку, мог ошибиться, но не сильно.
I>>для отрицательного не хватит. -2^31
F>Я ж говорил, что навскидку Знак забыл.
Re[4]: количество чисел в представлении целого числа
I>int f(int i)
...
I> if ( i < 10*10*10*10*10*10 )
...
I>
Может, не очень изящно, но зато шустро — быстрее, наверное, получится только при использовании здоровых Lookup-таблиц, да и то не факт.
Кстати, ИМХО лучше перебалансировать дерево, взяв первое сравнение не 10^6, а 10^4 — всё-таки, по жизни небольшие числа встречаются гораздо чаще.
Re[6]: количество чисел в представлении целого числа
Здравствуйте, ilnar, Вы писали:
I>пока данные не увидешь, приходится считать их равномерно распределенными.
Тогда и сравнивать лучше начинать с 10^9, там же 3/4 чисел
потом 10^8,7,6... Если цикл, то максимум 2 ошибки.
Кто может посмотреть на такты BSR, после неё одно сравнение остаётся...
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[6]: количество чисел в представлении целого числа
a18>>Может, не очень изящно, но зато шустро — быстрее, наверное, получится только при использовании здоровых Lookup-таблиц, да и то не факт.
I>имхо, точно не факт. тут максимум 4 сравнения, если предугадывание в среднем ошибется 2 раза, то результат получите за 2-3 длины конвейера процессора. даже если всегда ошибется, то за 4-5, пусть длина равна 20, результат в руках за 100 тактов. I>за это время можно достучаться только до кеша (разных уровней, приблизительно), а там памяти маловато будет (( I>смотря какие лукапы делать
Собственно, на мысль о лукапах натолкнул тот факт, что если взять 32-битное целое (для простоты — без знака), то по старшей половине (старшие два байта) из 65536 вариантов только в 6-ти случаях придётся анализировать ещё и младшую половину (hex: 0000, 0001, 000F, 0098, 05F5, 3B9A, если не ошибся), а во всех остальных 65530-ти случаях результат можно сразу вытащить из заранее подготовленной таблички.
Но вот насколько удачно это можно реализовать с учётом кешей — фиг знает.
Наверное, вряд ли это оправданно, ибо сама задача ИМХО довольно надуманная.
a18>>Кстати, ИМХО лучше перебалансировать дерево, взяв первое сравнение не 10^6, а 10^4 — всё-таки, по жизни небольшие числа встречаются гораздо чаще. I>пока данные не увидешь, приходится считать их равномерно распределенными.
Да, сорри, я почему-то решил взять медиану по выходу (1-10 цифр без знака), а не по входу (4 млрд. чисел).
Re[4]: количество чисел в представлении целого числа
если уж оптимизироваться, тогда в x86 процах есть команда получения первого установленного бита (слева и/или справа)
думаю, получив индексы первых двух единиц, можно сказать. подумать надо.
Здравствуйте, bin-tm, Вы писали:
BT>Не подскажет кто как можно в С быстренько определить сколько нужных символов (char), чтобы хранить целое число.
BT>Например, есть число 12. Результат должен быть 2. Для 4 — результат 1. И т.д.
BT>Ничего кроме десятичного логарифма в голову не приходит! Че-то туплю. Почти уверен, что можно как-то совсем просто!!!
BT>itoa и прочие извраты типа strlen не предлагать
BT>Спасибо!
Провел исследование.
Возьмем индекс самого старшего установленного бита, idx, отсчет от нуля
Переходы на следующий символ происходят при ((idx % 10) % 3)==0 -- это верно хотя бы до 64битных чисел. для больших может появится изменение начиная с некоторого бита будет условие (((idx-1) % 10) % 3)==0, это связано с 2^10=1024 (цифры 10 и 3 отсюда), тенденцию может поменять 24 на хвосте
При этом на переход влияют установленность битов idx-1 и idx-2 -- если любой из них установлен, то происходит переход
алгоритм для числа num:
1. получить idx для num
2. len = idx/10*3
3. if (((idx % 10) % 3)==0 && (num>>(idx-2))) ++len;
4. вернуть len
для Intel 80x86 есть команда процессора, котрый дает idx по num, называется bsr (bit scan reverse)
Здравствуйте, ilnar, Вы писали: I>потому что топикстартер хочет попроще, о десятичном логарифме и так знает.
М... ну а выигрышь в скорости от реализации будет на порядок?
I>встречный вопрос: зачем из пушки стрелять в воробья???
шоб картечью всю стаю накрыло!
Здравствуйте, loknalori, Вы писали:
L>Здравствуйте, ilnar, Вы писали: I>>потому что топикстартер хочет попроще, о десятичном логарифме и так знает. L>М... ну а выигрышь в скорости от реализации будет на порядок?
ожидаю, что будет. Все же нужно проверить. может завтра скажу.
I>>встречный вопрос: зачем из пушки стрелять в воробья??? L>шоб картечью всю стаю накрыло!
это смотря чем начинять
Re[3]: количество чисел в представлении целого числа
От:
Аноним
Дата:
12.11.07 19:19
Оценка:
Здравствуйте, stab, Вы писали:
S>Операция взятия "самого старшего установленного бита" — это двоичный логарифм.
В общем как ни крути, а без логарифма не обойтись
Можно прямо вычислять, можно на 10 в цикле делить, или умножать.
Можно через двоичный логарифм
Re[4]: количество чисел в представлении целого числа
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, 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, дела совсем плохи становятся. В общем как всегда, всё зависит от контекста использования.
Если не так часто используется то ну нафиг такие извраты...
, вроде как все по правилам 
