Fastest way to find the largest power of 10 smaller than x

Question

Is there any fast way to find the largest power of 10 smaller than a given number?

I'm using this algorithm, at the moment, but something inside myself dies 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'm wondering if there is some bit magic for decimal numbers.

Wistful

What's wrong with this? It takes .0161 microseconds on average to perform 10**(int(math.log10(987654321987654321))), which is actually rather impressive. – Urbai

are we talking about integers or floats? – Liguria

The fastest algorithm is probably going to be dependent on the size of x. You'll probably want to profile a hybrid approach. – Rayfordrayle

In my case x is an integer, but I guess it shouldn't change that much (could cast a float x in an integral value and vice versa). – Wistful

my answer was faster than others theoretically, It's useful for big numbers not 10 digits. – Stalder

Answer 1

An alternative algorithm is:

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

Folksy

That's a terrible approach in terms of computational complexity. Your method is O(n) in terms of the number of bits, whereas O(log(n)) is sufficient. – Subaqueous

Everything is a tradeoff. For numbers with a finite range, O(n) could very well be just fine, and this option uses no additional space (compared with having a large lookup table, precomputing a sequence of squares, etc.). Computational complexity is not the be-all and end-all of whether an algorithm is "good" or not. It would be relatively straightforward to modify this to square instead of naive-multiply until it gets close, but that would involve more code and might, in fact, slow it down on smaller inputs. The right choice depends on the expected input data, not solely on big-O performance. – Folksy

it's better do it while((i = i * 10) < x); or while (i<x) i*=10; and count-- at the end. – Stalder

Computational complexity is not the be-all and end-all - sure, but in this case he's specifically asked for the fastest way... – Pewit

Most (all?) of the answers I got are a lot cheaper than my old code. This solution is the simplest one to be implemented, clean and really easy to be understood. I'm implementing this one since I think that for my average case (at the moment) it won't need to iterate more than 4 or 5 times, thus a fast O(n) solution should be ok; if I see it's not enough yet, I'll try and implement other algorithms as well. – Wistful

Answer 2

Log and power are expensive operations. If you want fast, you probably want to look up the IEEE binary exponent in table to get the approximate power of ten, and then check if the mantissa forces a change by +1 or not. This should be 3 or 4 integer machine instructions (alternatively O(1) with a pretty small constant).

Given tables:

  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 computation 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 might really need to write this as assembler to squeeze out every last clock.] [This code not tested.]

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

So, do you want fast, or do you want short-to-write?

EDIT 12/23: OP now tells us that his "x" is integral. Under the assumption that it is a 64 (or 32) bit integer, my proposal still works but obviously there isn't an "IEEE_Exponent". Most processors have a "find first one" instruction that will tell you the number of 0 bits on the left hand (most significant) part of the value, e.g., leading zeros; you likely This is in essence 64 (or 32) minus the power of two for the value. Given exponent = 64 - leadingzeros, you have the power of two exponent and most of the rest of the algorithm is essentially unchanged (Modifications left for the reader).

If the processor doesn't have a find-first-one instruction, then probably the best bet is a balanced discrimination tree to determine the power of ten. For 64 bits, such a tree would take at most 18 compares to determine the exponent (10^18 ~~ 2^64).

Parlay

No, I'm not doing that in python -this was supposed a language independent algorithm- just wanted to show my current algorithm in a couple of languages to make it clearer, bad idea, probably... – Wistful

Log and power are expensive operations. This is obviously the case in the absence of hardware support for transcendental operations. But, how slow are we talking on consumer grade general purpose CPU (modern x86, Power, x86_64...)? – Cateyed

If you don't want to use floating point, a similar integer scheme works by using a count-leading-zeros assembly instruction. – Outrun

@dmckee: Even with built in floating point, the transcendentals take some time execute. The chip vendors don't want to tell you precise clock counts on anything anymore but it is hard to believe you implement a high-precision floating point long in a few clocks. My scheme, being only few integer instructions (even the apparant floating compare can actually done with integer instructions because of how IEEE is defined!) seems likely hard to beat. Is this worth it? Probably not, unless the OP is doing just this repeatedly in an inner loop. But he didn't ask if it was worth the trouble :-} – Parlay

Nice solution! I'm not going to implement this now: it seems quite complicated, but I will, in case will need to optimize even more the solution I chose. – Wistful

Answer 3

Create an array of powers of 10. Search through it for the largest value smaller than x.

If x is fairly small, you may find that a linear search provides better performance than a binary search, due in part to fewer branch mis-predictions.

Adlai

Answer 4

The asymptotically fastest 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 to N's representation size. [The time bound is probably a bit worse because I simplified optimistically]

Note that I assumed arbitrarily large integers (watch out for overflow!), since the naive times-10-until-over algorithm is probably fast enough when dealing with just 32-bit integers.

Invisible

@Yonatan The indentation is intended. It keeps the contents of the iterator block to the right of the block delimiters. – Invisible

As for the previous solution, it's a nice one! I'm not going to implement this now: it seems quite complicated, but I will, in case will need to optimize even more the solution I chose. – Wistful

Answer 5

I think the fastest way is O(log(log(n))^2), the while loop takes O(log(log(n)) and it can be recursive call finite time (we can say O(c) where see 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)) and constant, because of 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);
    }

Stalder

Answer 6

In Python:

10**(len(str(int(x)))-1)

Outface

Answer 7

Given that this is language independent, if you can get the power of two that this number is significant to, eg y in x*2^y (which is the way the number is stored, though I'm not sure I have seen an easy way to access y in any language I have used) then if

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

(one floating point division)

10^z or 10^(z+1) will be your answer, though 10^z is still is not so simple (beg to be corrected).

Liguria

If you can get the power of two, you can simply look up z in table (my answer) at the cost of one memory access which is much cheaper than a float divide. – Parlay

Answer 8

I timed the methods with the following variations in C++ for the value a being a size_t type (inlining improves performance but does not change relative ordering).

Try 1: Multiply until find number.

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

Try 2: Multiway if (could also be programmed using a 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: Modified from findPow10 of @Saaed Amiri, which uses squaring to more rapidly find very large powers 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: Lookup table indexed using count leading zeros instruction as per @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 );
}

Timing is as follows (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

The lookup/multiway-if beats everything in C++, but requires we know integers are a finite size. try3 is slower than try1 in this test for smaller values of the loop end value, for large numbers try3 beats try1. In python things are made difficult because integers are not limited so I would combine try2 with try3 to quickly process numbers up to a fixed limit then handle the possibly very large numbers.

In python I think lookup using a list comprehension is probably faster than a multiway-if.

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

Inclusion

When you need to write code that starts to look like ASCII art of a sailboat, you should be asking yourself if you really need this kind of optimization. – Peden

Answer 9

Assuming inputs stay within uint64, here's an implementation via awk that's language-agnostic enough:

• the function is fully self-contained, loop-less, recursion-less , and POSIX-compliant

• the function has no hard coded values, but instead, via 4 temp variables,

  it generates all necessary thresholds on all the fly in order to perform binary search without any division or modulo ops

  • 1st group handles the very small cases [1, 10, 100, 1000]

  • 2nd group binary splits remaining 16 powers of 10 [10^4 - 10^19]

• the only external function call is input truncation via int(..)

• the function uses a bare handful of constructs - basic ops + * ++ += *= < <= | exponentiation (^)

  … and a WHOLE LOT of nested ternaries (-if- ? -then- : -else-)

---

jot 41 0 | gawk -Mbe '$++NF = 3^$1 - 2' | 

gawk -Mbe ' 

function largest_pow10_within(__, _4, _2, _1, _) {

    return \
    (__ = int(__)) < (_ *=  _2 = _ *= _1 = _ += (_ += ++_) + (_ += _)) \
        ? ((_ = _1) * __ <  _2 ? _^(_ <= __) : __ < (_ *= _2) ? _2 : _) \
        : __ < (_1 *= __ < (_2 *= __ < (__ < _ * (_ *= _4 = _) ? _ : _ = \
                    _4 * (_4 *= _)) ? _ = _4 : _) ? _ : _ = _2) ? _ : _1    
}'

---

1
    1
    1
2
    7
    1
3
    25
    10
4
    79
    10
5
    241
    100
6
    727
    100
7
    2185
    1000
8
    6559
    1000
9
    19681
    10000
10
    59047
    10000
11
    177145
    100000
12
    531439
    100000
13
    1594321
    1000000
14
    4782967
    1000000
15
    14348905
    10000000
16
    43046719
    10000000
17
    129140161
    100000000
18
    387420487
    100000000
19
    1162261465
    1000000000
20
    3486784399
    1000000000
21
    10460353201
    10000000000
22
    31381059607
    10000000000
23
    94143178825
    10000000000
24
    282429536479
    100000000000
25
    847288609441
    100000000000
26
    2541865828327
    1000000000000
27
    7625597484985
    1000000000000
28
    22876792454959
    10000000000000
29
    68630377364881
    10000000000000
30
    205891132094647
    100000000000000
31
    617673396283945
    100000000000000
32
    1853020188851839
    1000000000000000
33
    5559060566555521
    1000000000000000
34
    16677181699666567
    10000000000000000
35
    50031545098999705
    10000000000000000
36
    150094635296999119
    100000000000000000
37
    450283905890997361
    100000000000000000
38
    1350851717672992087
    1000000000000000000
39
    4052555153018976265
    1000000000000000000
40
    12157665459056928799
    10000000000000000000

Bathroom