Google の 二段階認証が快適だった

Google からメールが来た

以下のようなメールが届いた。

Soon you’ll sign in with 2-Step Verification

After you enter your password, you’ll complete a second step on your phone. Keep your phone nearby when you sign in.

2-Step Verification will be turned on automatically on December 9. You can turn this on sooner if you want — your account is all set.

Google ログイン時に二段階認証が必要になるらしい。

二段階認証 = 面倒くさいという先入観

以前働いていたチームでサーバログイン時に二段階認証を使っていたが、正直言うと、かなり面倒という印象があった。

• ログイン画面にパスワードを入力する
• トークンデバイスに表示されるワンタイムパスワードを入力する

上記の認証方法は 2016 - 2018 年頃に所属していたチームで使われていた。（少なくとも自分の近くの）周りの人たちからは「生産性が落ちるだけ、セキュリティと生産性のトレードオフをもっと考えるべき」と酷評だった。

また、とあるクレジットカード会社ではウェブショッピングをするときに以下のような二段階認証が必要になる

• カード情報を入力後、クレジットカード会社のページにリダイレクトするので、パスワードを入力する
• 登録している携帯電話のSMSに送付されるワンタイムパスワードを入力する

海外にいる場合これは地味に面倒だったりする。認証時には通常つけている現地SIMを日本の番号のSIMに入れ替えなければいけない。また、海外にいるとSMSが届かなかい場合がある。それならいっそ現地SIMの番号を登録すればと思うが、日本の番号しか登録できなかったりする。

Googleのはどうなっているか

二段階認証するためのオプションがいくつか用意されている。SMSやボイスメールでの認証やワンタイムパスワードの認証も選択できるが、Google prompts がおすすめ。以下のように認証を行うことができる。

• パスワードを入力する
• スマホにインストールしている Google アプリに「あなたは今サインインしようとしていますか？」のようなポップアップが出るので、「はい」を選択する

これだけなのでかなりシンプル。

「はい」だけで認証できるのは大丈夫なのか心配になるが、デバイス情報、場所、時刻などからあやしいアクティビティはブロックされるらしい。ログイン済みのデバイスにしかポップアップ通知を出さないので、SMSより安全という気もする。一度認証が済んだデバイスは信頼できるデバイスとして登録することができ、次回の認証からは二段階認証をスキップできる。

ということで、自分がもっていた「二段階認証 = 面倒くさい」という先入観は無くなりました。利便性を損ねることなくセキュリティを強化するように考えられていて、さすが Google と感動しました。

GETとPOSTの違い

GETとPOSTの違いについて勉強しました。

HTML specificationsによる定義/推奨

■ GET

• データはURLに含まれる。
•  idempotentな（永続的な効果をもたらさない、副作用をもたらさない）処理を行うときに使うことが推奨されている。 ⇒データを取得するときに使用する。

■ POST

• データはmessage body部分に含まれる。 
• idempotentではない処理を行うときに使うことが推奨されている。 ⇒データのソート、更新、商品の注文、Emailの送信など。

実用的な違い/留意点

• GETはサーチエンジンのクローラーに踏まれる可能性があるので、副作用のある処理をGETで処理すると、不用意にデータを消去されたり、更新されたりする可能性がある。
• GETリクエストに対するレスポンスはキャッシュできる（※）場合が多い。POSTリクエストに対するレスポンスがキャッシュされることはほとんどない。
• GETはURLをブックマーク保存できる。
• GETはURLにデータが載るので、Webサーバやプロキシサーバーのログに残る。リンクで他ページに遷移したときにRefererのところにも載る。⇒パスワードなどのセンシティブな情報を送る場合はGETは避けるべき。
• GETにはASCII文字以外を含めない方がいい。(原則上は扱えないが、実用上は扱える。)マルチバイト文字をクエリーに含む検索処理の場合は、POSTを使う方が（idempotent=GETの基本精神に反するが）ベター。
• GETはPOSTより送信できる情報量が少ない。
• ブラウザの「戻る」ボタン⇒POSTは警告を上げる。GETはそのまま遷移。

（※）ちなみにキャッシュはいろいろな種類があって、

• ブラウザーキャッシュ
• プロキシーキャッシュ
• ゲートウェイキャッシュ（リバースプロキシー）

などがあります。

まとめ

基本的には、データのREAD処理の場合はGETを使い、CREATE/UPDATE/DELETE処理の場合POSTを使えばよいと思います。あとはセキュリティの観点からセンシティブな情報を送信する場合はPOSTを使うべきです。

参考サイト

1. Methods GET and POST in HTML forms - what's the difference?
2. Get vs Post
3. CACHING TUTORIAL

Google Translate APIが有料化されてた

最近気付いたのですが、Google Translate APIが有料化されました。昨年twitter上の英語のつぶやきを日本語に自動翻訳するというサイトを作ったのですが、それがうまく機能していないのに気付き調べてみると以下のとおりでした。

Google Translate API v2 is now available as a paid service only, and the number of requests your application can make per day is limited. As of December 1, 2011, Google Translate API v1 is no longer available; it was officially deprecated on May 26, 2011. These decisions were made due to the substantial economic burden caused by extensive abuse. For website translations, we encourage you to use the Google Website Translator gadget.

(http://code.google.com/intl/ja/apis/language/translate/overview.htmlより引用)

　何とも悲しい限りです。しかしサイトを作った労力は無駄にはならないはずです。RESTの概念やphpでxmlをパースする方法を勉強できたので。

32bit v.s. 64 bit CPU

I was not perfectly sure about what the difference between a 32bit CPU and that of 64-bit.

But all things have cleared away.

There are two differences between them.

1. The maximum size of number that each CPU can deal with.

I found an interesting site:

The below explains quite well about the difference.

http://stackoverflow.com/questions/3072444/long-long-int-on-32-bit-machines

2. The maximum size of memory size that can be effectively used.

This is because of 1., I think.

Since the maximum number 32 bit can express is up to 2^32 ~ 4*10^9,

it makes no sense to mount more-than-4GB memory on PC with a 32bit CPU.

And you can effectively use 2^64 ~ 10^19 byte memory on 64bit machine, theoretically.

Notice that ONE address is assigned to memory by ONE byte.

クロージャとは何か？(2)

前回に引き続き、クロージャについて。

前回のブログで、クロージャとは”汎用的な機能を持つ関数の機能を何らかの変数で固定して使うような仕組み”と説明しました。

実際に例を見て、クロージャとは何かを更に詳しく調べてみます。

1,2,3, ...., n

という数列の和を求める関数を書いてみます。

def seriesSum(n):
  ret = 0
  for x in range(1, n+1):
      ret += x
  return ret

久々のPython。。

では、次に、

1, 4, 9, ...., n^2

という数列の和を求める関数を書いてみましょう。

def seriesSum(n):
  ret = 0
  for x in range(1, n+1):
      ret += x*x
  return ret

じゃあ、一般的に

f(1), f(2), ..., f(n)

という数列の和を求める関数は書けないものでしょうか？

クロージャを使えば書けます。

こんな感じ。

def genSeriesSum(_f):
  func = _f
  def seriesSum(n):
      ret = 0
      for x in range(1, n+1):
          ret += func(x)
      return ret
  return seriesSum

使うときは、どうするのでしょうか？

例えば、fはx -> x^2の写像とする場合は以下のようにして使います。

def square(x):
  return x*x

squareSum = genSeriesSum(square)
print squareSum(10)

では、説明してみます。

まず、genSeriesSum()について。

この関数は、

まず、関数オブジェクト_fを受け取ります。

そのあと、変数funcに_fを代入しています。

そして、関数内で定義された関数seriesSum()を関数オブジェクトとして返します。

ここでポイントは、seriesSum()の中のfuncという変数は、_fという値に固定されているということです。

つまり、genSeriesSum()は、機能を固定した（funcを_fにした）関数seriesSum()を生成するような関数であると言えます。

そう、これです。

「機能を固定した関数を生成する関数」

これが、クロージャです。

クロージャを使うと、こんなことも出来ます。

関数の微分値を求める関数。

def genDeriverable(_f, _dx):
  f = _f
  dx = _dx
  def deriverable(x):
      return (f(x + dx) - f(x)) / dx

  return deriverable

どうでしょうか？

クロージャ、すごいです。

個人的には、クロージャとは、関数ファクトリーという感覚を覚えました。

私の認識が間違ってたら、是非是非指摘してくださいーー。

クロージャとは何か？(1)

最近よく耳にするクロージャ。

JavaやC++の最新バージョンがクロージャをサポートするとか、しないとか。。

で、結局、クロージャって何なの？

いろいろ調べてみましたが、「なるほど！」と思わせるサイトがいくつかあったので、それを読んで得た知識を紹介します。（間違いなどありましたらご指摘ください。）

wikiをみると、以下のような解説があります。

In computer science, a closure is a first-class function with free variables that are bound in the lexical environment.　Such a function is said to be "closed over" its free variables. A closure is defined within the scope of its free variables, and the extent of those variables is at least as long as the lifetime of the closure itself.

日本語訳。（間違いあるかも。。）

クロージャとは自由変数を持つ第一級関数である。そして、その自由変数はそのスコープにおいて境界となる。このような関数はその自由変数に包括されたと言われる。

クロージャはその自由変数のスコープによって定義され、それらの変数の有効期限は、クロージャそのもののライフタイムと同じ程度である。

これだけ見ても？？な感じですが、具体的な例を見るとその意味が分かります。

クロージャの例や便利な使い方（pythonでの使用例）は次回紹介するとして、今回は、クロージャのポイントをまとめます。

①変数を持ち、かつ、オブジェクトのように扱うことのできる関数である。

②自由変数によってその機能がclosed（固定）される。

③自由変数は、クロージャそのものが存在している間は、記憶され続ける。

どうやら、汎用的な機能を持つ関数の機能を何らかの変数で固定して使うような仕組みを”クロージャ”と呼ぶのではないでしょうか？

逆に言うと、異なる変数で"closed"してあげると、異なる機能を持った関数を簡単に作成することができるということにもなります。

続きを読む..

末尾再帰について

ちょっと夜更かしして末尾再帰について勉強。。

下の解説がかなり分かりやすいです。

In traditional recursion, the typical model is that you perform your recursive calls first, and then you take the return value of the recursive call and calculate the result. In this manner, you don't get the result of your calculation until you have returned from every recursive call.

In tail recursion, you perform your calculations first, and then you execute the recursive call, passing the results of your current step to the next recursive step. This results in the last statement being in the form of "(return (recursive-function params))" (I think that's the syntax for Lisp). Basically, the return value of any given recursive step is the same as the return value of the next recursive call.

The consequence of this is that once you are ready to perform your next recursive step, you don't need the current stack frame any more. This allows for some optimization. In fact, with an appropriately written compiler, you should never have a stack overflow snicker with a tail recursive call. Simply reuse the current stack frame for the next recursive step. I'm pretty sure Lisp does this.

ざっくり日本語で言うと、

1. 普通に再帰を書くと、再帰して呼び出した結果を利用して、値を計算するという流れになる。
2. 末尾再帰では、一番最後に自身を再帰する。最初に計算をして、その値を呼び出し先に伝えるという手法を取る。
3. 末尾再帰を用いると、現在使用しているスタック構造をそのまま再帰呼び出し先で再利用することができ、スタックの節約ができる。

3.は末尾再帰の最適化と呼ばれているそうです。実際は、再帰が繰り返しループに置換されるみたい。末尾再帰の恩恵を受けるには、この最適化機能が使用する言語で提供されているかどうかが肝になるみたい。

とりあえず、言葉の説明はこの程度にしておいて、いつものようにサンプルコードを。

int factorial(int n) {
  if (!n)
      return 1;
  return n * factorial(n-1);
}

上のコードは階乗を求めるソースです。普通は、上のように書くでしょう。。

これは、factorial(n-1)の値を求めて、それにnをかけてreturnするという形になっています。つまり再帰呼び出しの結果を用いて計算を実施したのち、returnという形です。

計算されるイメージはこんな感じ。

factorial(5)

5*factorial(4)

5*(4*factorial(3))

5*(4*(3*factorial(2)))

5*(4*(3*(2*factorial(1))))

5*(4*(3*(2*1)))

これに対して、末尾再帰。

int factorial2(int n, int acc=1) {
   if (!n)
       return acc;
   return factorial2(n-1, n*acc);
}

かるく衝撃を覚えるほどのソースコードです。returnするときには、現在の関数のスタックは必要じゃなくなってますね。。ちょっと動的計画を彷彿とさせるような感じですが。。

この場合の計算イメージはこんな感じです。

factorial2(5,1)

factorial2(4,5)

factorial2(3,20)

factorial2(2,60)

factorial2(1,120)

factorial2(0,120)

末尾再帰の場合は、最後に呼び出された関数の戻り値が答えになります。それぞれの関数は自分の役割を終えたら、後は呼び出し先に任せるよ。ってイメージです。

逆に普通の再帰の場合は、最初に呼ばれた関数の戻り値が答えになります。

それぞれの関数は、自分の仕事を部下に任せるんですが、部下が仕事を終えるのをずっと待っていなくてはなりません。一番上の関数は、部下の部下の部下の・・・・部下の仕事が終って、自分のところまで結果が戻ってくるのを待たないといけないわけですね。。これは大変。（面倒くさそう。。日本のソフト開発の主流であるウォータフォールモデルみたい。。）

残念ながら、私が使用しているC++環境では末尾再帰の最適化はサポートされていないようです。末尾再帰を使って書いた関数（総和を求める関数）でもスタックオーバーを起こしました。。

引用サイト：　http://stackoverflow.com/questions/33923/what-is-tail-recursion

誤差にまつわるエトセトラ

今日は、浮動小数点小数の数値計算誤差について書こうと思う。


まず、以下のコードを実行してみましょう。

#define EPS 1e-7

int main() {
    // case 1
    double x = 1e16;
    printf("%lf\n", x + 1);

    // case 2
    double y1 = 123456123456.1234588623046875;
    double y2= 123456123456.1234741210937500;

    printf("%d\n", ABS(y1 - y2) < EPS);
    printf("%d\n", ABS(y1 - y2) < EPS * y1);

    // case 3
    double z1 =  1e-1072;
    double z2 =  -1e-1072;
    printf("%d\n", ABS(z1 - z2) < EPS * z1);

    return 0;
}

結果は以下のようになります。


>10000000000000000.000000
0
>1
>0
>1.000000


まず、case1から見ていきましょう。
10000000000000000.000000に1を足しても
10000000000000001.000000にはなりません。
これは、doubleの有効桁数が2^52 ~10^15だからです。最初の15桁以下は丸められてしまいます。逆に言うと、10^15以下の整数ならdoubleで正確に表すことができます。
この辺の話は昔投稿しているので、こちらをご覧ください。


次に、case2です。
これは、おもしろいです。y1とy2をビット列で表すとそれぞれ以下のようになります。


01000010 00111100 10111110 10001110 11110010 01000000 00011111 10011011
01000010 00111100 10111110 10001110 11110010 01000000 00011111 10011100


実は、この2つの数は、doubleの世界では連続する数値です。それにも関らず、(y1-y2)は1e-5程度です。
これは、大変です。連続する値なので、ほんの少しのエラーで、ある値がもう片方の値になりえます。
数値計算を実施する際は、この２つは、同じ値とみなしてよいでしょう。
しかし、ABS(y1-y2) ＜ eps (eps = 1e-7)

なんてやっちゃうと、この2つの値は、同値とは判定できません。

何がまずかったのでしょう・・。

doubleは浮動小数点なので、小数点の位置は固定ではありません。つまり、絶対的な値を誤差の許容範囲とするには無理があります。

ここでは、

ABS(y1-y2) ＜ eps * y1

とするとよいでしょう。

最後にcase3。これは、やっかいです。case2で

ABS(y1-y2) ＜ eps * y1

を判定条件に用いればよいことを示しましたが、case3では、この判定条件は適切ではありません。

同値とみなすべきz1とz2が同値とみなされません。

符号が異なる2つの微量な数値を比較する場合は、case2の場合は適さないようです。

では、どうすればいいか・・・。

case2とcase3を2つ使って判定しましょう。結構面倒ですが・・。。

競技系プログラミングでは、小数が現れないように分母を他辺に掛けるテクニックが有効のようです。また、比較する値の絶対値が比較的小さいものであれば、絶対評価（case2）だけ十分でしょう。

出典）

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=integersReals

読んで理解したことを書こうと思ったら、ほぼ和訳みたいになりました（笑）

英語が出来る人は、上の原文を読んだ方が分かりやすいはずです。

ビット演算で遊ぼう

Hi, folks. How's it going?

I made an application that deals with some bit operations. Guess it's downright interesting.

If you're unfamiliar with bit operations, I recommend you try the application below.

どうやら、アメリカからもアクセスがあるみたいなので、ちょっとだけ英語でも書いてみました。

今日はビット演算がテーマです。

世の変態天才プログラマーたちは、ビット演算を巧みに扱います。ビット演算の魔術師と言っても過言ではありません。

私も最近ビット演算のすごさに気付きました。ビットというのは2進数なのでいろいろなことに使えます。例えばバイナリサーチの応用のようなこと(※)もビット演算で出来ます。

（※　「のようなこと」と書いたのは少なくとも私のイメージではという意味です。0か1かを常に2つに1つの可能性を選んでデータを構築していて、探索時はO(log n)で出来るという意味です。詳しくは「ビット演算を用いたべき乗計算の高速化」参照のこと。）

『ビット演算を制するものはプログラムを制する！』

『そうか、ビット演算を使えば、コードの量も1/2になり、実行速度も2倍になる。

つまり、おれがビット演算を使えば、その働きは4倍っていうことか！！！』

桜木花道もびっくり@_@

ちょっと話が脱線しましたが、下がソースです。

ビット演算初心者向けです。かなり基本ですが動きを自分で見て確認するにはいいかと。。

あと、どのような演算を施すと何が起きるのかをしっかり把握できます。一度自分で同じようなものを作ってみるといいでしょう。

void getBin(int n, char bin[]) {
    REP (i, 16)
        bin[15 - i] = (n >> i & 1) + '0';
    bin[16] = '\0';
}

int main() {
    int n, bit;
    char calc, bin[16 + 1];

    cout << "Input an integer." << endl;
    cin >> n;
    getBin(n, bin);
    printf("%s\n", bin);

    // Input one of the manipulations below:
    // q       exit
    // u bit   change bit-th bit to '1'
    // d bit   change bit-th bit to '0'
    // x bit   reverse bit-th bit
    // c       reverse all bits
    // where q, u, d, x and c are characters themselves, bit is an integer and 0-based.
    while (cin >> calc) {
        switch (calc) {
        case 'q':
            cout << "Bye!" << endl;
            return 0;
        case 'u':
            cin >> bit;
            n |= 1 << bit;
            break;
        case 'd':
            cin >> bit;
            n &= ~(1 << bit);
            break;
        case 'x':
            cin >> bit;
            n ^= 1 << bit;
            break;
        case 'c':
            n = ~n;
            break;
        default:
            cerr << "Syntax Error." << endl;
            cerr << "Try again." << endl;
            continue;
        }
        getBin(n, bin);
        printf("%s\n", bin);
    }
    return 0;
}