Best search algorithm to find condition within a range

[Steven D'Aprano]

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.

If the array is always a multiple of four bytes, then that is logically
equivalent to using base 4294967296 with 32-bit digits:

\x0\x0\x0\x0 \x0\x0\x0\x1 \x0\x0\x0\x2 ... \xFF\xFF\xFF\xFF

(in decimal, 0 to 4294967295). It's still fundamentally binary though, but I
suppose it's not entirely pointless to talk about base 2**32 or base 2**64
numbers, in the context of a high-performance Big Num implementation. But
it wouldn't be practical to use *arbitrary bases* up to 2**32 or 2**64, and
it certainly isn't practical to have human beings read or write numbers in
such large bases. 


-- 
Steven