|ZerreZ on Fri, 06 Feb 2009 11:37:28 +0100|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|Re: How can I change the base in PARI (A12-140)|
* ZerreZ [2009-02-06 10:40]:
> First of all, I'm sorry for creating a new thread instead of replying to myFirst of all, every single message that you sent to the list has been
> previous, but
> your anti-spam system is /really/ trying to get rid of me. It's blocking
> every message.
sent & seen twice, so maybe the system hasn't really been blocking anything ?
and see for yourself.
If I understand correctly, you want to convert a (huge) PARI integer to
> 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.
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;
v[i] = t;
1) depending on the PARI version you are using, you should add
my(t, N, v)
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
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]