Самый быстрый способ найти наибольшую мощность в 10 меньше x
https://stackoverflow.com/questions/4513707
-
12-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Есть ли быстрый способ найти наибольшую мощность на 10 меньше, чем данное число?
В настоящее время я использую этот алгоритм, но что -то внутри меня умирает в любое время, когда я его вижу:
10**( int( math.log10(x) ) ) # python
pow( 10, (int) log10(x) ) // C
Я мог бы реализовать простые log10 а также pow Функции для моих проблем с одной петлей каждый, но все же мне интересно, есть ли немного волшебства для десятичных чисел.
Решение
Альтернативный алгоритм:
i = 1;
while((i * 10) < x)
i *= 10;
Другие советы
Журнал и питание - это дорогие операции. Если вы хотите быстро, вы, вероятно, хотите посмотреть бинарную экспонент IEEE в таблице, чтобы получить приблизительную мощность десяти, а затем проверить, заставляет ли мантисса изменение на +1 или нет. Это должно быть 3 или 4 целое число Инструкции машины (альтернативно O (1) с довольно маленькой постоянной).
Даны таблицы:
int IEEE_exponent_to_power_of_ten[2048]; // needs to be 2*max(IEEE_exponent)
double next_power_of_ten[600]; // needs to be 2*log10(pow(2,1024)]
// you can compute these tables offline if needed
for (p=-1023;p>1023;p++) // bounds are rough, see actual IEEE exponent ranges
{ IEEE_exponent_to_power_of_ten[p+1024]=log10(pow(2,p)); // you might have to worry about roundoff errors here
next_power_of_ten[log10(pow(2,p))+1024]=pow(10,IEEE_exponent_to_power_of_ten[p+1024]);
}
тогда ваши вычисления должны быть:
power_of_ten=IEEE_exponent_to_power_of_10[IEEE_Exponent(x)+1023];
if (x>=next_power_of_ten[power_of_ten]) power_of_ten++;
answer=next_power_of_ten[power_of_ten];
Возможно, вам действительно потребуется написать это как ассемблер, чтобы выжать все последние часы.] [Этот код не проверяется.
Однако, если вы настаиваете на том, чтобы делать это в Python, накладные расходы переводчика могут затопить время журнала/EXP, и это может не иметь значения.
Итак, вы хотите быстро, или вы хотите короткий к записи?
РЕДАКТИРОВАТЬ 12/23: ОП теперь говорит нам, что его «X» является неотъемлемой частью. При предположении, что это 64 (или 32) битовое целое число, мое предложение все еще работает, но, очевидно, нет «ieee_exponent». У большинства процессоров есть инструкция «Найти первый», которая сообщит вам количество 0 бит на левой (наиболее значимой) часть значения, например, ведущие нули; Скорее всего, это в сущности 64 (или 32) минус мощность двух для значения. Учитывая показатель = 64 - Leadingzeros, у вас есть сила двух показателей, и большая часть остальной части алгоритма по сути не изменилась (модификации, оставленные для читателя).
Если у процессора нет инструкции «Найти первую первую очередь», то, вероятно, лучшая ставка-это сбалансированное дерево дискриминации, чтобы определить силу десяти. В течение 64 бит такое дерево потребует не более 18 сравнений, чтобы определить показатель (10^18 ~~ 2^64).
Создайте массив полномочий 10. Поиск по ней для наибольшего значения, меньшего, чем x.
Если X довольно мал, вы можете обнаружить, что линейный поиск обеспечивает лучшую производительность, чем бинарный поиск, отчасти из-за меньшего количества ошибок в филиале.
Насколько я знаю, асимптотически самый быстрый способ включает в себя повторный квадрат.
func LogFloor(int value, int base) as int
//iterates values of the form (value: base^(2^i), power: 2^i)
val superPowers = iterator
var p = 1
var c = base
while c <= value
yield (c, p)
c *= c
p += p
endwhile
enditerator
//binary search for the correct power
var p = 0
var c = 1
for val ci, pi in superPowers.Reverse()
if c*ci <= value
c *= ci
p += pi
endif
endfor
return p
Алгоритм занимает логарифмическое время и пространство в n, что является линейным размером представления N. [Временная граница, вероятно, немного хуже, потому что я оптимистично упростил
Обратите внимание, что я предполагал произвольно большие целые числа (следите за переполнением!), Поскольку наивный алгоритм Times-10-le Over, вероятно, достаточно быстр, когда имел дело с всего 32-битным целым числом.
Учитывая, что это не зависит от языка, если вы можете получить силу двух, что это число, например, в x*2^y (именно так, как хранится число, хотя я не уверен, что видел простой способ получить доступ к Y на любом языке, который я использовал), тогда если
z = int(y/(ln(10)/ln(2)))
(Одно плавающее подразделение)
10^z или 10^(z+1) будет вашим ответом, хотя 10^z все еще не так просто (просит быть исправленным).
Я думаю, что самый быстрый способ - это (log (log (n))^2), цикл while принимает O (log (n)), и это может быть рекурсивное конечное время (мы можем сказать O (c) где см. is constant), first recursive call is takes log(log(sqrt(n))) time second takes .. and the number of sqrt in sqrt(sqrt(sqrt....(n)) < 10 is log(log( n)) и постоянный, из -за ограничений машины.
static long findPow10(long n)
{
if (n == 0)
return 0;
long i = 10;
long prevI = 10;
int count = 1;
while (i < n)
{
prevI = i;
i *= i;
count*=2;
}
if (i == n)
return count;
return count / 2 + findPow10(n / prevI);
}
В Python:
10 ** (Len (str (int (x)))-1)
Я рассчитывал методы со следующими вариациями в C ++ для значения a быть size_t Тип (Inlining улучшает производительность, но не меняет относительный заказ).
Попробуйте 1: умножьте, пока не найдите номер.
size_t try1( size_t a )
{
size_t scalar = 1ul;
while( scalar * 10 < a ) scalar *= 10;
return scalar;
}
Попробуйте 2: Multiway IF (также можно запрограммировать с помощью таблицы поиска).
size_t try2( size_t a )
{
return ( a < 10ul ? 1ul :
( a < 100ul ? 10ul :
( a < 1000ul ? 100ul :
( a < 10000ul ? 1000ul :
( a < 100000ul ? 10000ul :
( a < 1000000ul ? 100000ul :
( a < 10000000ul ? 1000000ul :
( a < 100000000ul ? 10000000ul :
( a < 1000000000ul ? 100000000ul :
( a < 10000000000ul ? 1000000000ul :
( a < 100000000000ul ? 10000000000ul :
( a < 1000000000000ul ? 100000000000ul :
( a < 10000000000000ul ? 1000000000000ul :
( a < 100000000000000ul ? 10000000000000ul :
( a < 1000000000000000ul ? 100000000000000ul :
( a < 10000000000000000ul ? 1000000000000000ul :
( a < 100000000000000000ul ? 10000000000000000ul :
( a < 1000000000000000000ul ? 100000000000000000ul :
( a < 10000000000000000000ul ? 1000000000000000000ul :
10000000000000000000ul )))))))))))))))))));
}
Попробуйте 3: Модифицирован из FindPow10 @SAAED Amiri, который использует квадрат, чтобы более быстро найти очень большие способности, чем попробовать 1.
size_t try3( size_t a )
{
if (a == 0)
return 0;
size_t i, j = 1;
size_t prev = 1;
while( j != 100 )
{
i = prev;
j = 10;
while (i <= a)
{
prev = i;
i *= j;
j *= j;
}
}
return prev;
}
Попробуйте 4: Таблица поиска, индексированная с использованием инструкции по Zeros, в соответствии с @ira Baxter.
static const std::array<size_t,64> ltable2{
1ul, 1ul, 1ul, 1ul, 1ul, 10ul, 10ul, 10ul,
100ul, 100ul, 100ul, 1000ul, 1000ul, 1000ul,
1000ul, 10000ul, 10000ul, 10000ul, 100000ul,
100000ul, 100000ul, 1000000ul, 1000000ul,
1000000ul, 1000000ul, 10000000ul, 10000000ul,
10000000ul, 100000000ul, 100000000ul,
100000000ul, 1000000000ul, 1000000000ul,
1000000000ul, 1000000000ul, 10000000000ul,
10000000000ul, 10000000000ul, 100000000000ul,
100000000000ul, 100000000000ul, 1000000000000ul,
1000000000000ul, 1000000000000ul, 1000000000000ul,
10000000000000ul, 10000000000000ul, 10000000000000ul,
100000000000000ul, 100000000000000ul, 100000000000000ul,
1000000000000000ul, 1000000000000000ul, 1000000000000000ul,
1000000000000000ul, 10000000000000000ul, 10000000000000000ul,
10000000000000000ul, 100000000000000000ul, 100000000000000000ul,
100000000000000000ul, 100000000000000000ul, 1000000000000000000ul,
1000000000000000000ul };
size_t try4( size_t a )
{
if( a == 0 ) return 0;
size_t scalar = ltable2[ 64 - __builtin_clzl(a) ];
return (scalar * 10 > a ? scalar : scalar * 10 );
}
Время заключается в следующем (GCC 4.8)
for( size_t i = 0; i != 1000000000; ++i) try1(i) 6.6
for( size_t i = 0; i != 1000000000; ++i) try2(i) 0.3
for( size_t i = 0; i != 1000000000; ++i) try3(i) 6.5
for( size_t i = 0; i != 1000000000; ++i) try4(i) 0.3
for( size_t i = 0; i != 1000000000; ++i) pow(10,size_t(log10((double)i)))
98.1
Поиск/Multiway-I, если все в C ++, но требуется, чтобы мы знали, что целые числа имеют конечный размер. try3 медленнее, чем try1 В этом тесте для меньших значений конечного значения цикла для больших чисел try3 удары try1. Анкет В Python вещи затруднены, потому что целые числа не ограничены, поэтому я бы комбинировал try2 с try3 Чтобы быстро обрабатывать числа до фиксированного предела, обрабатывайте, возможно, очень большие числа.
В Python я думаю, что поиск с использованием понимания списка, вероятно, быстрее, чем мультивея.
# where we previously define lookuptable = ( 1, 10, 100, ..... )
scalar = [i for i in lookuptable if i < a][-1]
