In fact from A = __GMP_ALLOCATE_FUNC_LIMBS (2 * K * (nprime + 1));
I surmise that for an FFT of length K with n' bits per coefficient, it requires 2*K*(n'+1) *bits*. Now K*n' should be 2 times the input bit size. So it is requesting 4 times the input bit size. It also allocates some pointers and a few other smaller bits and pieces. Bill. 2010/1/4 Bill Hart <goodwillh...@googlemail.com>: > If it is the latter then here is the relevant code: > > wsize = usize + vsize; > > ..... > > if (wp == up || wp == vp) > { > free_me = wp; > free_me_size = w->_mp_alloc; > } > else > (*__gmp_free_func) (wp, w->_mp_alloc * BYTES_PER_MP_LIMB); > > w->_mp_alloc = wsize; > wp = (mp_ptr) (*__gmp_allocate_func) (wsize * BYTES_PER_MP_LIMB); > w->_mp_d = wp; > > Which shows that the only things that can go wrong are: > > 1) BYTES_PER_MP_LIMB is not 4 > > or > > 2) something is wrong with __gmp_allocate_func > > The latter is given by the following code: > > void * (*__gmp_allocate_func) _PROTO ((size_t)) = __gmp_default_allocate; > > void * > __gmp_default_allocate (size_t size) > { > void *ret; > #ifdef DEBUG > size_t req_size = size; > size += 2 * BYTES_PER_MP_LIMB; > #endif > ret = malloc (size); > if (ret == 0) > { > fprintf (stderr, "GNU MP: Cannot allocate memory (size=%u)\n", size); > abort (); > } > .... > > which is where your message is coming from. But malloc is clearly > being fed the right value. > > To check if the temporary allocation made by the FFT is correct is > slightly more work.... > > Bill. > > 2010/1/4 Bill Hart <goodwillh...@googlemail.com>: >> This would be using the FFT. And the FFT should in theory require 4 >> times the input bit size in order to do the squaring. So to multiply >> integers of 2^31 bits, it will request 2^30 bytes of memory. This is >> all assuming that the FFT is written to use memory fairly efficiently. >> This is in addition to the amount of memory required for the input and >> output, which will be a total of 2^31 bits plus 2^32 bits. That makes >> a total of just below 8 times the input size, or 2^31 bytes. >> >> It's possible to reduce the FFT memory usage a little below that in >> theory, but not much. >> >> Or are you saying that the number of bytes allocated in the actual >> output mpz_t is the amount given there? >> >> Bill. >> >> 2010/1/4 Cactus <rieman...@googlemail.com>: >>> >>> >>> On Jan 4, 2:43 pm, Bill Hart <goodwillh...@googlemail.com> wrote: >>>> uintptr_t is a c99 feature. So it "exists" on linux, but formally only >>>> in c99 mode. I'm not keen to switch MPIR to c99. But we can define >>>> something in mpir.h which on Windows in uintptr_t and on linux is the >>>> same size as an mp_limb_t or whatever (I think it is the case that an >>>> mp_limb_t should always be the same size as a pointer on the systems >>>> we care about). >>> >>> If I square numbers of increasin sizes, I get the output: >>> >>> 26 134217724 >>> 27 268435456 >>> 28 536870911 >>> 29 1073741821 >>> 30 2147483645 >>> GNU MP: Cannot allocate memory (size=4294837280) >>> >>> The number on the left is log2(number of bits in the input), the >>> number on the right being the number of bits in the result. >>> >>> As can be seen it fails for 2^31 input bits because memory for 2^32 >>> _bytes_ cannot be allocated. >>> >>> So it is asking for a lot more memory than its should need. >>> >>> mpz_mul asks for memory through the call: >>> >>> void *_mpz_realloc (mpz_ptr m, mp_size_t new_alloc) >>> >>> and mp_size_t is defined to be an int in gmp-impl.h: >>> >>> typedef long int mp_size_t; >>> >>> This is 32-bits on Windows so the realloc call will fail as soon as >>> 2^32 bytes are asked for. >>> >>> The define: >>> >>> typedef size_t mp_size_t; >>> >>> would seem to be better here. >>> >>> But this doesn't explain the excess memory request. >>> >>> Brian >>> >>> -- >>> >>> You received this message because you are subscribed to the Google Groups >>> "mpir-devel" group. >>> To post to this group, send email to mpir-de...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> mpir-devel+unsubscr...@googlegroups.com. >>> For more options, visit this group at >>> http://groups.google.com/group/mpir-devel?hl=en. >>> >>> >>> >> > -- You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to mpir-de...@googlegroups.com. To unsubscribe from this group, send email to mpir-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en.