scipr-lab / libfqfft Goto Github PK

View Code? Open in Web Editor NEW

95.0 95.0 46.0 153 KB

C++ library for Fast Fourier Transforms in finite fields

License: Other

CMake 4.35% C++ 93.65% Gnuplot 2.00%

libfqfft's People

Contributors

Stargazers

Watchers

libfqfft's Issues

libprocps not available

I am trying to install libfqfft on a unix distribution that is not ubuntu. I am not able to compile anything without libprocps which is available only for ubuntu.
-- Checking for module 'libprocps'
-- No package 'libprocps' found
CMake Error at /gpfs/fs1/sfw/cmake/3.7.1/b1/share/cmake-3.7/Modules/FindPkgConfig.cmake:415 (message):
A required package was not found
Call Stack (most recent call first):
/gpfs/fs1/sfw/cmake/3.7.1/b1/share/cmake-3.7/Modules/FindPkgConfig.cmake:588 (_pkg_check_modules_internal)
CMakeLists.txt:63 (pkg_check_modules)

-- Configuring incomplete, errors occurred!
See also "/home/mvenkita/sources/libfqfft/CMakeFiles/CMakeOutput.log".

About the fields.

Hi,
I am trying to use FFT in the extension field, and I noticed that the field should implement some interfaces. I have a question, what does the member root_of_unity mean in libff::Double? Of which order?

Thanks.

Tests fail when configured with -DMULTICORE=ON

First of all, thank you for open sourcing your FFT library! :)

I configured and built libfqfft on Ubuntu 16.04.3 and MacOS X without multicore support and the make check tests pass!

However, when I configured and builtlibfqfft on Ubuntu 16.04.3 with -DMULTICORE=ON, all the tests seem to fail. (I couldn't build on OS X due to Apple's clang's dislike for -fopenmp.)

alinush@dvorak [~/repos/libfqfft/build-multicore] (master *%) $ make check
[  6%] Built target zm
[ 72%] Built target ff
[ 76%] Built target gtest
[ 80%] Built target gtest_main
[ 87%] Built target evaluation_domain_test
[ 93%] Built target polynomial_arithmetic_test
[100%] Built target kronecker_substitution_test
Test project /home/alinush/repos/libfqfft/build-multicore
    Start 1: evaluation_domain_test
1/3 Test #1: evaluation_domain_test ...........***Failed    0.04 sec
    Start 2: polynomial_arithmetic_test
2/3 Test #2: polynomial_arithmetic_test .......***Failed    0.00 sec
    Start 3: kronecker_substitution_test
3/3 Test #3: kronecker_substitution_test ......***Failed    0.00 sec

0% tests passed, 3 tests failed out of 3

Total Test time (real) =   0.05 sec

The following tests FAILED:
	  1 - evaluation_domain_test (Failed)
	  2 - polynomial_arithmetic_test (Failed)
	  3 - kronecker_substitution_test (Failed)
Errors while running CTest
CMakeFiles/check.dir/build.make:57: recipe for target 'CMakeFiles/check' failed
make[3]: *** [CMakeFiles/check] Error 8
CMakeFiles/Makefile2:103: recipe for target 'CMakeFiles/check.dir/all' failed
make[2]: *** [CMakeFiles/check.dir/all] Error 2
CMakeFiles/Makefile2:110: recipe for target 'CMakeFiles/check.dir/rule' failed
make[1]: *** [CMakeFiles/check.dir/rule] Error 2
Makefile:188: recipe for target 'check' failed
make: *** [check] Error 2

I'm sharing below the output of one of the tests called evaluation_domain_test:

Any help would be appreciated!

alinush@dvorak [~/repos/libfqfft/build-multicore] (master *%) $ libfqfft/evaluation_domain_test 
Running main() from gtest_main.cc
[==========] Running 10 tests from 2 test cases.
[----------] Global test environment set-up.
[----------] 5 tests from EvaluationDomainTest/0, where TypeParam = libff::Fp_model<5l, libff::mnt46_modulus_A>
[ RUN      ] EvaluationDomainTest/0.FFT
extended_radix2(): expected logm == FieldT::s + 1 - skipping
[       OK ] EvaluationDomainTest/0.FFT (48 ms)
[ RUN      ] EvaluationDomainTest/0.InverseFFTofFFT
extended_radix2(): expected logm == FieldT::s + 1 - skipping
[       OK ] EvaluationDomainTest/0.InverseFFTofFFT (26 ms)
[ RUN      ] EvaluationDomainTest/0.InverseCosetFFTofCosetFFT
extended_radix2(): expected logm == FieldT::s + 1 - skipping
[       OK ] EvaluationDomainTest/0.InverseCosetFFTofCosetFFT (15 ms)
[ RUN      ] EvaluationDomainTest/0.LagrangeCoefficients
8604239876081398105 == 8604239876081398105
6727725685108281804 == 6727725685108281804
6021529708918185102 == 6021529708918185102
-8672858129864896056 == -8672858129864896056
6127711232979806485 == 6127711232979806485
5607822086181446769 == 5607822086181446769
8710421400142519438 == 8710421400142519438
7354468502987514997 == 7354468502987514997
extended_radix2(): expected logm == FieldT::s + 1 - skipping
8604239876081398105 == 8604239876081398105
6021529708918185102 == 6021529708918185102
6127711232979806485 == 6127711232979806485
8710421400142519438 == 8710421400142519438
6727725685108281804 == 6727725685108281804
-8672858129864896056 == -8672858129864896056
5607822086181446769 == 5607822086181446769
7354468502987514997 == 7354468502987514997
7384186903335305300 == 7384186903335305300
7548044701675791237 == 7548044701675791237
-1544406568649535252 == -1544406568649535252
1215467308995890383 == 1215467308995890383
-4994999779324644556 == -4994999779324644556
3509618270083209309 == 3509618270083209309
5401195558141975678 == 5401195558141975678
3515209894566712929 == 3515209894566712929
-4953057286198132771 == -4953057286198132771
280 == 280
-4953057286198133680 == -4953057286198133680
1800 == 1800
-4953057286198134835 == -4953057286198134835
1512 == 1512
-4953057286198133365 == -4953057286198133365
120 == 120
[       OK ] EvaluationDomainTest/0.LagrangeCoefficients (30 ms)
[ RUN      ] EvaluationDomainTest/0.ComputeZ
extended_radix2(): expected logm == FieldT::s + 1 - skipping
[       OK ] EvaluationDomainTest/0.ComputeZ (0 ms)
[----------] 5 tests from EvaluationDomainTest/0 (119 ms total)

[----------] 5 tests from EvaluationDomainTest/1, where TypeParam = libff::Double
[ RUN      ] EvaluationDomainTest/1.FFT
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:68: Failure
Value of: e == a[i]
  Actual: false
Expected: true
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:68: Failure
Value of: e == a[i]
  Actual: false
Expected: true
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:68: Failure
Value of: e == a[i]
  Actual: false
Expected: true
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:68: Failure
Value of: e == a[i]
  Actual: false
Expected: true
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:68: Failure
Value of: e == a[i]
  Actual: false
Expected: true
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:68: Failure
Value of: e == a[i]
  Actual: false
Expected: true
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:68: Failure
Value of: e == a[i]
  Actual: false
Expected: true
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:68: Failure
Value of: e == a[i]
  Actual: false
Expected: true
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:68: Failure
Value of: e == a[i]
  Actual: false
Expected: true
expected m == 1ul<<log_m - skipping
[  FAILED  ] EvaluationDomainTest/1.FFT, where TypeParam = libff::Double (3 ms)
[ RUN      ] EvaluationDomainTest/1.InverseFFTofFFT
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:104: Failure
Value of: f[i] == a[i]
  Actual: false
Expected: true
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:104: Failure
Value of: f[i] == a[i]
  Actual: false
Expected: true
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:104: Failure
Value of: f[i] == a[i]
  Actual: false
Expected: true
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:104: Failure
Value of: f[i] == a[i]
  Actual: false
Expected: true
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:104: Failure
Value of: f[i] == a[i]
  Actual: false
Expected: true
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:104: Failure
Value of: f[i] == a[i]
  Actual: false
Expected: true
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:104: Failure
Value of: f[i] == a[i]
  Actual: false
Expected: true
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:104: Failure
Value of: f[i] == a[i]
  Actual: false
Expected: true
expected m == 1ul<<log_m - skipping
[  FAILED  ] EvaluationDomainTest/1.InverseFFTofFFT, where TypeParam = libff::Double (2 ms)
[ RUN      ] EvaluationDomainTest/1.InverseCosetFFTofCosetFFT
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:142: Failure
Value of: f[i] == a[i]
  Actual: false
Expected: true
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:142: Failure
Value of: f[i] == a[i]
  Actual: false
Expected: true
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:142: Failure
Value of: f[i] == a[i]
  Actual: false
Expected: true
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:142: Failure
Value of: f[i] == a[i]
  Actual: false
Expected: true
[  FAILED  ] EvaluationDomainTest/1.InverseCosetFFTofCosetFFT, where TypeParam = libff::Double (1 ms)
[ RUN      ] EvaluationDomainTest/1.LagrangeCoefficients
2223080 == 1388889
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:186: Failure
Value of: e == a[i]
  Actual: false
Expected: true
0 == -123762
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:186: Failure
Value of: e == a[i]
  Actual: false
Expected: true
-2071224 == -1136364
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:186: Failure
Value of: e == a[i]
  Actual: false
Expected: true
-9223372036854775808 == -123762
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:186: Failure
Value of: e == a[i]
  Actual: false
Expected: true
-4446160 == 1388889
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:186: Failure
Value of: e == a[i]
  Actual: false
Expected: true
-9223372036854775808 == -123762
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:186: Failure
Value of: e == a[i]
  Actual: false
Expected: true
3998131 == -1136364
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:186: Failure
Value of: e == a[i]
  Actual: false
Expected: true
0 == -123762
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:186: Failure
Value of: e == a[i]
  Actual: false
Expected: true
33791 == -10613
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:186: Failure
Value of: e == a[i]
  Actual: false
Expected: true
-30759 == 8684
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:186: Failure
Value of: e == a[i]
  Actual: false
Expected: true
-39104 == -10613
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:186: Failure
Value of: e == a[i]
  Actual: false
Expected: true
36517 == 8684
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:186: Failure
Value of: e == a[i]
  Actual: false
Expected: true
218 == 249
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:186: Failure
Value of: e == a[i]
  Actual: false
Expected: true
-243 == -107
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:186: Failure
Value of: e == a[i]
  Actual: false
Expected: true
-1139 == 249
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:186: Failure
Value of: e == a[i]
  Actual: false
Expected: true
719 == -107
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:186: Failure
Value of: e == a[i]
  Actual: false
Expected: true
2223080 == 278
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:186: Failure
Value of: e == a[i]
  Actual: false
Expected: true
-2334368 == -1032624
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:186: Failure
Value of: e == a[i]
  Actual: false
Expected: true
-3934949 == 1028508
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:186: Failure
Value of: e == a[i]
  Actual: false
Expected: true
3764694 == -619665
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:186: Failure
Value of: e == a[i]
  Actual: false
Expected: true
0 == -9223372036854775808
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:186: Failure
Value of: e == a[i]
  Actual: false
Expected: true
-9223372036854775808 == 0
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:186: Failure
Value of: e == a[i]
  Actual: false
Expected: true
-9223372036854775808 == -9223372036854775808
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:186: Failure
Value of: e == a[i]
  Actual: false
Expected: true
0 == 0
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:186: Failure
Value of: e == a[i]
  Actual: false
Expected: true
-1 == -1
2 == 2
-2 == -2
2 == 2
0 == 0
0 == 0
0 == 0
0 == 0
-36 == -36
280 == 280
-945 == -945
1800 == 1800
-2100 == -2100
1512 == 1512
-630 == -630
120 == 120
[  FAILED  ] EvaluationDomainTest/1.LagrangeCoefficients, where TypeParam = libff::Double (8 ms)
[ RUN      ] EvaluationDomainTest/1.ComputeZ
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:225: Failure
Value of: Z == a
  Actual: false
Expected: true
/home/alinush/repos/libfqfft/libfqfft/tests/evaluation_domain_test.cpp:225: Failure
Value of: Z == a
  Actual: false
Expected: true
[  FAILED  ] EvaluationDomainTest/1.ComputeZ, where TypeParam = libff::Double (17 ms)
[----------] 5 tests from EvaluationDomainTest/1 (31 ms total)

[----------] Global test environment tear-down
[==========] 10 tests from 2 test cases ran. (150 ms total)
[  PASSED  ] 5 tests.
[  FAILED  ] 5 tests, listed below:
[  FAILED  ] EvaluationDomainTest/1.FFT, where TypeParam = libff::Double
[  FAILED  ] EvaluationDomainTest/1.InverseFFTofFFT, where TypeParam = libff::Double
[  FAILED  ] EvaluationDomainTest/1.InverseCosetFFTofCosetFFT, where TypeParam = libff::Double
[  FAILED  ] EvaluationDomainTest/1.LagrangeCoefficients, where TypeParam = libff::Double
[  FAILED  ] EvaluationDomainTest/1.ComputeZ, where TypeParam = libff::Double

 5 FAILED TESTS

Cannot checkout source code on Windows

Some filenames have characters in their names which are reserved/illegal on the Windows platform.

e.g. https://github.com/scipr-lab/libfqfft/blob/master/libfqfft/profiling/logs/memory/02-19_03:18/memory.ps

Is it necessary for these files to be in the repository (I assume they're log files which were committed by accident?), if not - removing them will make it easier to build this library on Windows.

basic radix 2 coset IFFT: combine multiply by coset and multiply by constant

For a coset of size L, the coset IFFT does an extra L multiplications at the moment (in exchange for better abstraction)

The basic radix 2 coset IFFT does the normal IFFT, and then multiplies the coefficients of the polynomial by powers of the coset offset. The normal IFFT at the end multiplies every element of the polynomial by a constant. These multiplications can be merged.

The multiply by coset procedure essentially computes offset, offset^2, offset^3 ..., by just multiplying the previous term by offset. In the coset IFFT, you really want to compute k*offset, k*offset^2, ..., which can be done by just multiplying the first term by the constant, and then proceeding as before.

run `make` only compile zm and libff, then exit

pls fix~

Recommend Projects

React

A declarative, efficient, and flexible JavaScript library for building user interfaces.
Vue.js

🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript

TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
TensorFlow

An Open Source Machine Learning Framework for Everyone
Django

The Web framework for perfectionists with deadlines.
Laravel

A PHP framework for web artisans
D3

Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

javascript

JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
web

Some thing interesting about web. New door for the world.
server

A server is a program made to process requests and deliver data to clients.
Machine learning

Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Visualization

Some thing interesting about visualization, use data art
Game

Some thing interesting about game, make everyone happy.

Recommend Org

Facebook

We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft

Open source projects and samples from Microsoft.
Google

Google ❤️ Open Source for everyone.
Alibaba

Alibaba Open Source for everyone
D3

Data-Driven Documents codes.
Tencent

China tencent open source team.