On Wed, Apr 8, 2015 at 3:06 PM, Marko Rauhamaa <ma...@pacujo.net> wrote: > BartC <b...@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 -- https://mail.python.org/mailman/listinfo/python-list
