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.
