投稿2

290

$ $
$ $
$ $
この記事はぜんぜん数学的に厳密ではありません　ゆるして　　(ふい字Pをダウンロードしているとこの文字がふい字Pで表示されるよ！) 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

$\quad$投稿2

$\quad$MZVの具体値とか求めるアプリいる？
$\quad$ってきいたら作って欲しいといわれたので作りました。
$\quad$…
$\quad$という前回の記事はこちら→ 初投稿

$\quad$プログラムの数学

$\quad$ mathlogのコミュニティガイドライン
$\quad$を読んできたのですが、実は結構震えています。
$\quad$数学として、プログラムの話をしてもよいのでしょうか。
$\quad$どう考えてもさすがにそれはまずいので、計算量の話をしますが、
$\quad$それでもここで話す内容ではないのではと考えてしまいます。
$\quad$Mathlog で投稿可能な内容として次のようなものがあります。

物理学やコンピュータサイエンス、経済学などの数学の応用先となる分野の内容*
*$\\$運営としては、物理やコンピューターサイエンスなどの数学を応用した内容によって、数学に対する見方が変わる人や数学を学ぶきっかけになる人も多くいると考えております。そのため、数学を応用した分野の内容も投稿可能としています。

$\quad$とあるので、少しだけ安心しました。

$\quad$本題

$\quad$まず前回の定義をばばば

定義1　Multiple Zeta Value(limited)

\begin{eqnarray} \zeta_{a}^{p}(s_1,s_2,\dots,s_r) := \sum_{{\color{red} {\large a}} <n_1<n_2< \dots <n_r< {\color{red} {\large p+r}}} n_1^{-s_1}n_2^{-s_2} \dots n_r^{-s_r} \qquad(a<p) \end{eqnarray}

$\quad$ここはmathlogなので、計算量の話をします。

$\quad$前回のおさらい

\begin{eqnarray} \zeta_{a}^{p}(s_1,s_2,\dots,s_r)-\zeta_{a+1}^{p}(s_1,s_2,\dots,s_r)={(a+1)^{-s_1}}\zeta_{a+1}^{p+1}(s_2,s_3,\dots,s_r) \end{eqnarray}

$\quad$こんな公式を導いていました↑↑（テトレーションじゃないよ）

$\quad$結局これどう使うの？

$\quad$導いたとしてこれをどう使うのでしょうか？
$\quad$よく公式を見てみましょう

\begin{eqnarray} \zeta_{a}^{p}(s_1,s_2,\dots,s_r)-\zeta_{a+1}^{p}(s_1,s_2,\dots,s_r)={(a+1)^{-s_1}}\zeta_{a+1}^{p+1}(s_2,s_3,\dots,s_r) \end{eqnarray}
イコールの左と右で何が違うのでしょうか？
（私は左利きです）
重要なことに気づきました。

右辺のゼータの変数が減っている！！！！

ということは？
これを上手に使えば変数を一つにまで減らせる????
具体的に行動してみましょう！$a=0,p=5,r=3$です
\begin{eqnarray}\\ \color{#f50}\zeta_{0}^{5}(s_1,s_2,s_3)-\color{#f9f}\zeta_{1}^{5}(s_1,s_2,s_3)&=&{1^{-s_1}}\color{#99f}\zeta_{1}^{6}(s_2,s_3) \\\\\color{#99f} \zeta_{1}^{6}(s_2,s_3)-\color{#9ff}\zeta_{2}^{6}(s_2,s_3)&=&{2^{-s_2}}\zeta_{2}^{7}(s_3) \end{eqnarray}

ちょっと待って

$\zeta_{2}^{7}(s_3)$はいいとして、
$\color{#f9f}\zeta_{1}^{5}(s_1,s_2,s_3)$とか$\color{#9ff}\zeta_{2}^{6}(s_2,s_3)$ってどうやって求めるんですか？
\begin{eqnarray} \zeta_2^7(s_3)= 3^{-s_3}+4^{-s_3}+5^{-s_3}+6^{-s_3}+7^{-s_3} \end{eqnarray}
は求められますね
$\color{#f9f}\zeta_{1}^{5}(s_1,s_2,s_3)$ですが、これも上記のようにすればいいんじゃないですか???
つまり、
\begin{eqnarray}\\ \color{#f9f}\zeta_{1}^{5}(s_1,s_2,s_3)&-&\color{#fc7}\zeta_{2}^{5}(s_1,s_2,s_3)&=&{2^{-s_1}}\color{#9ff}\zeta_{2}^{6}(s_2,s_3) \\\\\color{#9ff} \zeta_{2}^{6}(s_2,s_3) &-&\color{#09f}\zeta_{3}^{6}(s_2,s_3) &=&{3^{-s_2}}\zeta_{3}^{7}(s_3) \end{eqnarray}
この$\color{#fc7}\zeta_{2}^{5}(s_1,s_2,s_3)$と$\color{#09f}\zeta_{3}^{6}(s_2,s_3)$も同じことすればいいんじゃないですか???
\begin{eqnarray}\\ \color{#fc7}\zeta_{2}^{5}(s_1,s_2,s_3)&-&\color{#f90}\zeta_{3}^{5}(s_1,s_2,s_3)&=&{2^{-s_1}}\color{#09f}\zeta_{3}^{6}(s_2,s_3) \\\\\color{#09f} \zeta_{3}^{6}(s_2,s_3) &-&\color{#0f9}\zeta_{4}^{6}(s_2,s_3) &=&{3^{-s_2}}\zeta_{3}^{7}(s_3) \end{eqnarray}
うわ、ぐちゃぐちゃになってきました。もうちょっと綺麗に図にしたいですね。どうしようかな、綺麗に図を描けるやつとかあったかな､､､

\begin{xy} \xymatrix { \zeta_{0}^{5}(s_1,s_2,s_3) &\zeta_{1}^{5}(s_1,s_2,s_3) \ar@//[l] & 1^{-s_1} \zeta_{1}^{6}(s_2,s_3) \ar@//[l] &\zeta_{1}^{6}(s_2,s_3) \ar@{.>}[l] &\zeta_{2}^{6}(s_2,s_3) \ar@//[l] & 2^{-s_2}\zeta_{2}^{7}(s_3) \ar@//[l] &\zeta_{2}^{7}(s_3) \ar@{.>}[l] \\ \zeta_{1}^{5}(s_1,s_2,s_3) \ar@//[ur] &\zeta_{2}^{5}(s_1,s_2,s_3) \ar@//[l] &2^{-s_1} \zeta_{2}^{6}(s_2,s_3) \ar@//[l] &\zeta_{2}^{6}(s_2,s_3) \ar@{.>}[l] \ar@//[ur] &\zeta_{3}^{6}(s_2,s_3) \ar@//[l] &3^{-s_2}\zeta_{3}^{7}(s_3) \ar@//[l] &\zeta_{3}^{7}(s_3) \ar@{.>}[l] \ar@/_/[u] \\ \zeta_{2}^{5}(s_1,s_2,s_3) \ar@//[ur] &\zeta_{3}^{5}(s_1,s_2,s_3) \ar@//[l] &3^{-s_1} \zeta_{3}^{6}(s_2,s_3) \ar@//[l] &\zeta_{3}^{6}(s_2,s_3) \ar@{.>}[l] \ar@//[ur] &\zeta_{4}^{6}(s_2,s_3) \ar@//[l] &4^{-s_2}\zeta_{4}^{7}(s_3) \ar@//[l] &\zeta_{4}^{7}(s_3) \ar@{.>}[l] \ar@/_/[u] \\ \zeta_{3}^{5}(s_1,s_2,s_3) \ar@//[ur] &\zeta_{4}^{5}(s_1,s_2,s_3) \ar@//[l] &4^{-s_1} \zeta_{4}^{6}(s_2,s_3) \ar@//[l] &\zeta_{4}^{6}(s_2,s_3) \ar@{.>}[l] \ar@//[ur] &\zeta_{5}^{6}(s_2,s_3) \ar@//[l] &5^{-s_2}\zeta_{5}^{7}(s_3) \ar@//[l] &\zeta_{5}^{7}(s_3) \ar@{.>}[l] \ar@/_/[u] } \end{xy}

ありましたねxymatrixが。
上のような感じで綺麗に書けました。(矢印を白くできなかったので文字は黒、背景は#9aaにしています)

さて、一番右のやつらは計算できますし、計算するときに一つ下で計算した値を使いまわせますね。
例
\begin{eqnarray} \zeta_2^7(s_3) &=& 3^{-s_3}+4^{-s_3}+5^{-s_3}+6^{-s_3}+7^{-s_3} \\ \zeta_3^7(s_3) &=& 4^{-s_3}+5^{-s_3}+6^{-s_3}+7^{-s_3} \\ \therefore　\zeta_2^7(s_3) &=& 3^{-s_3}+\zeta_3^7(s_3) \end{eqnarray}

じゃぁ、$\zeta_{4}^{5}(s_1,s_2,s_3)$や、$\zeta_{5}^{6}(s_2,s_3)$はどうやって求めるの？
これはもう、定義に沿った方が早いです。

定義より、
\begin{eqnarray} \zeta_{4}^{5}(s_1,s_2,s_3)　&=& \sum_{4 < n_1< n_2< n_3< 5+3} n_1^{-s_1}n_2^{-s_2} n_3^{-s_3} \\ &=& 5^{-s_1} + 6^{-s_2} + 7^{-s_3} \\ \zeta_{5}^{6}(s_2,s_3)　&=& \sum_{5 < n_1< n_2< 6+2} n_1^{-s_2} n_2^{-s_3} \\ &=& 6^{-s_2} + 7^{-s_3} \\ \end{eqnarray}
あれ、これも計算結果を使いまわせますね。
\begin{eqnarray} \zeta_{4}^{5}(s_1,s_2,s_3)　&=& 5^{-s_1} + \zeta_{5}^{6}(s_2,s_3) \end{eqnarray}
これで、矢印を上手に辿って戻ることで、$\zeta_{0}^{5}(s_1,s_2,s_3)$を求めることができます！！！！

$\quad$肝心の計算量は？

では、もとめられると分かったとして、結局これの計算量はどのぐらいになっているのでしょうか???
$p$と$r$が上の図でどこに当たるのかですが、縦の大きさは$p-1$行、横は$r$列あるように見えますね(点線の矢印で区切ると3つのセクションに分かれる)
と、いうことは、、、、、、、、、、、、、、、、、、、、、

いうことは、、、、、、、、、、、、、、、、、

、、、、、、、、、、、、、、、、

、、、、、、、、

、、、、

、、

、

あれ、

計算量$\mathcal{O}( p \cdot r)$では????????

前の記事を思い出してみてください。

で、計算量はどのくらいになるのかというのを見積もると、超大雑把にみて$\mathcal{O}(p^r)$くらいかなぁと考えました。
(javascriptの四則演算の計算量のオーダーがはっきりとしないので、
ここでいう計算量はループの数ということにして、計算量を比較していきます。)
ここで、$p$と$r$は$\zeta_a^p(s_1,s_2,…,s_r)$から来ています。
実用的には$p$のほうが$r$よりもずっと大きく設定するので、これでいいでしょう。
これ、指数レベルのオーダーなので、多変数&精度を求められると、計算時間が爆発してしまいます。
さて、$\mathcal{O}(p^r)$というのは、ループの数のオーダーなのですが、
これをいかにして減らすのでしょうか？？？？？？？

あれ、指数時間でしたね。ということは？

指数時間→多項式時間

＼＼\\指数時間→多項式時間//／／

$\quad$実装

理論の構築は完璧にできましたが実装ではまぁその後も色々ありまして､､､
例えばどう言う計算の順序で処理するべきかとか、(要素数$p$の配列を作って右から順に計算することにしました。
こうすれば$r$回の反復で計算が終わり、$r$はあまり大きくないので少し負担が減ります。)
javascriptはちょっと遅いのでC言語でGNU MPを使って書いたものをWebAssemblyで入れようとしたけど、WebAssemblyとGNU MPを同時に使うやり方がわからなかったり、データの受け渡し方法をどうすればいいか分からなかったりしました。
､､､

まぁ、できたんですけどね。

前より5倍くらい早くなったサイト