Addressing single digits of big integers

Paul Zimmermann Paul.Zimmermann at
Mon Jul 28 13:38:02 CEST 2008


> Date: Thu, 24 Jul 2008 16:48:03 -0300
> From: "Rafael Anschau" <rafael.anschau at>
> Is it possible to address single digits in big integers, without the high
> costs of export import ? Something like a pointer to the digit ?
> Thanks.
> Rafael

from a theoretical point of view, as far as I know, the complexity of computing
a single digit (say the middle one) in a base that is not commensurable to the
internal base (for example in base 10 when numbers are represented in radix 2)
is the same as converting the whole number, i.e., O(n log n).

Now if you mean digits in base say 16 or 256, that are commensurable to 2, you
can access them directly using the mpn layer.

Paul Zimmermann

More information about the gmp-discuss mailing list