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

["Karim Belabas" <Karim.Belabas@math.u-bordeaux1.fr>]

* 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]
`