src/conv/trans/ntt_doubling/lib.hpp - GCC Code Coverage Report

Directory:	./
Coverage:	low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%

	Coverage	Exec / Excl / Total
Lines:	100.0%	30 / 0 / 30
Functions:	100.0%	3 / 0 / 3
Branches:	62.5%	15 / 0 / 24

    src/conv/trans/ntt_doubling/lib.hpp
    
        Line
        Branch
        Exec
        Source
      
        #pragma once
      
        #include "../../../math/qpow/basic/lib.hpp"
      
        #include "../../../util/alias/others/lib.hpp"
      
        #include "../../../util/traits/math/lib.hpp"
      
        namespace tifa_libs {
      
        template <ntt_c NTT_t, std::same_as<TPN NTT_t::data_t> mint>
      
        1758
        CEXP void ntt_doubling(NTT_t CR ntt, vec<mint>& f, u32 n = 0) NE {
      
          3/6void tifa_libs::ntt_doubling<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > >, tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >&, unsigned int):
✗ Branch 0 not taken.
✓ Branch 1 taken 586 times.
void tifa_libs::ntt_doubling<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >&, unsigned int):
✗ Branch 0 not taken.
✓ Branch 1 taken 586 times.
void tifa_libs::ntt_doubling<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >&, unsigned int):
✗ Branch 0 not taken.
✓ Branch 1 taken 586 times.

        1758
          if (!n) n = (u32)f.size() / 2;
      
          6/12void tifa_libs::ntt_doubling<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > >, tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >&, unsigned int):
✓ Branch 1 taken 586 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 586 times.
✗ Branch 5 not taken.
void tifa_libs::ntt_doubling<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >&, unsigned int):
✓ Branch 1 taken 586 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 586 times.
✗ Branch 5 not taken.
void tifa_libs::ntt_doubling<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >&, unsigned int):
✓ Branch 1 taken 586 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 586 times.
✗ Branch 5 not taken.

        1758
          assert(std::has_single_bit(n) && f.size() >= n * 2);
      
        1758
          vec<mint> g(begin(f), begin(f) + n);
      
        1758
          ntt.dit(g);
      
        1758
          mint r = 1;
      
        1758
          const mint zeta = qpow(ntt.G, (mint::mod() - 1) / (n * 2));
      
          6/6void tifa_libs::ntt_doubling<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > >, tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >&, unsigned int):
✓ Branch 3 taken 56770956 times.
✓ Branch 4 taken 586 times.
void tifa_libs::ntt_doubling<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >&, unsigned int):
✓ Branch 3 taken 56770956 times.
✓ Branch 4 taken 586 times.
void tifa_libs::ntt_doubling<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >&, unsigned int):
✓ Branch 3 taken 56770956 times.
✓ Branch 4 taken 586 times.

        170314626
          flt_ (u32, i, 0, n) g[i] *= r, r *= zeta;
      
        1758
          ntt.dif(g), copy(g, begin(f) + n);
      
        1758
        }
      
        }  // namespace tifa_libs

Line	Branch	Exec	Source
1			#pragma once
2
3			#include "../../../math/qpow/basic/lib.hpp"
4			#include "../../../util/alias/others/lib.hpp"
5			#include "../../../util/traits/math/lib.hpp"
6
7			namespace tifa_libs {
8
9			template <ntt_c NTT_t, std::same_as<TPN NTT_t::data_t> mint>
10		1758	CEXP void ntt_doubling(NTT_t CR ntt, vec<mint>& f, u32 n = 0) NE {
11	3/6 void tifa_libs::ntt_doubling<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > >, tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >&, unsigned int): ✗ Branch 0 not taken. ✓ Branch 1 taken 586 times. void tifa_libs::ntt_doubling<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >&, unsigned int): ✗ Branch 0 not taken. ✓ Branch 1 taken 586 times. void tifa_libs::ntt_doubling<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >&, unsigned int): ✗ Branch 0 not taken. ✓ Branch 1 taken 586 times.	1758	if (!n) n = (u32)f.size() / 2;
12	6/12 void tifa_libs::ntt_doubling<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > >, tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >&, unsigned int): ✓ Branch 1 taken 586 times. ✗ Branch 2 not taken. ✓ Branch 4 taken 586 times. ✗ Branch 5 not taken. void tifa_libs::ntt_doubling<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >&, unsigned int): ✓ Branch 1 taken 586 times. ✗ Branch 2 not taken. ✓ Branch 4 taken 586 times. ✗ Branch 5 not taken. void tifa_libs::ntt_doubling<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >&, unsigned int): ✓ Branch 1 taken 586 times. ✗ Branch 2 not taken. ✓ Branch 4 taken 586 times. ✗ Branch 5 not taken.	1758	assert(std::has_single_bit(n) && f.size() >= n * 2);
13		1758	vec<mint> g(begin(f), begin(f) + n);
14		1758	ntt.dit(g);
15		1758	mint r = 1;
16		1758	const mint zeta = qpow(ntt.G, (mint::mod() - 1) / (n * 2));
17	6/6 void tifa_libs::ntt_doubling<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > >, tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > const&, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >&, unsigned int): ✓ Branch 3 taken 56770956 times. ✓ Branch 4 taken 586 times. void tifa_libs::ntt_doubling<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > const&, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >&, unsigned int): ✓ Branch 3 taken 56770956 times. ✓ Branch 4 taken 586 times. void tifa_libs::ntt_doubling<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >, tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > >(tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > const&, std::vector<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >, std::allocator<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >&, unsigned int): ✓ Branch 3 taken 56770956 times. ✓ Branch 4 taken 586 times.	170314626	flt_ (u32, i, 0, n) g[i] = r, r = zeta;
18		1758	ntt.dif(g), copy(g, begin(f) + n);
19		1758	}
20
21			} // namespace tifa_libs
22