FFT wrapper done

[Bill Hart]

I have now written a wrapper function in mul_fft_full.c which
multiplies two integers. It will fail if the product is too small to
use the FFT (there is an assert for this which hopefully will be on
during testing).

If I have done the calculations correctly it won't work if the product
of the two integers is less than about 4000 bits. But the assert gives
a more precise condition (which is complex).

The new test function is t-mul_fft_full.c.

I have also added fft_tuning.h (top level source directory of the
flint tree) and there are modifications to the top of mulmod_2expp1.c
where the tuning parameters were formerly recorded.

The only things remaining to be done now are efficient squaring code
and tuning code. I'll do at least one of those tomorrow. I'm sure you
can see from fft_tuning.h that tuning will be totally trivial and very
fast.

Bill.

[Cactus]

Bill's new FFT code is now fully integrated into the mpir-exp branch of the MPIR repository.

It passes all tests but it has not been properly tuned yet.

I have not stripped out the old FFT code and the old and new FFT can be compared by building MPIR with the define OLD_FFT set if timings for the old FFT are wanted.

[casevh]

I tried compiling the mpir-exp using configure.bat and make.bat. I
modified make.bat to compile and link the fft directory but I get the
following error message when I run 'make check'. I'm looking for
suggestions.

t-bswap.c
mpir.lib(mul_truncate_sqrt2.obj) : error LNK2019: unresolved external
symbol __gmpn_mulmod_2expp1_basecase referenced in
function __gmpn_mul_truncate_sqrt2
mpir.lib(mulmod_2expp1.obj) : error LNK2001: unresolved external
symbol __gmpn_mulmod_2expp1_basecase
mpir.lib(mulmod_2expp1.obj) : error LNK2001: unresolved external
symbol __gmpn_mulmod_2expp1_basecase
t-bswap.exe : fatal error LNK1120: 1 unresolved externals
ERROR

I also found one error in fft/mulmod_2expp1.c. The function
fft_mulmod_2expp1 is defined as 'void', but the function returned 0.

Case

[Cactus]

Thanks for trying this Case - I appreciate your efforts.

Unfortunately I don't use Jason's command line build but since it all works in Visual Studio, I would guess that it must be something missing in this build.  

If it is possible to check all the files that are compiled into the build, it would be worth checking that the file mulmod_2expp1_basecase.c is being included.  It has a name that has a long prefix that is the same as another file but I think the days when this would have been a problem are long passed.

Another clue may be that the missing symbol is internal to the library and is hence defined in gmp-impl.h rather than mpir.h - is the right version of gmp-impl.h being picked up when this file is compiled?

    Brian

[Case Van Horsen]

On Sun, Jan 15, 2012 at 10:34 AM, Cactus <riem...@gmail.com> wrote:
> Thanks for trying this Case - I appreciate your efforts.
>
> Unfortunately I don't use Jason's command line build but since it all works
> in Visual Studio, I would guess that it must be something missing in this
> build.
>
> If it is possible to check all the files that are compiled into the build,
> it would be worth checking that the file mulmod_2expp1_basecase.c is being
> included.  It has a name that has a long prefix that is the same as another
> file but I think the days when this would have been a problem are long
> passed.

I can't find mulmod_2expp1_basecase.c on either a Windows or Linux
checkout. Is the file possibly missing from SVN?

Case

>
> Another clue may be that the missing symbol is internal to the library and
> is hence defined in gmp-impl.h rather than mpir.h - is the right version of
> gmp-impl.h being picked up when this file is compiled?
>
>     Brian
>
>

> --
> You received this message because you are subscribed to the Google Groups
> "mpir-devel" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/mpir-devel/-/_nSqACWqfocJ.
>
> To post to this group, send email to mpir-...@googlegroups.com.
> To unsubscribe from this group, send email to
> mpir-devel+...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/mpir-devel?hl=en.

[Cactus]

You are right, the file is not in the SVN.

My apologies for this - I assumed that a file in the SVN could be renamed and would stay in the SVN but it doesn't seem so.

I've now uploaded it and corrected the other problem you found as well.   

   Brian

[Case Van Horsen]

Brian,

Much better. However, when I test, I get a failure in
fft_t-mul_truncate_sqrt2.exe. The only information I get from the
debugger is:

Unhandled exception at 0x000000013fd7257a in t-mul_truncate_sqrt2.exe:
0xC00000FD: Stack overflow.

The test fails when compiled with the VS2008 SDK and when compiled
with VS2010. I have attached the configure.bat and make.bat files I
used. The steps to recreate are:

cd mpir-exp\win
<<< replace existing .bat file with mine >>>
configure ABI=64
make
make check

Case

[Cactus]

Thanks Case - I can reproduce the problem and I will do some work on it with Bill and get a fix as soon as possible.

Is this the only test that fails?

    Brian

[Case Van Horsen]

I also get a failure on t-locale.c

t-locale.c
LIBCMT.lib(lconv.obj) : error LNK2005: localeconv already defined in
t-locale.obj
t-locale.exe : fatal error LNK1169: one or more multiply defined symbols found
ERROR

IIRC, that test fails on on quite a few systems so I wasn't too worried about.

>
> --
> You received this message because you are subscribed to the Google Groups
> "mpir-devel" group.
> To view this discussion on the web visit

> https://groups.google.com/d/msg/mpir-devel/-/wKc01kTkr2gJ.

[Case Van Horsen]

On Sun, Jan 15, 2012 at 3:38 PM, Case Van Horsen <cas...@gmail.com> wrote:
> On Sun, Jan 15, 2012 at 3:33 PM, Cactus <riem...@gmail.com> wrote:
>> Thanks Case - I can reproduce the problem and I will do some work on it with
>> Bill and get a fix as soon as possible.
>>
>> Is this the only test that fails?
>>
>>     Brian
>
> I also get a failure on t-locale.c
>
> t-locale.c
> LIBCMT.lib(lconv.obj) : error LNK2005: localeconv already defined in
> t-locale.obj
> t-locale.exe : fatal error LNK1169: one or more multiply defined symbols found
> ERROR

It does not fail on a VS2008 SDK build. Does the MSVC version check in
t-locale.c need to be updated?

[Cactus]

Bill found the problem with the FFT code and I have now uploaded the fix to the mpir-exp branch in the MPIR repository.  

This fixes the problem for me but I would be grateful if you could check it out.

Thanks for helping to test this branch.  

Do you have any applications that will exercise the MPIR-EXP 64-bit integer support on Windows x64?

    Brian

[Case Van Horsen]

On Mon, Jan 16, 2012 at 1:41 AM, Cactus <riem...@gmail.com> wrote:
> Bill found the problem with the FFT code and I have now uploaded the fix to
> the mpir-exp branch in the MPIR repository.
>
> This fixes the problem for me but I would be grateful if you could check it
> out.

Thanks for the quick fix. Tests pass on my machine.

>
> Thanks for helping to test this branch.
>
> Do you have any applications that will exercise the MPIR-EXP 64-bit integer
> support on Windows x64?

I will be using it with GMPY2.

Case
>
>     Brian

>
> --
> You received this message because you are subscribed to the Google Groups
> "mpir-devel" group.
> To view this discussion on the web visit

> https://groups.google.com/d/msg/mpir-devel/-/NO9B_zsFDt8J.

[smi...@gmail.com]

Aqqafa7+@$'_)#####*****************************************#aq*q*
Sent via BlackBerry from T-Mobile

[Cactus]

Thanks for the testing.  You are right - the t-locale.c test failure is not a major concern.

Has anyone tested a Linux build for the mpir-exp branch?

    Brian

[Jason]

This will need some configure work done first , I was just waiting for it to settle done a bit , I should have the time tonight

>
> Brian
>
>

[Cactus]

Thanks Jason,

Right now the source code files for the mpn_* routines provide the interface to the new FFT are in the fft subdirectory.  

Does this matter - should I move them to the mpn\generic subdirectory?

I don't expect these to be subject to assembler code overrides but there may be other reasons for putting them in mpn\generic that I am unaware of.

   Brian

[Jason]

yes , only files which may have asm overrides need to be in the mpn/generic , I think!

[Jason]

done it except for the new fft tuning . I had to change a minor bit about ULLONG_MAX in tests/t-constants.c as I dont think unix has these or if configure supports them , I'll check

[jason]

Tried running the stand alone fft-tune with FLINT_BITS=64 and even
with 3GB and swap space I cant tune the second param

/* fft_tuning.h -- autogenerated by tune-fft */

#ifndef FFT_TUNING_H
#define FFT_TUNING_H

#include "mpir.h"

#define FFT_TAB \
{ { 4, 3 }, { 4, 3 }, { 3, 2 }, { 2, 1 }, { 2, 1 } }

#define MULMOD_TAB \
{ Segmentation fault

It clearly uses too much memory

Jason

[Cactus]

Great work Jason!

I got quite a few of these out of memory issues in my testing of the new FFT. 

It probably occurs when one of the recursive FFT routines is entered with the length (n) set to zero, which causes an 'infinite' recursion.  This (n == 0) is not supposed to happen.

If you can send Bill a stack trace, he will perform magic on it and will, hopefully, come up with a fix (at least this is what he has been able to do for me).

    Brian

[Jason]

compiling mpir with --enable-assert we get this straight away

/* fft_tuning.h -- autogenerated by tune-fft */

#ifndef FFT_TUNING_H
#define FFT_TUNING_H

#include "mpir.h"

#define FFT_TAB \
{ { mulmod_2expp1_basecase.c:51: GNU MP assertion failed: !((xp) + (n) > (yp) && (yp) + (n) > (xp))
Aborted

which is a partial overlap of src and dst in the function

[Bill Hart]

The code was working ok in situ in flint so presumably the most recent bug fixes also need to be propagated to the tuning code as well.

If that doesn't lead to the source of the problem then check that the memory allocation, especially of tt is being done correctly.

Unfortunately I am not with my computer today so can't check that the tuning code still works in flint after the most recent bug fixes.

Bill.

[Cactus]

The FFT tuning appears to work in Windows but if I turn on asserts I see the same problem that Jason reported earlier. 

But I don't see the out of memory problem.

    Brian

[Jason]

with asserts on it fails make check anyway , so it's nothing to do with the tuning program , could be default
parameters for the fft or something else

[Jason]

like the other parameters or cutoff points , this was on a sandybridge

[Bill Hart]

OK, then we do need a trace of the function calls and the parameters
that are passed for the failing test. Brian is probably right. It's
probably an n=0 or trunc=2*n or trunc=0 passed somewhere, or
something like that. I'm glad I left the code so that it doesn't deal
with these cases, as it may shake some bugs out. It is very odd that
it fails on such a small example though.

Bill.