よく考えたら、これは長い多項式の掛け算だからKaratsuba法が使えますね。Scalaは多倍長整数の掛け算が遅いので特に効果が大きいはずです。
これくらい速くなりました。
1050 0.6s -> 0.12s
10100 3.4s -> 0.5s
10200 28s -> 2.4s
よく考えたら、これは長い多項式の掛け算だからKaratsuba法が使えますね。Scalaは多倍長整数の掛け算が遅いので特に効果が大きいはずです。
これくらい速くなりました。
1050 0.6s -> 0.12s
10100 3.4s -> 0.5s
10200 28s -> 2.4s