今週は無理しすぎて風邪をひいてしまいました。つらい。 来年度からはもっと規則正しい生活をするようにしたいです。 それから、「いつまでにやるか明確に決まっていないけれど、いずれやらないといけないこと」は3月に片づけようと思っていたのに、いろいろ…

先週の記事の続きです。 最大公約数をもっと高速に求める（その3） - よーる 前回示したコードは、以下のようなものでした。 uint64_t gcd_impl( uint64_t n, uint64_t m ) { constexpr uint64_t K = 5; for( int i = 0; i < 80; ++i ) { uint64_t t = n - m…

先週の記事の続きです。 最大公約数をもっと高速に求める（その2）【cmova命令は遅い】 - よーる 前回示したコードは、以下のようなものでした。 uint64_t gcd_impl( uint64_t n, uint64_t m ) { for( int i = 0; i < 10; ++i ) { uint64_t t = n - m; bool …

先週の記事の続きです。 最大公約数をもっと高速に求める（その1） - よーる 前回示したコードは、以下のようなものでした。 uint64_t gcd_impl( uint64_t n, uint64_t m ) { for( int i = 0; i < 10; ++i ) { uint64_t t = n - m; bool q = m > t; n = q ? …

最大公約数を求める非常に有名なアルゴリズムとして、ユークリッドの互除法が知られています。 このアルゴリズムは、二つの入力を十進法で表したとき、小さいほうの桁数の高々五倍の回数の剰余演算で最大公約数が求まることが知られています（ラメの定理）*1…