|Bill Allombert on Fri, 06 Feb 2009 12:11:16 +0100|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|Re: How can I change the base in PARI (A12-140)|
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.