Best search algorithm to find condition within a range

[Ian Kelly]

On Tue, Apr 7, 2015 at 7:18 PM, Steven D'Aprano
<steve+comp.lang.python at pearwood.info> wrote:
> On Wed, 8 Apr 2015 10:38 am, Steven D'Aprano wrote:
>
>> On Wed, 8 Apr 2015 03:44 am, Ian Kelly wrote:
>>
>>>>>>
>>
> to_base(2932903594368438384328325832983294832483258958495845849584958458435439543858588435856958650865490,
>>>>>> 429496729)
>>> [27626525, 286159541, 134919277, 305018215, 329341598, 48181777,
>>> 79384857, 112868646, 221068759, 70871527, 416507001, 31]
>>
>>
>> They're not exactly *digits* though, are they?
>
> Oh, I forgot... I think this is why Python long ints effectively uses a base
> 256 internal storage. If memory serves me correctly, internally a long int
> is stored as an array of bytes using digits:
>
> \x0 \x1 \x2 ... \xFF
>
> (in decimal, 0 to 255). Each digit takes a single byte, so it's nicely
> compact, and Python includes a bunch of fast algorithms for doing
> arithmetic on these.

According to the comments in longintrepr.h, Python uses either 15- or
30-bit digits, determined at configure time.