Re: seg fault in mpz_root

[Jason Moxham]

On Friday 13 Dec 2002 12:12 am, Kevin Ryde wrote:
> Jason Moxham <address@hidden> writes:
> > the fn mpn_rootrem , calculates an approx root which can be one unit too
> > large , and then it powers it to see if it is too large , if the approx
> > root is 3 , whereas the real root is 2 then after powering a lot more
> > space is required
>
> Ah, beaut.
>
> > 1) would to be allocate enough space for the worst case  eg (3/2)^k more
> > limbs
>
> Yes, better do that.  Can you come up with a good change for the 4.1.1
> code?
>

There is also the same problem with the initial approximation , I'll do a 
patch which allocates worst case memory(when needed)

> > ,assuming mpn_rootrem is only called when root>=2
>
> True currently I think.
>

I will check this

> > 2) identified these worst cases (these cases can be identified fairly
> > quickly(see my code for example)) and call a mpn_pow_1 which checks for
> > overflow
>
> That might be better for the future.  Unless we change to Paul Z.'s
> discrete variant, which if I understand it keeps intermediates below
> the true root.

Not too certain if Paul Z method will be very fast for large k (say >10) as

        It think it would be easy to extend, but no so efficient for large k.
        The reason is that at each step we have to compute k-1 terms of (a+b)^k
        [the main term was computed in the previous iteration, and the 2nd one
        by one division]. For large k computing these k-1 terms could even be
        slower than computing (a+b)^k directly. This is the reason why I first
        wanted to try k=3.
        
        For k=4 the best will probably to perform two square roots.
        
        Paul