diff options
| author | MITSUNARI Shigeo <herumi@nifty.com> | 2019-03-07 10:02:43 +0800 |
|---|---|---|
| committer | MITSUNARI Shigeo <herumi@nifty.com> | 2019-03-07 10:02:43 +0800 |
| commit | ec765198b9e69a799ab923c17617ac41a05ff43f (patch) | |
| tree | 8802177d3d9f3ce5bc769546fe2bdcf1748be0d7 | |
| parent | da49e9158cc858d16f2277e39bd86c0c714ce30f (diff) | |
| download | dexon-mcl-ec765198b9e69a799ab923c17617ac41a05ff43f.tar.gz dexon-mcl-ec765198b9e69a799ab923c17617ac41a05ff43f.tar.zst dexon-mcl-ec765198b9e69a799ab923c17617ac41a05ff43f.zip | |
fast reduction accepts bls12-381 prime
| -rw-r--r-- | include/mcl/vint.hpp | 4 | ||||
| -rw-r--r-- | test/vint_test.cpp | 33 |
2 files changed, 35 insertions, 2 deletions
diff --git a/include/mcl/vint.hpp b/include/mcl/vint.hpp index f9e1859..83dd34d 100644 --- a/include/mcl/vint.hpp +++ b/include/mcl/vint.hpp @@ -619,8 +619,8 @@ void divNM(T *q, size_t qn, T *r, const T *x, size_t xn, const T *y, size_t yn) return; } assert(xTopBit > yTopBit); - // fast reduction for larger than fullbit-2 size p - if (yTopBit >= sizeof(T) * 8 - 3) { + // fast reduction for larger than fullbit-3 size p + if (yTopBit >= sizeof(T) * 8 - 4) { T *xx = (T*)CYBOZU_ALLOCA(sizeof(T) * xn); T qv = 0; if (yTopBit == sizeof(T) * 8 - 2) { diff --git a/test/vint_test.cpp b/test/vint_test.cpp index ca4cdbf..15e1426 100644 --- a/test/vint_test.cpp +++ b/test/vint_test.cpp @@ -6,6 +6,9 @@ #include <cybozu/benchmark.hpp> #include <cybozu/test.hpp> #include <cybozu/xorshift.hpp> +#ifndef DONT_USE_GMP_IN_TEST +#include <gmpxx.h> +#endif #define PUT(x) std::cout << #x "=" << x << std::endl; @@ -1232,6 +1235,36 @@ CYBOZU_TEST_AUTO(bench) CYBOZU_BENCH_C("sub", N, Vint::sub, z, x, y); CYBOZU_BENCH_C("mul", N, Vint::mul, z, x, y); CYBOZU_BENCH_C("div", N, Vint::div, y, z, x); + + const struct { + const char *x; + const char *y; + } tbl[] = { + { + "0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", + "0x2523648240000001ba344d8000000007ff9f800000000010a10000000000000d" + }, + { + "0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", + "0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab", + }, + { + "0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", + "0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001", + }, + + }; + for (size_t i = 0; i < CYBOZU_NUM_OF_ARRAY(tbl); i++) { + x.setStr(tbl[i].x); + y.setStr(tbl[i].y); + CYBOZU_BENCH_C("fast div", N, Vint::div, z, x, y); +#ifndef DONT_USE_GMP_IN_TEST + { + mpz_class mx(tbl[i].x), my(tbl[i].y), mz; + CYBOZU_BENCH_C("gmp", N, mpz_div, mz.get_mpz_t(), mx.get_mpz_t(), my.get_mpz_t()); + } +#endif + } } struct Seq { |