stack space in gcd operations

[David Harvey]

Hi,

I am having a problem with a threaded application using mpz_invert  
and running out of stack space on OS X. The default stack size for  
new threads on OSX is apparently only 512 KB, compared with 8 MB for  
linux (at least on the systems I tried).

The code below creates a new thread with the requested amount of  
stack space and attempts an n-limb mpz_invert operation. On OS X this  
fails (bus error) e.g. when the stack is 448 KB and n = 2800, but it  
works fine with a larger stack, even for much larger operands. This  
doesn't leave much room on the stack for the calling application.

(Note that I haven't checked directly whether the stack is  
overflowing; I tried to use -fstack-check but couldn't get it to  
work. The only evidence I have is which values of n and stack size  
cause the program below to crash.)

It is reasonable for GMP to require so much stack space for xgcd?

david

==========================================

#include <limits.h>
#include <stdio.h>
#include <gmp.h>
#include <pthread.h>


void*
worker (void* arg)
{
   size_t n = * (size_t*) arg;

   mpz_t a, b;
   mpz_init (a);
   mpz_init (b);

   /* try to invert a random number modulo B^n + 1 */
   mpz_random (a, n);
   mpz_set_ui (b, 1);
   mpz_mul_2exp (b, b, n * GMP_NUMB_BITS);
   mpz_add_ui (b, b, 1);
   mpz_invert (a, a, b);

   mpz_clear (b);
   mpz_clear (a);
}


int
main (int argc, char* argv[])
{
   if (argc < 3)
     {
       printf ("syntax: test <n> <stacksize>\n");
       return 0;
     }

   size_t n = atol (argv[1]);
   size_t old_stacksize;
   size_t new_stacksize = atol (argv[2]);

   pthread_attr_t attr;
   pthread_attr_init (&attr);

   pthread_attr_getstacksize (&attr, &old_stacksize);
   printf ("old stacksize = %ld\n", old_stacksize);

   int retval = pthread_attr_setstacksize (&attr, new_stacksize);
   if (retval != 0)
     {
       printf ("PTHREAD_STACK_MIN = %ld\n", PTHREAD_STACK_MIN);
       printf ("pthread_attr_setstacksize call failed with size = %ld 
\n",
               new_stacksize);
       return 0;
     }

   pthread_t thread;
   pthread_create (&thread, &attr, worker, &n);
   pthread_join (thread, NULL);

   pthread_attr_destroy (&attr);

   return 0;
}

==========================================