Addressing single digits of big integers
Paul.Zimmermann at loria.fr
Mon Jul 28 13:38:02 CEST 2008
> 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 ?
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.
More information about the gmp-discuss