[Python-Dev] int(string)

[Tim Peters]

[Tim]
...
>> int('102002022201221111211', 3) = 0

I should have added that all those examples simply used 2**32 as
input, expressed as a string in the input base.  They're not the only
failing cases; e.g., this is also obviously wrong:

>>> int('102002022201221111212', 3)
1

...

>> The challenge (should you decide to accept it <wink>) is to replace
>> the overflow-checking with something both correct _and_ much faster
>> than doing n integer divisions for an n-character input.  For example,
>> 36**6 < 2**32-1, so whenever the input has no more than 6 digits
>> overflow is impossible regardless of base and regardless of platform.
>> That's simple and exploitable.  For extra credit, make int(string) go
>> faster than preparing your taxes ;-)

|Michael Hudson]
> So, you're suggesting dividing the input up into known non-overflowing
> chunks and using the normal Python operations to combine those chunks,
> relying on them overflowing to longs as needed?

Possibly.  I want int(str), for the comparatively short decimal
strings most apps convert most of the time, to be much faster too. 
The _simplest_ thing one could do with the observation is add a
number-of-digits counter to PyOS_strtoul's loop, skip the overflow
check entirely for the first six digits converted, and for every digit
(if any) after the sixth do "obviously correct" overflow checking.

That would save min(len(s), 6) integer divisions per call, and would
probably be a real speed win for most apps that do a lot of
int(string).  Slightly more ambitious would be to use a different
constant per base; e.g., for base 10 overflow is impossible if there
are no more than 9 digits, and exploiting that would buy that
int(decimal_str) would almost never need to do an integer division in
most apps.

The strategy you suggest could, if implemented carefully, speed all
int(string) and long(string) operations, except for long(string, base)
where base is a power of 2 (the latter case is highly optimized
already, in longobject.c's long_from_binary_base).

Speeding long(string) for non-power-of-2 bases is tricky.  It benefits
already from the internal muladd1() routine, which does the "multiply
by the base and add in the next digit" step in one gulp, mutating the
C representation of a long directly.  That's a very efficient loop in
part because it _knows_ the base fits in a single "Python long digit".

Combining larger chunks _could_ be faster, but the multiplication
problem gets harder if base**chunk_size exceeds a single Python long
digit.

So there are a world of possible complications here.  I'd be delighted
to see "just" correct overflow checking plus a major speed boost for
int(decimal_string) where the result does fit in a 32-bit unsigned int
(which I'm sure accounts for the vast bulk of dynamic real-life
int(string) invocations).

> All of the examples you posted should have returned longs anyway, right?

On a 32-bit box, yes.  Regardless of box, all of the original examples
should return 2**32.  The one at the top of this message should return
2**32+1.

> I guess the change to automatically overflowing to longs has led to
> some code that shows its history more than one would like.

Well, these particular cases were always broken -- they always
returned 0.  The difference is that in modern Pythons they should
return the right answer, while in older Pythons they should have
raised OverflowError.