Math/Convolution

[key-moon]

No description provided.

[terry-u16]

C++版のconvolutionは以下のような関数定義になっています。

// 1. modをテンプレート引数で受け取り、T型のvectorについて畳み込みを行う。Tはint, uint, ll, ull。
vector<T> convolution<int m = 998244353>(const vector<T>& a, const vector<T>& b)

// 2. static_modint型のvectorについて畳み込みを行う。引数はコピーされるため、呼び出し側のvectorは変更されない。
vector<static_modint<m>> convolution<int m>(vector<static_modint<m>> a, vector<static_modint<m>> b)

// 3. ll型のvectorについて、modを取らず畳み込みを行う。
vector<ll> convolution_ll(const vector<ll>& a, const vector<ll>& b)

これをできる限り踏襲すると、C#版に移植するなら以下のようなインターフェースが考えられるかなと思っています。
（INumOperatorについては #33 を、 C#版のmodintに関しては #12 および #46 を参照。）

// 1. int, uint, long, ulong に対応させるため INumOperator<T> を使用。modを引数で受け取り、内部でDynamicModInt<T>を使う。
//    利用しやすいよう、別途int, uint, long, ulong版のオーバーロードを作成してラップする。
TValue[] Convoluton<TValue, TOp>(ReadOnlySpan<TValue> a, ReadOnlySpan<TValue> b, int mod)
    where TValue : struct
    where TOp : struct, INumOperator<TValue> { }

// 2. StaticModInt<T>のSpanを受け取る。C++に合わせ、内部でa, bをコピーしてから計算。
StaticModInt<T>[] Convolution<T>(ReadOnlySpan<StaticModInt<T>> a, ReadOnlySpan<StaticModInt<T>> b) 
    where T : struct, IStaticMod { }

// 3. C++版の通り。
long[] ConvolutionLong(ReadOnlySpan<long> a, ReadOnlySpan<long> b) { }

2.と3.についてはC++版とほとんど変わりません。2.でmodをテンプレート引数で受け取るか、IStaticModとして受け取るかの違いのみです。
問題は1.なのですが、テンプレート引数で手軽にmodが渡せない以上、基本的には引数で渡すことになるかと思います。
引数渡しの場合コンパイル時にmodが決まらないため、内部ではDynamicModIntとして計算することとなり、

• modをコンパイル時定数として扱うことができず、パフォーマンスが落ちる
• StaticModInt版とDynamicModInt版の両方でバタフライ演算を実装する必要があるのがつらい
  • INumOperator的なものを新たに定義するのもそれはそれでつらい

あたりがちょっと辛いところです。

TValue[] Convoluton<TValue, TOp, TMod>(ReadOnlySpan<TValue> a, ReadOnlySpan<TValue> b)
    where TValue : struct
    where TOp : struct, INumOperator<TValue>
    where TMod : struct, IStaticMod{ }

のようにすれば解決するのですが、C++では1.が「modintのことを知らずとも使える」というメリットを持っている以上、そこをスポイルするのは微妙な気もしています……。

何かご意見頂ければ嬉しいです……！

[terry-u16]

冷静に考えると、1.はmodintの配列に流し込んで2.にパスするだけなので、INumOperatorは不要（各オーバーロードで流し込めば良い）な気がしてきました。

とはいえmod周りの問題についてはまだ残っているので悩んでいます。いっそ1.をなくしてしまっても良いような気もしますが……。

[takytank]

DynamicModInt が StaticModInt にパフォーマンスで劣るのと同じように、1.に関してはパフォーマンスに目をつむって中身をDynamicModIntで実装するのが、一番使いやすく元のC++コードにも近くなるのかなと思います。

[terry-u16]

ありがとうございます……！内部実装はともかく、インターフェース部分はC++版に合わせたいですね。
#48 でConvolutionのインターフェース部分を作成してみましたが、いかがでしょうか……？

[key-moon]

1. についても、以下のように IStaticMod を型引数として渡す実装でも問題ないのではないでしょうか?

public static ulong[] Convolution<TMod>(ulong[] a, ulong[] b)
    where TMod : struct, IStaticMod
    => throw new NotImplementedException();

C++のModintを知らなくても使えるという制約については、恐らくテンプレート引数は知っているが演算子のオーバーロードあたりを知らない、という層を想定していると思います。そのため、このような実装ならば十分な知識量で対応できると感じます。
デフォルト型引数(<int m = 998244353>) については

public static ulong[] Convolution(ulong[] a, ulong[] b)
    where TMod : struct, IStaticMod
    => Convolution<Mod998244353>(a, b);

のような実装をすれば解決するはずです。

[key-moon]

DynamicModInt が StaticModInt にパフォーマンスで劣るのと同じように、1.に関してはパフォーマンスに目をつむって中身をDynamicModIntで実装するのが、一番使いやすく元のC++コードにも近くなるのかなと思います。

DynamicModInt と StaticModInt は C++ でも同様の定数倍の問題が発生していますが、C++ の convolution でこれは発生しないため、できるならばノーコストでやりたいという思いがあります。

[terry-u16]

確かに型引数として渡すだけであれば特に難解でもないですね。
またデフォルト型引数については正直あまり考えていませんでした。その方法で投げてあげるのが良さそうです。

こちらの方針で修正してみます。どうもありがとうございました……！ #48

[terry-u16]

インターフェース部分を修正しました。 #48
並行して実装の方も進めていきます。