mpz_root aborts for n-th root when n is very large

[Marc Glisse]

On Sun, 27 Feb 2011, Torbjorn Granlund wrote:

> It is supposed to work (but the argument will overflow on a 32bit
> machine, or when using the 32bit ABI on a 64-bit machine).
>
> It should require at most a few dozed bytes, not 7312500040 words...

I just tried the following on a 64bit machine. Note that disabling alloca 
should help notice the issue.

#include <stdlib.h>
#include <stdio.h>
#include <gmp.h>

void* mymalloc(size_t s){
         fprintf(stderr,"malloc %zd\n",s);
         return malloc(s);
}
void* myrealloc(void*p,size_t old,size_t neu){
         fprintf(stderr,"realloc %zd %zd\n",old,neu);
         return realloc(p,neu);
}
void myfree(void*p,size_t s){
         fprintf(stderr,"free %zd\n",s);
         free(p);
}
int main(){
         mp_set_memory_functions(mymalloc,myrealloc,myfree);
         mpz_t out,in;
         mpz_init(out);
         mpz_init_set_ui(in,1);
         mpz_root(out,in,1000000000ul);
         return 0;
}


Running it prints:
malloc 8
malloc 8
malloc 73125040
malloc 73125040
free 73125040
free 73125040

and the function mpn_rootrem(_internal) indeed calls TMP_ALLOC_LIMBS with 
an argument linear in k.

-- 
Marc Glisse