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

[ZerreZ <zerrez@gmail.com>]

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. 

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?

By the way, thanks for the info about the mailing list. I will make sure not to resend this message 
if it appears on the list (even though it does not correspond with the "blocked" messages I get). 

For all it's worth: Thanks for your help so far K.B. :-)

On Fri, Feb 6, 2009 at 11:11 AM, Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr> wrote:

* ZerreZ [2009-02-06 10:40]:

> First of all, I'm sorry for creating a new thread instead of replying to my
> previous, but
> your anti-spam system is /really/ trying to get rid of me. It's blocking
> every message.

First of all, every single message that you sent to the list has been
sent & seen twice, so maybe the system hasn't really been blocking anything ?

Please check

 http://pari.math.u-bordeaux1.fr/archives/pari-users-0902/threads.html

and see for yourself.

> I am computing the roots of integer polynomials to high precision and I want
> to do this in several different bases.
> If PARI is using base 2^32 internally, it should be possible to change the
> output base?
>
> "high precision" means 10-100 million digits, so a manual base change would
> be /very/ slow.

If I understand correctly, you want to convert a (huge) PARI integer to
a (huge) vector of, say base 5, coefficients.

The simplest way to do it is to write a function such as

conv(N, B = 5) =
{
 v = vector(ceil(log(N)/log(B) + 1));
 for (i = 1, #v,
   t = divrem(N, B);
   N    = t[1];
   v[i] = t[2];
 ); v;
}

1) depending on the PARI version you are using, you should add

 my(t, N, v)

or

 local(t, N, v)

at the beginning to avoid overwriting global variables of the same names.

2) the above is optimized for clarity, not for speed; say 10 minutes to
convert a 1 million decimal digits integer to base 5.

One should really

- expand in base B^k, where k = floor( log(2^32) / log(B) ) is the largest
integer such that B^k < 2^32.  [ Replace 2^32 -> 2^64 if you run PARI on
a 64-bit architecture. ]

You will certainly be able to recover the properties you're looking for
in that new setting. Expect a speedup of a factor about k ( = 13 or 27
when converting to "base 5" )

- the correct algorithm to use is a divide & conquer strategy [ almost
linear, when the above is quadratic ]. A 10 to 30 minutes exercise, I
would say.

Cheers,

   K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`

-- 
Johan Brinch