Самый быстрый способ найти наибольшую мощность 10 меньше, чем х

Question

Есть ли какой-нибудь быстрый способ найти наибольшую степень 10, меньшую заданного числа?

Сейчас я использую этот алгоритм, но что-то внутри меня умирает каждый раз, когда я его вижу:

10**( int( math.log10(x) ) ) # python
pow( 10, (int) log10(x) )   // C

Я мог бы реализовать простые функции log10 и pow для своих задач с одним циклом каждая, но все же мне интересно, есть ли какая-то магия для десятичных чисел.

Answer 1

Альтернативный алгоритм:

i = 1;
while((i * 10) < x)
    i *= 10;

Answer 2

Бревно и энергопотребление являются дорогостоящими операциями. Если вы хотите быстро, вы, вероятно, хотите посмотреть двоичный показатель 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, накладные расходы интерпретатора могут затопить время log / exp и это может не иметь значения.

Итак, вы хотите быстро, или вы хотите короткую запись?

РЕДАКТИРОВАТЬ 12/23: ОП теперь говорит нам, что его "х" является целым. Исходя из предположения, что это 64-разрядное (или 32-разрядное) целое число, мое предложение все еще работает, но, очевидно, «IEEE_Exponent» не существует. У большинства процессоров есть команда «найти первым», которая сообщит вам число 0 битов в левой (самой значимой) части значения, например, ведущие нули; вероятно, это 64 (или 32) минус степень двойки для значения. Учитывая показатель степени = 64 - ведущие нули, у вас есть степень двух показателей, и большая часть остальной части алгоритма практически не изменяется (модификации оставлены для читателя).

Если у процессора нет инструкции «найти первым», то, вероятно, лучшим вариантом будет сбалансированное дерево дискриминации для определения степени десяти. Для 64-битного такого дерева потребуется не более 18 сравнений для определения показателя степени (10 ^ 18 ~~ 2 ^ 64).

Answer 3

Создайте массив степеней 10. Найдите в нем наибольшее значение, меньшее x.

Если x довольно мало, вы можете обнаружить, что линейный поиск обеспечивает лучшую производительность, чем двоичный поиск, из-заотчасти для того, чтобы меньше ошибочных предсказаний ветвей.

Answer 4

Асимптотически самый быстрый способ, насколько я знаю, включает повторное возведение в квадрат.

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.[Сроки, вероятно, немного хуже, потому что я оптимистично упростил]

Обратите внимание, что я принял произвольно большие целые числа (следите за переполнением!), Так как наивный алгоритм "умножение на 10-пока-до", вероятно, достаточно быстрпри работе только с 32-битными целыми числами.

Answer 5

В Python:

10 ** (Len (ул (интермедиат (х))) - 1)

Answer 6

Я думаю, что самый быстрый способ - это O (log (log (n)) ^ 2), цикл while принимает O (log (log (n))), и это может быть рекурсивный вызов конечного времени (можно сказать O (c) ), где см. является константой), первый рекурсивный вызов занимает журнал (log (sqrt (n))), второй раз занимает .. и число sqrt в sqrt (sqrt (sqrt .... (n)) <10 является лог (log (n)) и постоянная из-за ограничений машины. </p>

    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);
    }

Answer 7

Учитывая, что это не зависит от языка, если вы можете получить степень двойки, для которой это число значимо, например, y в x * 2 ^ y (то есть способ хранения числа, хотя я не уверен видел простой способ доступа к y на любом языке, который я использовал), тогда если

z = int(y/(ln(10)/ln(2))) 

(одно деление с плавающей запятой)

10 ^ z или 10 ^ (z + 1) будет вашим ответом, хотя 10 ^ z все еще не так просто (прошу исправить).

Answer 8

Я рассчитал методы со следующими изменениями в C ++ для значения a, являющегося типом size_t (встраивание улучшает производительность, но не меняет относительное упорядочение).

Попробуйте 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: Таблица поиска индексируется с использованием инструкции подсчета ведущих нулей согласно @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

lookup / multiway-if превосходит все в C ++, но требует, чтобы мы знали, что целые числа имеют конечный размер. try3 медленнее, чем try1 в этом тесте для меньших значений конечного значения цикла, для больших чисел try3 ударов try1. В Python все усложняется, потому что целые числа не ограничены, поэтому я бы скомбинировал try2 с try3, чтобы быстро обработать числа до фиксированного предела, а затем обработать возможно очень большие числа.

В python я думаю, что поиск с использованием понимания списка, вероятно, быстрее, чем multiway-if.

# where we previously define lookuptable = ( 1, 10, 100, ..... )
scalar = [i for i in lookuptable if i < a][-1]