whileD'iary

日記とか

逆リファクタリングとfma関数

この記事について

100%ポエムです。あとは微妙な技術的要素。

fma関数と僕

僕が所属しているサークルでは、人生において無意味みたいなことをときたまやっているのですが、先日逆リファクタリングをしようという動きがありました。 ざっくり逆リファクタリングを説明すると、いかにコードを汚くかけるかというもので、クソほどの役にもたちません。

実を言うと去年一度開催してまして、そのときにお世話になったのが記事名にもあるfma関数です。このfma関数は何をしてくれるかと言うと

fma(a, b, c);
=> a * b + c

といった具合に積和演算をしてくれます。この関数があると逆リファクタリングする際にあることができます。

そう...アラビア数字を1文字も使わなくてよいのです!!



ご存知の通りc++ではtrueが1、falseが0であり、fma関数から任意の数字を作り出すことが可能です。(これ書いてる途中に気がついたんですが、ビット演算ができるから別にfma関数なくても任意の数を作れますね)

以下はほんの一例

fma(fma(true, true, true), fma(true, true, true), true);
=> 2 * 2 + 1 = 5
fma(true, ~false, ~false) 
=> -2

そもそもこの関数なんのためにあるんだ?

恥知らずなので最近業務でc++を書きはじめてバッドになってる先輩に「数字を使わないでFizzBuzzかけるんですよ〜〜」とか言ったらひとしきり大爆笑した後、謎関数呼ばわり。 気になったので調べてるとどうやらfma関数はC++99の時点であってかなりの古参関数らしい。

こんな掛けて足すだけの関数が本当に重要なのか……?とう疑念を持ちつつも調べていくと、どうやらハードウェアレベルの話でfma系の命令が実装されているっぽいことがわかった。その時は完全にSIMDとかSSEとかに無知だったので意味不明だったのだが、それらを調べると「俺のほうが無知、fmaは偉大みたい」な話に発展。

どうやらfmaをハードウェア側で実装すると丸めの計算が1回に減る上に、大量のベクトル計算ができるから爆速でいいねということだった。

となると当然fma命令を実際に回したかったのだが、僕の環境ではfma命令を入れてくれなかった。俺は偽物のfmaを呼び出して和積を計算。ちゃんとコンパイルオプションつけてコンパイルするとfma関数でfma命令を入れてくれるらしい。

最後に

そんなこんなでサークルのごく一部で無駄に熱いコンテンツになったfma。 そのおかげでCPUのアーキテクチャマイコンなんかも触りたくなって結構いい感じにテックできたなといった感じです。機会があれば積極的に使っていこうと思います、それでは。

FMA周りが詳しく紹介されているサイト。

FMA (Fused Multiply-Add) について色んな観点でまとめてみた - 小清水さんとコンピューター数学

あと去年書いたコード。

#include <iostream>
#include <cmath>
using namespace std;

int inc(int num);
int zero();
int one();
int two();
int three();
int five();
int seven();
int ten();
int sixty_six();
int seventy();
int one_hundred_five();
int one_hundred_seventeen();
int one_hundred_twenty_two();

string Fizz();
string Buzz();

int main(){
  for(int i=zero(); i <= fma(ten(), two(), zero()); i = inc(i)){
    if(i%three() == zero() && i%five() == zero()) cout << Fizz() << Buzz() << endl;
    else if(i%three() == zero()) cout << Fizz() << endl;
    else if(i%five() == zero()) cout << Buzz() << endl;
    else cout << i << endl;
  }
}

int inc(int num) {
  return fma(num, one(), one());
}

int zero(){
  return false;
}

int one(){
  return true;
}

int two(){
  return fma(one(), one(), one());
}

int three(){
  return fma(two(), one(), one());
}

int five(){
  return fma(three(), one(), two());
}

int seven(){
  return fma(three(), two(), one());
}

int ten(){
  return fma(five(), two(), zero());
}

int sixty_six(){
  return fma(five(), ten(), fma(three(), five(), one()));
}

int seventy(){
  return fma(ten(), seven(), zero());
}

int one_hundred_five(){
  return fma(ten(), ten(), five());
}

int one_hundred_seventeen(){
  return fma(one_hundred_five(), one(), fma(ten(), one(), two()));
}

int one_hundred_twenty_two(){
  return fma(one_hundred_five(), one(), fma(ten(), one(), seven()));
}

string Fizz(){
  string fizz;
  fizz.push_back((char)seventy());
  fizz.push_back((char)one_hundred_five());
  fizz.push_back((char)one_hundred_twenty_two());
  fizz.push_back((char)one_hundred_twenty_two());
  return fizz;
}

string Buzz(){
  string buzz;
  buzz.push_back((char)sixty_six());
  buzz.push_back((char)one_hundred_seventeen());
  buzz.push_back((char)one_hundred_twenty_two());
  buzz.push_back((char)one_hundred_twenty_two());
  return buzz;
}

蟻本の分割数の問題を整理

目的

僕には何を言っているのかさっぱりだったので、他の方の解説を見ながら整理して理解する

分割数

nをm個以下に順序を区別せずに分割する方法の総数

m=nのとき特にnの分割数と呼ぶ

問題の漸化式

dp[i][j] = dp[i][j-i] + dp[i-1][j]

このdpのメモは、jをi分割したときの総数(dp[i][j] = jをi分割したときの総数)

まずjをi分割するとなったときにi個のものが自動的に最低1の数としてまず確定する

例えば5を3分割した場合、次の2パターン

  • 3, 1, 1
  • 2, 2, 1

7を4分割した場合、次の3パターン

  • 4, 1, 1, 1
  • 3, 2, 1, 1
  • 2, 2, 2, 1

このときどう分割したところで、それぞれの数は1より下にならない

つまりそれぞれの数から1を引いた数であるj-iの、順序を区別しない並べ方と考えることができる(このときは0を含むので注意)

イメージ的にはi個分の箱を用意して、j-i個のボールを重複のパターンがでないように入れる感じ

上記5を3分割した場合では

  • 2, 0, 0
  • 1, 1, 0

7を4分割した場合では

  • 3, 0, 0, 0
  • 2, 1, 0, 0
  • 1, 1, 1, 0

実際にパターン数は合致している

最後に後ろのdp[i-1][j]はjのi未満の分割の総数だからそれを足して

dp[i][j] = dp[i][j-i] + dp[i-1][j]

となる

参考サイト

Tech Tips: 分割数を考える

分割数の漸化式がよくわかんなかったから軽く整理した - 迷いませんか?

コドフォ初参加

Codeforces#467 div.2にでた

やる気がでてきたのでコドフォに出ました

やる気の維持のために振り返りとか何がわからんかったとかまとめたい

もっとやる気がでたら備忘録的に解説でもしようと思います

A.Olympiad

英語が全然できないので、わかってはいたが英文の問題に戸惑う

英語の読む方に時間かかった

言ってることは割と簡単だったので、重複を消して0以外の個数を数え上げてそれを出力して正解

B.Vile Grasshoppers

英語わかんねって思いながらサンプルと注意書きのところみたら理解できた

答えをnだとすると、nはpまでの数全てで割り切れない

ということはsqrt(109)までの素数リスト作ってyからp+1まで試し割りすればいいかなってなって実装して正解

C.Save Energy!

読解力がなさすぎて、翻訳を駆使しても何を言ってるのか全然わからなかった……

40分くらい英語と格闘して結局諦め

ストーブがついてない時間を計算してtに足せばいいのかな、とか思ってた

全体的に

英語がわからん 以上

bit全探索

C - たくさんの数式 / Many Formulas

をやってて、bitで組み合わせの全探索できるなみたな感じには思えたけど実装がわからなかったので覚え書き程度に書く。

bit全探索

ビットを仕切りに見立てて、ビットを全探索することで部分集合などを求める探索

今回の場合ようは、

1234567

という文字列があったとき

000110

というビットを用いて

1234|5|67

のように分割されているとみなすことができる。

計算量は2n

コード

以下提出したコード

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
using namespace std;
 
int main(){
  string s;
  cin >> s;
  vector<string> nums;
  for (int i=0; i<s.length(); i++) nums.push_back(s.substr(i, 1));
 
  long res = 0;
  long tmp;
  long digit;
  long sum = 0;
  string ssum = "";
  for (int i=0; i< (1 << (nums.size() - 1)); i++) { // bit演算なので条件
    sum = 0;
    tmp = 0;
    digit = 1;
    ssum = nums[0];
    for (int k=0; k<nums.size()-1; k++) {
      if (i & (1 << k)) { // 見てるbitと現在見てる桁に+がついているとき
        sum +=  stol(ssum);
        ssum = "";
      }
      ssum += nums[k+1];
    }
    sum += stol(ssum);
    res += sum;
  }
 
  cout << res << endl;
}

前にビットを使ったとき、アホなので"00000"みたいな文字列作って頑張ってた気がします

bitsetを使えばもっと綺麗にかけそうな気がしないでもない

JS記号プログラミングをやって思ったこと

はじめに

adventar.org

の24日目の記事です

アドベントカレンダーが始まってから24日も経つんですね、はやい

さて今回は、最近JavaScript記号プログラミングをやっていたので、それについて思ったことを書こうと思います

JavaScript 記号プログラミングについて

次のコードを見ていただくと、雰囲気はわかると思います

配列から数値が生成できたり、配列から文字列が作成できる。 しかも次のコードから関数オブジェクトが作成できるので、実質なんでもできます。

[]["constructor"]"constructor"

1 //1
-~[] //1

// constructorと出力
([][$_=([]+{})[-~-~-~-~-~[]]+([]+{})[-~[]]+([][[]]+[])[-~[]]+(![]+[])[-~-~-~[]]+((!![]+[])[-[]])+((!![]+[])[-~[]])+([][[]]+[])[-[]]+([]+{})[-~-~-~-~-~[]]+(!![]+[])[-[]]+([]+{})[-~[]]+(!![]+[])[-~[]]][$_]((([]+{})[-~-~-~-~-~[]]+([]+{})[-~[]]+([][[]]+[])[-~[]]+(![]+[])[-~-~-~[]]+([]+{})[-~[]]+(![]+[])[-~-~[]]+(![]+[])[-~-~-~-~[]])+'.'+(![]+[])[-~-~[]]+([]+{})[-~[]]+(([]+[])[$_]+[])[-~-~-~-~-~-~-~-~-~-~-~-~-~-~[]]+([][$_]+[])[(-~[]<<-~-~-~-~[])+(~-~[])]+"'"+$_+"'"+([][$_]+[])[(-~[]<<-~-~-~-~[])+(~[])]))() 

// constructorと出力
(function(){console.log('constructor')})()

思ったこととか

  • 文字数が少ないほど見にくくなっていい感じになる
    • 使える文字数が増えるにつれ便利になっていくので推測しやすい
  • =や,などの推測可能な文字はできるだけ避けた方がいい
    • 上記のconstructorの例だとわかりやすいが、変数っぽく見える
    • <<などのシフト演算なども避けたほうがいい
  • 改行はしないほうがいい

だいたい以上のリスト通りやるとみにくくなるんじゃないかと思います

シンプルなほどわかりにくいってのはBrainf*ckやwhitespaceが教えてくれている

短く難読化しようとすると、以外にも法則が見つかってしまうので、ここが悩ましいところ

個人的にはダブルクォーテーションや、シングルクォーテーションなど、一発で文字列とわかってしまうのはあまり使いたくなかったのですが、時間なかったのでこれでやってしまった

あと記号プログラミングは先輩がやっていたからやってみたのですが、最初は敬遠していたものの、案外パズルみたいで楽しいですねこれ

皆さんもやってヤバイコード見つけて教えてください

明日のアドベントカレンダー最後の記事を飾るのはかったーさんです

docker使ってC#書いてみた

はじめに

adventar.org

このアドベントカレンダーの19日目の記事です

前回はかがりさんだったのですが、ちゃんと読んだ本をアウトプットしててすごいなと思いました

今回は最近やったこととして、dockerでサクっとC#を書いたという話です

dockerということなので今回はMonoを使用してみました

docker

$ docker run -it mono /bash/bin
$ apt update
$ apt install vim

Mono公式がDockerイメージを配布するのでありえん楽ですね

とりあえずこれでコンテナ内でC#コンパイルと実行ができます

本当は外部ファイルをコンパイルと実行をできるようにしたかったけどよくわからなかったのでやめました

わかる方は教えてください

C

とりあえず車輪の再発明ですがかんたんにスタックを実装

using System.Collections.Generic;
using System;

namespace Info.Whiled {
  class StuckTest{
    public static void Main(){
      Stuck<string> stuck = new Stuck<string>();
      stuck.Push("vim");
      stuck.Push("c#");
      
      Console.WriteLine(stuck.Pop());
      Console.WriteLine(stuck.Pop());
    }
  }
  
  class Stuck<Type> {
    private List<Type> list = new List<Type>();

    public void Push(Type data) {
      list.Add(data);
    }

    public Type Pop() {
      Type data = list[list.Count-1];
      list.RemoveAt(list.Count-1);
      return data;
    }
  }
}

コンパイルして実行

$ mcs Stuck.cs
$ mono Stuck.exe
> c#
> vim

本当にC#コンパイルして実行できた、とか言ってた気がします

次にエラトステネスのふるいを実装

こちらはとりあえず言語触るたびに書いてたのですんなり

特有の構文もいりませんし

using System;

namespace Info.Whiled {
  class Era {
    public static void Main(string[] args){
      bool[] bools = new bool[101];
      for(var i=2; i<bools.Length; i++) bools[i] = true;

      for(var i=2; i<bools.Length; i++){
        if(bools[i])
          for(var j=i*2; j<bools.Length; j+=i)
            bools[j] = false;
      }

      for(var i=2; i<bools.Length; i++){
        if(bools[i]) Console.WriteLine(i);
      }
    }
  }
}
$ mcs Era.cs
$ mono Era.exe
2
3
5
7
11
... 

めっちゃ楽

感想

C#、なかなか書きやすいのではないかと感じた

dockerめっちゃ便利

あと僕に知識がなくそのままコンテナ内でvim使って書いてたのでシンタクッスハイライトとかなにもなしで書いてたのでつらかった

最後に一つ、Windowsがある場合は普通にWindowsで書けばいいなと思いました

内容全然なかったですが、これで終わりです。明日の記事はぬまたさんで「2017年おもしろかったYouTubeの動画を紹介します。」だそうです。きっと面白い記事を書いてくれるでしょう。