Addressing single digits of big integers
Paul Zimmermann
Paul.Zimmermann at loria.fr
Mon Jul 28 13:38:02 CEST 2008
Rafael,
> Date: Thu, 24 Jul 2008 16:48:03 -0300
> From: "Rafael Anschau" <rafael.anschau at gmail.com>
>
> 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