Best search algorithm to find condition within a range

[Chris Kaynor]

On Wed, Apr 8, 2015 at 3:06 PM, Marko Rauhamaa <marko at pacujo.net> wrote:
> BartC <bc at freeuk.com>:
>
>> 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.)
>
> It is common to implement big integers in base-2**16, base-2**32 or
> base-2**64. Arithmetics is performed just like in elementary school.

While basically true, its not quite true: there are generally more
efficient but more complex algorithms for the computations than are
typically taught in school. For example, multiplication will often be
done with the Karatsuba algorithm, which is O(n^1.585)[1], rather than
long multiplication, which is O(n^2). Processors internally often use
shift-and-add, which is a variation on long multiplication, and is
fairly easy to implement in hardware for fixed-size integers.

[1] http://en.wikipedia.org/wiki/Karatsuba_algorithm