src/conv/add/czt/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:	66.7%	12 / 0 / 18

    src/conv/add/czt/lib.hpp
    
        Line
        Branch
        Exec
        Source
      
        #pragma once
      
        #include "../../../fps/czt/lib.hpp"
      
        #include "../../../math/qpow/basic/lib.hpp"
      
        #include "../../../nt/proot/uint/lib.hpp"
      
        namespace tifa_libs {
      
        template <class poly>
      
        159
        CEXP auto conv_czt(poly l, poly r, u32 ans_size = 0) NE {
      
          using mint = TPN poly::val_t;
      
          3/6auto tifa_libs::conv_czt<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >, unsigned int):
✓ Branch 0 taken 53 times.
✗ Branch 1 not taken.
auto tifa_libs::conv_czt<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, unsigned int):
✓ Branch 0 taken 53 times.
✗ Branch 1 not taken.
auto tifa_libs::conv_czt<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, unsigned int):
✓ Branch 0 taken 53 times.
✗ Branch 1 not taken.

        159
          if (!ans_size) ans_size = u32(l.size() + r.size() - 1);
      
          assert(mint::mod() <= u64(-1_u32));
      
        159
          cu32 m = (u32)mint::mod(), s = std::bit_ceil(u32(l.size() + r.size() - 1));
      
          3/6auto tifa_libs::conv_czt<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >, unsigned int):
✗ Branch 0 not taken.
✓ Branch 1 taken 53 times.
auto tifa_libs::conv_czt<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, unsigned int):
✗ Branch 0 not taken.
✓ Branch 1 taken 53 times.
auto tifa_libs::conv_czt<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, unsigned int):
✗ Branch 0 not taken.
✓ Branch 1 taken 53 times.

        159
          assert((m - 1) % s == 0);
      
        159
          const mint c = qpow(mint(proot(m)), (m - 1) / s);
      
        159
          l.resize(s), r.resize(s);
      
        159
          l = czt_fps(l, c), r = czt_fps(r, c);
      
          6/6auto tifa_libs::conv_czt<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >, unsigned int):
✓ Branch 3 taken 24709402 times.
✓ Branch 4 taken 53 times.
auto tifa_libs::conv_czt<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, unsigned int):
✓ Branch 3 taken 24709402 times.
✓ Branch 4 taken 53 times.
auto tifa_libs::conv_czt<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, unsigned int):
✓ Branch 3 taken 24709402 times.
✓ Branch 4 taken 53 times.

        74128365
          flt_ (u32, i, 0, s) l[i] *= r[i];
      
        159
          (l = czt_fps(l, c.inv())).resize(ans_size);
      
        159
          return l *= mint(s).inv();
      
        }
      
        }  // namespace tifa_libs

Line	Branch	Exec	Source
1			#pragma once
2
3			#include "../../../fps/czt/lib.hpp"
4			#include "../../../math/qpow/basic/lib.hpp"
5			#include "../../../nt/proot/uint/lib.hpp"
6
7			namespace tifa_libs {
8
9			template <class poly>
10		159	CEXP auto conv_czt(poly l, poly r, u32 ans_size = 0) NE {
11			using mint = TPN poly::val_t;
12	3/6 auto tifa_libs::conv_czt<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >, unsigned int): ✓ Branch 0 taken 53 times. ✗ Branch 1 not taken. auto tifa_libs::conv_czt<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, unsigned int): ✓ Branch 0 taken 53 times. ✗ Branch 1 not taken. auto tifa_libs::conv_czt<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, unsigned int): ✓ Branch 0 taken 53 times. ✗ Branch 1 not taken.	159	if (!ans_size) ans_size = u32(l.size() + r.size() - 1);
13			assert(mint::mod() <= u64(-1_u32));
14		159	cu32 m = (u32)mint::mod(), s = std::bit_ceil(u32(l.size() + r.size() - 1));
15	3/6 auto tifa_libs::conv_czt<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >, unsigned int): ✗ Branch 0 not taken. ✓ Branch 1 taken 53 times. auto tifa_libs::conv_czt<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, unsigned int): ✗ Branch 0 not taken. ✓ Branch 1 taken 53 times. auto tifa_libs::conv_czt<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, unsigned int): ✗ Branch 0 not taken. ✓ Branch 1 taken 53 times.	159	assert((m - 1) % s == 0);
16		159	const mint c = qpow(mint(proot(m)), (m - 1) / s);
17		159	l.resize(s), r.resize(s);
18		159	l = czt_fps(l, c), r = czt_fps(r, c);
19	6/6 auto tifa_libs::conv_czt<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >, unsigned int): ✓ Branch 3 taken 24709402 times. ✓ Branch 4 taken 53 times. auto tifa_libs::conv_czt<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, unsigned int): ✓ Branch 3 taken 24709402 times. ✓ Branch 4 taken 53 times. auto tifa_libs::conv_czt<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, unsigned int): ✓ Branch 3 taken 24709402 times. ✓ Branch 4 taken 53 times.	74128365	flt_ (u32, i, 0, s) l[i] *= r[i];
20		159	(l = czt_fps(l, c.inv())).resize(ans_size);
21		159	return l *= mint(s).inv();
22			}
23
24			} // namespace tifa_libs
25