メモの日々

■ [dev][math] 累乗を高速に計算する

累乗の計算はバイナリ法（繰り返し二乗法）と呼ばれるアルゴリズムで高速に計算できる。

再帰で考えるとわかりやすいのでそれをメモ。

\[ \ a^x = \begin{cases} 1 & (x = 0) \\ (a^2)^{\frac{x}{2}} & (\text{$x$が偶数}) \\ a \cdot a^{x-1} & (\text{$x$が奇数}) \end{cases} \]

が成り立つので、これをそのままコードに書けばよい。

素朴な実装と繰り返し二乗法の実行時間を比較するコードを示す。計算結果は巨大な数になるため、1000000007 で割った余りを計算するようにしている。

#include <chrono>
#include <iomanip>
#include <iostream>
#include <string>

// 素朴な実装
long mod_pow0(long a, long x, long m)
{
  long result = 1;
  for (long i = 0; i < x; ++i) {
    result = result * a % m;
  }
  return result;
}

// 繰り返し二乗法
long mod_pow(long a, long x, long m)
{
  if (x <= 0) return 1;
  return x & 1
      ? a * mod_pow(a, x - 1, m) % m
      : mod_pow(a * a % m, x >> 1, m);
}

// 時間計測をする
template<typename F>
void measure(const std::string& name, F f)
{
  namespace ch = std::chrono;
  const auto s = ch::steady_clock::now();
  const auto result = f();
  const auto e = ch::steady_clock::now();
  const auto d = ch::duration_cast<ch::duration<double>>(e - s).count();
  std::cout << std::fixed
      << name << " = " << result
      << " (" << d << " sec)"
      << std::endl;
}

int main()
{
  constexpr long m = 1000000000 + 7;
  long a, x;
  std::cin >> a >> x;

  measure("mod_pow0", [a, x, m]() { return mod_pow0(a, x, m); });
  measure("mod_pow ", [a, x, m]() { return mod_pow(a, x, m); });
}

手元の環境だと、素朴な実装でもxが10**8までなら1秒程度で計算できるが、10**9になると10秒以上かかる。繰り返し二乗法は速い。

$ ./a.out
2 10000000
mod_pow0 = 255718402 (0.128632 sec)
mod_pow  = 255718402 (0.000001 sec)

$ ./a.out
2 100000000
mod_pow0 = 494499948 (1.274563 sec)
mod_pow  = 494499948 (0.000001 sec)

$ ./a.out
2 1000000000
mod_pow0 = 140625001 (13.117252 sec)
mod_pow  = 140625001 (0.000002 sec)

■ [hard] ドライヤーを買った

5年前に買ったドライヤーのコードが熱を持つようになったので買い替え。

テスコムからパナソニックへ乗り換えてみる。EH-NE4Aという2500円くらいのにしたが、冷風のターボが無い所は以前のものより劣っている。Amazonのレビューに匂いのことが書かれており、確かに本体が匂う。子供がくさいくさいと言っていた。自分はそれほど気にならないが。

■ [life][work] マイナンバーカードを使ってe-Taxで電子申告をした

青色申告特別控除で65万円の控除を受ける条件として、来年の申告からはe-Taxの使用が加わるようなので、今回初めてe-Taxを使って確定申告をしてみた。

e-TaxはICカードリーダを購入しなければならないのがネックで使っていなかったが、既にNFC対応Android端末をICカードリーダとして利用できるようになっている。

使用したもの

e-Taxの利用には色々な方法があって混乱するのだけれど、今回は次を使って行った。

• Bluetooth対応Windows PCとEdge
• NFC対応Android端末 (Pixel 3a)
• マイナンバーカード

ウェブブラウザとしてEdgeかIE11を使わなければならない。PCとAndroid端末はBluetoothで接続しておく必要がある。

また、PCとAndroid端末にはそれぞれ専用ソフトウェアのインストールが必要になる。

• PC
  • e-Tax Edge用AP
  • 事前準備セットアップ（このインストーラから色々なアプリケーションがインストールされる）
• Android端末
  • JPKI利用者ソフト
  • e-Taxアプリ

PC用ソフトウェアについては手順通り進めていけば順にインストールを促されるのでそれに従えばいい。

申告は確定申告書等作成コーナーから行った。

はまったところ

一番困ったのは、マイナンバーカードから基本4情報を参照する画面で読取エラーになったこと。PC上で「券面事項入力補助用パスワード」を入力するよう促されて入力するのだけれど、何度やってもエラーになってしまう。途方に暮れたが、

• スマートフォンをICカードリーダライタとして利用するためにはどうすればよいのですか。

というFAQ内に

【注意】

Android端末をICカードリーダライタとして利用する場合、券面４情報（氏名・住所・生年月日・性別）の読み取りに対応していませんので、お手数ですが、新規にマイナンバーカード方式を利用する場合は、事前にAndroid端末から以下のとおり、操作してください。

とあるのを見つけて解決できた。Androidのe-Taxアプリを使って事前登録が必要だったのだ。PC上の操作画面にはそのような注意は表示されていなかった(と思う）ので、全員困ってしまうと思うがどうなのだろう。

感想

ほかにも各種ソフトウェアが不安定だったりわかりにくかったり、パスワードを何度も入力させられてうんざりするなど、かなりイライラさせられた。

でも、何とか電子申告できて達成感はある。

■ [life] toto当せんした(7) 3320円

2か月経たないうちにまた当せん。100円BIGの4等で3320円。黒字になるには2等以上じゃないとダメだなあ。

■ [c++] C++17の畳み込み式(fold expression)

C++17から可変引数テンプレートに対して畳み込み式というのが使えることを知ったのでメモ。

• 畳み込み式 (cpprefjp)
• 畳み込み式 (cppreference.com)

以前に書いた可変引数テンプレートのコードを畳み込み式を使って書き直してみる。

#include <iostream>
#include <string>

// sからindexesで指定された位置の文字を繋いだ文字列を返す。
template<typename... Args>
auto select(const std::wstring& s, Args... indexes)
-> decltype(std::initializer_list<int>({indexes...}), std::wstring{})
{
  using namespace std::literals::string_literals;
  return (L""s + ... + s.at(indexes));
}

int main()
{
  std::ios_base::sync_with_stdio(false);
  std::wcout.imbue(std::locale(""));
  std::wcout << select(L"パタトクカシーー", 1, 3, 5, 7) << std::endl;
}

非常に強力。