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.
