What is wrong with my "digit finder" in python?

Question

I am learning python through the Project Euler problems. For problem 40 I wrote this code:

import math
i = 1
counter = 0
while counter <= 1000000:
    MMM = int(math.log(i, 10)) + 1
    counter = counter + MMM
    V = math.log(i, 10)
    print(i, counter, MMM, V)
    i += 1

It is supposed to return the number containing the Nth digit. Basically, this is supposed to keep track of what would happen if I concatenated the integers from 1 through whatever into another number. The goal is to determine what a specific digit is. This code works below a certain threshold, however, by the time it gets to the millionth digit it is off by one. What am I missing here? I have seen other implementations that save time, but I am more interested in why the count becomes wrong at some point

Edit:

replacing

MMM = int(math.log(i, 10)) + 1

with

MMM = len(str(i))

works like a champ!

Although it would be nice to have an all numeric solution, It'll have to wait until I can trust log functions in Python.

Answer 1

Floating point error somewhere along the way? It might be possible that at some point math.log is returning something that's barely less than (or greater, depending on the direction of your off-by-1 result) an integer boundary and thus int() is truncating it to the wrong value. Floating-point numbers are not precise for numbers which can't be represented using a certain number of binary digits.

Answer 2

I think this is the problem line

MMM = int(math.log(i, 10)) + 1

Some examples

>>> int(math.log(1000000, 10)) + 1
6
>>> int(math.log(1000001, 10)) + 1
7

Whereas I suspect you really wanted

>>> len(str(1000000))
7
>>> len(str(1000001))
7

Edit Actually (as you suggested!) math.log10 seems to be the best solution and more in line with what you wrote originally

>>> int(math.log10(10000000))
7
>>> int(math.log10(10000001))
7
>>> int(math.log10(10**1000))
1000
>>> int(math.log10(10**10000))
10000
>>> int(math.log10(10**100000))
100000

math.log10 must keep the accuracy better than math.log(x, 10)

Answer 3

Wow... I was not aware of this but...

>>> math.log(1000000, 10) 
5.9999999999999991 

>>> log10(1000000)
6.0

That's pretty depressing. :,( Is anybody aware of the most accurate common log in python?

Answer 4

The issue here is one of precision of floating point numbers which is not amazing. I gets fuzzier and fuzzier as the number of digits increase. This is the basic nature of floating point numbers, when you are doing this kind of math you need to be aware what precision you require.

The standard library module decimal allows you fine grained control of the precision of decimal values. Since this module is not hardware bases allows the user alter the precision of floating point number (the default is 28 places). You create decimal numbers like below:

 import decimal
 x = decimal.Decimal(1000000)
 x.log10()

You can alter the precision you require like this: decimal.getcontext().prec = 8