Best search algorithm to find condition within a range

BartC bc at freeuk.com
Wed Apr 8 23:22:49 CEST 2015


On 07/04/2015 23:57, Steven D'Aprano wrote:
> On Tue, 7 Apr 2015 07:44 pm, jonas.thornvall at gmail.com wrote:
>
>
>> I want todo faster baseconversion for very big bases like base 1 000 000,
>> so instead of adding up digits i search it.
>
> What digits would you use for base one-million?
>
> Base 2 uses 0 1.
> Base 3 uses 0 1 2.
> Base 10 uses 0 1 2 3 4 5 6 7 8 9.
> Base 16 uses 0 1 2 3 4 5 6 7 8 9 A B C D E F.
>
> Base one million uses what?
>
> How would you write down 12345 in base one-million?
>

That's only necessary when printing out the numbers as text (or reading 
them in). Even then, you don't need a million unique symbols; groups of 
letters or digits will do. The simplest way to represent a digit is 
write it out in normal base 10.

So the the number 3,012,345, in base 1000000, could represented in text 
form as the two 'digit':

  (3, 12345)

ie. 3*1000000 + 12345*1. In internal binary, each digit can just be 
stored in the normal form, probably as one digit per 32-bit integer.

(I have a big integer library that works exactly this way, using a 
decimal representation, but using base 1000000 with digits 0 to 999999, 
rather than base 10 and digits 0 to 9.)

-- 
Bartc





More information about the Python-list mailing list