On Sun, Jan 3, 2010 at 12:33 PM, Cactus wrote:
>
>
> On Jan 3, 8:15 pm, Case Vanhorsen wrote:
>> Hello,
>>
>> I discovered an interesting memory allocation behavior on Windows vs.
>> Linux. I was testing GMPY on 64-bit Windows when I stumbled into this.
>> GMPY replaces the native MPIR memory all
I fixed my negacyclic convolution. I had to change two whole
characters to make it more efficient. It now beats MPIR from about
603684864 bits up. By the time we reach about 2GB it beats MPIR by
about 20-25%.
I'll post new times and code tomorrow. It does pass the test code,
which is a good sign.
Ah, I see that our current mpn_mulmod_2expp1 does not do anything
special at this stage.
So that is my number 3:
3. Make mpn_mulmod_2expp1 deal with the special case where you are
multiplying mod 2^{3B}+1 where B is some integer divisible by
GMP_LIMB_BITS.
Simply use the identity 2^{3B}+1 = (2^B
I've had a long think, and I don't think there is a way to get the FFT
to use the mpn_mulmod_2expm1 function for pointwise mults, no matter
what we do. I think it is fundamentally impossible.
That's completely bizarre to me.
And there is no such thing as an FFT in a Mersenne ring as I called
it.
On Jan 3, 8:58 pm, Bill Hart wrote:
> Not yet. It is just included in the svn as a file /new_fft.c.
>
> It probably won't work on Windows yet (the FFT_combine* and
> FFT_split*) functions need some ulongs replaced with mp_limb_t's and
> there is probably a fair amount of gnu extention/C99 stuff.
My mind does not keep up with my fingers typing. Of course my
suggestion 3 will not work because of this principal unit thing.
I'll need to give that whole part of the strategy some more thought.
I'm also now slightly confused as to why MPIR falls so far behind the
new code in the middle, then ca
Not yet. It is just included in the svn as a file /new_fft.c.
It probably won't work on Windows yet (the FFT_combine* and
FFT_split*) functions need some ulongs replaced with mp_limb_t's and
there is probably a fair amount of gnu extention/C99 stuff.
It's a standalone program at the moment. It is
On Jan 3, 8:45 pm, Bill Hart wrote:
> I've now committed the new code I mentioned to the repo. I didn't
> actually need to change anything to get the test code to pass after
> all! :-)
I'm connfused Bill - is this new code a part of MPIR?
If so what, if any, new files need to be added to the W
I've now committed the new code I mentioned to the repo. I didn't
actually need to change anything to get the test code to pass after
all! :-)
Bill.
2010/1/3 Bill Hart :
> 8. What remains to be done.
>
> Wow, I made it all the way to section 8! This is the most important
> section, where I descri
I've made the proposed improvement to lshift.asm the subject of trac
ticket #271.
At present issuing a release is being held up by me not setting up the
necessary infrastructure to fix our autotools installation, which is
broken. But I anticipate having it done in the next few weeks, as I
find the
I made both issues into trac tickets. See #269 and #270. One is a
blocker for MPIR 1.3 as it regards a serious bug by the looks of it.
Bill.
2010/1/3 Cactus :
>
>
> On Jan 3, 8:15 pm, Case Vanhorsen wrote:
>> Hello,
>>
>> I discovered an interesting memory allocation behavior on Windows vs.
>> L
On Jan 3, 8:15 pm, Case Vanhorsen wrote:
> Hello,
>
> I discovered an interesting memory allocation behavior on Windows vs.
> Linux. I was testing GMPY on 64-bit Windows when I stumbled into this.
> GMPY replaces the native MPIR memory allocation routines with Python's
> memory allocator. If I e
8. What remains to be done.
Wow, I made it all the way to section 8! This is the most important
section, where I describe what remains, in order to make this
implementation really fast, clean and worth switching out the existing
implementation in MPIR.
I'm very interested if people would like to
Hello,
I discovered an interesting memory allocation behavior on Windows vs.
Linux. I was testing GMPY on 64-bit Windows when I stumbled into this.
GMPY replaces the native MPIR memory allocation routines with Python's
memory allocator. If I enable debugging in GMPY, I get a trace of all
the memor
On Jan 3, 7:32 pm, techtech wrote:
> On Jan 3, 12:25 pm, Cactus wrote:
>
> > If you have a small example that fails to link, I will be happy to
> > have a look at it.
>
> > Brian
>
> Unfortunately my app depends on several third-party libraries like SDL
> and Boost. I'm stuck in the middle
On Jan 3, 12:25 pm, Cactus wrote:
> If you have a small example that fails to link, I will be happy to
> have a look at it.
>
> Brian
Unfortunately my app depends on several third-party libraries like SDL
and Boost. I'm stuck in the middle trying to guess which lib is truly
the cause of the
On Jan 3, 6:05 pm, Shawn Yarbrough wrote:
> On Sun, Jan 3, 2010 at 11:57 AM, Cactus wrote:
> > Do you need the C++ library?
>
> > Brian
>
> Yes, I'm statically linking with MPIR's C++ library, and I have all of
> MPIR's non-DLL projects using the same "Multi-threaded Debug DLL
> (/MDd)" setti
On Sun, Jan 3, 2010 at 11:57 AM, Cactus wrote:
> Do you need the C++ library?
>
> Brian
>
Yes, I'm statically linking with MPIR's C++ library, and I have all of
MPIR's non-DLL projects using the same "Multi-threaded Debug DLL
(/MDd)" setting for Runtime Library. Same as my application.
=Shawn
On Jan 3, 5:42 pm, techtech wrote:
> Can anyone tell me if MPIR works under Microsoft Visual Studio 2008
> with the "Multi-threaded Debug DLL (/MDd)" setting for Runtime
> Library?
>
> MPIR's projects for VS 2008 use the non-DLL setting of "Multi-threaded
> Debug (/MTd)". I can build the MPIR l
Can anyone tell me if MPIR works under Microsoft Visual Studio 2008
with the "Multi-threaded Debug DLL (/MDd)" setting for Runtime
Library?
MPIR's projects for VS 2008 use the non-DLL setting of "Multi-threaded
Debug (/MTd)". I can build the MPIR library itself successfully with
both settings.
T
5. References.
I am indebted to the people who prepared the following references:
"Matters Computational: ideas, algorithms and source code", by J org
Arndt, see http://www.jjj.de/fxt/fxtbook.pdf
Specifically I used chapter 3. Note that I took very great care to not
refer to the source code. I f
Hmm, so the only reason MPIR can be beating me for small
multiplications is general coding efficiency. My butterfly strategy
probably introduces overheads when the coefficients are small, i.e.
only a few limbs.
The overheads could be lowered by having an iterative FFT for short
lengths. But we sho
2010/1/3 David Harvey :
>
>
> On Jan 3, 9:03 am, Bill Hart wrote:
>
>> I figured I probably did misunderstand. What I think they are trying
>> to get at is that one can use coefficients modulo 2^N+1 except at
>> certain levels because the roots of unity are actually the same. But
>> then the discu
2010/1/3 David Harvey :
> See the recent discussion on the GMP list, for
> example the thread
>
> http://gmplib.org/list-archives/gmp-devel/2009-October/001053.html
Interesting discussion. Seems they've reached the same conclusions as
me regarding the "dyadic product" business. But I actually th
4. The strategy used.
I'll now describe the strategy I ended up settling on. But first some
notation to make this simpler.
Suppose I have a convolution length 2*n where n is a power of 2. A
standard Fermat transform with coefficients mod p = 2^{w*n}+1 can
support such a transform length. Here 2^w
2010/1/3 David Harvey :
>
>
> On Jan 3, 9:03 am, Bill Hart wrote:
>
>> I figured I probably did misunderstand. What I think they are trying
>> to get at is that one can use coefficients modulo 2^N+1 except at
>> certain levels because the roots of unity are actually the same. But
>> then the discu
On Jan 3, 9:03 am, Bill Hart wrote:
> I figured I probably did misunderstand. What I think they are trying
> to get at is that one can use coefficients modulo 2^N+1 except at
> certain levels because the roots of unity are actually the same. But
> then the discussion becomes one of combining a
2010/1/3 David Harvey :
>
> On Jan 2, 4:13 pm, Bill Hart wrote:
>
>> 2) The MPIR FFT uses both a Fermat FFT and a Mersenne FFT, i.e. it
>> does a multiplication of polynomials with coefficients mod p with p =
>> 2^{aN}+1 then one with coefficients mod p = 2^N-1. Then it CRT's the
>> results. By va
On Jan 2, 4:13 pm, Bill Hart wrote:
> 2) The MPIR FFT uses both a Fermat FFT and a Mersenne FFT, i.e. it
> does a multiplication of polynomials with coefficients mod p with p =
> 2^{aN}+1 then one with coefficients mod p = 2^N-1. Then it CRT's the
> results. By varying the parameter _a_, as well
29 matches
Mail list logo