The fastest way to find the highest power 10 is less than x

Question

Is there any quick way to find the highest power 10 less than a given number?

I am using this algorithm at the moment, but something inside me is dying anytime I see it:

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

I could implement simple log10 and pow functions for my problems with one loop each, but still I wonder if there is any bitmagic for decimal numbers.

Answer 1

Alternative algorithm:

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

Answer 2

Log and power are expensive operations. If you want fast, you probably want to find the IEEE binary indicator in the table to get an approximate power of ten, and then check if the mantissa changes to +1 or not. It should be 3 or 4 whole machine instructions (alternatively O (1) with a fairly small constant).

Table data:

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

then your calculations should be:

  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]; 

[You really need to write this as assembler in order to squeeze all the last hours.] [This code has not been verified.]

However, if you insist on doing this in python, the interpreter overhead can attenuate the log / exp time, and it may not matter.

So, do you want to write fast or want to write briefly?

EDIT 12/23: OP now tells us that its “x” is integral. Assuming it is a 64 (or 32) bit integer, my suggestion still works, but obviously the "IEEE_Exponent" does not exist. Most processors have a “find first” command that tells you the number of 0 bits in the left (most significant) part of the value, for example, leading zeros; you are probably essentially 64 (or 32) minus the power of two for the value. Given the exponent = 64 - leadingzeros, you have the power of two exponents, and most of the rest of the algorithm remains virtually unchanged (the changes remain for the reader).

If the processor does not have a find-first-one instruction, then probably the best option is a balanced difference tree to determine the power of ten. For 64 bits, such a tree will occupy no more than 18 to determine the indicator (10 ^ 18 ~~ 2 ^ 64).

Answer 3

Create an array of powers of 10. Find it for the largest value less than x.

If x is quite small, you may find that linear search provides better performance than binary search, due in particular to fewer branch predictions.

Answer 4

Asymptotically fast way, as far as I know, involves repeated squaring.

 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 

The algorithm takes logarithmic time and space in N, which is linear up to N representation size. [Timing is probably a little worse because I am optimistic with optimism]

Note that I took arbitrarily large integers (watch out for overflows!), Since the naive-10-to-end algorithm is probably fast enough when dealing only with 32-bit integers.

Answer 5

Given that this is language independent, if you can get the power of two for which that number matters, for example y in x * 2 ^ y (this is a way of storing the number, although I'm not sure I saw a simple way to access y in any language that I used), then if

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

(one floating point division)

10 ^ z or 10 ^ (z + 1) will be your answer, although 10 ^ z is still not that simple (try fixing).

Answer 6

I think the fastest way is O (log (log (n)) ^ 2), while while loop takes O (log (log (n)) ^ and can be a recursive finite time call (we can say that O (c), where see is constant), the first recursive call takes log (log (sqrt (n))) takes a second time .. and the number of sqrt in sqrt (sqrt (sqrt .... (n)) <10 is log (log (n )) and a constant due to machine limitations.

  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

In Python:

10 ** (LEN (ul (intermediate (x))) - 1)

Answer 8

I have timed methods with the following variations in C ++ for a value of type size_t (nesting improves performance but does not change the relative order).

Try 1: Multiply until it finds the number.

 size_t try1( size_t a ) { size_t scalar = 1ul; while( scalar * 10 < a ) scalar *= 10; return scalar; } 

Try 2: Multiway if (can also be programmed using the lookup table).

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

Try 3: Changed from findPow10 @Saaed Amiri, which uses a square to quickly find very large capacities than Try 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; } 

Try 4: a lookup table indexed using the leading zero count command according to @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 ); } 

Dates: (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 is superior to everything in C ++, but requires that we know that integers are of finite size. try3 slower than try1 in this test for smaller values ​​of the final value of the loop; for larger numbers of try3 , the beat of try1 . In python, everything is difficult to do because integers are unlimited, so I would combine try2 with try3 to quickly process numbers to a fixed limit and then process, possibly very large numbers.

In python, I think searching using list comprehension is probably faster than multi-page. if.

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