Re: How can I change the base in PARI (A12-140)

[Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr>]

On Fri, Feb 06, 2009 at 11:35:44AM +0100, ZerreZ wrote:
> Well, It's a floating number (the root).
> Anyway, if PARI can convert the number in less than an hour, that would be
> fair.
> I want to calculate the root in several bases and compare, but the actual
> calculation
> is quite heavy, so if base convertion could be done in reasonable time it
> would be
> much faster than recalculating in a different base.

I am sure it would, yes.

> The naive convertion algorithm is straight forward, so I think i can (with
> no PARI experience)
> implement it. Do you know of any none-quadratic algorithm for base
> convertion, when dealing
> with real numbers?

Sure, and it is implemented in GMP (and in PARI).
You need a non-quadratic Euclidean division.
The algorithm is as follow:
Let M be the number you want to convert.
Let b be the basis and 2*n such that b^(2*(n-1))<=M<b^(2n).
Write M as =Q*b^n+R and convert both Q and R in basis b
by calling this algorithm recursively. Then you just need
to concatenate the two results.

If your Euclidean division is subquadratic, then it can be shown to
be also subquadratic.

For a floating point g, you have to take care of the exponent before
converting the mantissa: if g=m*2^k, find u such that b^u is close to
2^k, and compute g*b^-u. This should be close from an integer that you
can convert to base b.

Cheers,
Bill.