Representation of Floating-Point Numbers

浮動小数点数のまとめ

概要

• 限られたビットの中で小数を表現する方法の一つが浮動小数点数
• 今日の実装は処理系、言語を問わずIEEE方式(IEEE 754)が標準
• とりあえずIEEE方式の倍精度浮動小数点数(C言語のdouble)の仕組みを覚えておけばいい

 

Wikipedia

浮動小数点数 - Wikipedia
IEEE 754 - Wikipedia

IEEE 754

IEEE 754: Standard for Binary Floating-Point Arithmetic

 

ビットの表現

小数を「(符号) 基数2の指数×仮数」で表現するのが基本的な考え方。
倍精度浮動小数点数の場合、64ビットを以下の3つの部分に分けて意味を持たせる。

 

Sign (符号部, 1bit)

• 0 なら +, 1 なら - を表す

Exponent (指数部, 11bits)

• 11ビットの符号無し整数で表現できるのは 0〜2047(=2^11-1)。
• 0(全てのビットが0)と2047(全てのビットが1)は特殊な用途(後述)で使用される。
• 1〜2046の範囲を、1023 のバイアス付き整数(ゲタ履き表現)で表す。
  例えば符号無し整数の値が 1 であれば -1022、1023 であれば 0、2046 であれば 1023 を意味する。
• だいたい ±1000 と覚えておけば、ビット数を忘れても思い出しやすい
• 基数を 10 で考えると、だいたい 1e-308 〜 1e+308 の範囲を表せる

Significand (仮数部, 52bits)

• 指数部を掛け合わせる前の絶対値
• 整数部分が 1 になるように指数部を調整する(正規化)ので、整数部分の1は明らかであり表現しない。(hidden bitと呼ばれる)
• 例えば仮数が10進表記で 1.75 である場合は、2進表記だと 1.11。
  整数部分を除外して、仮数部の表現は 11000000...(以下0が続く) となる。
• 0付近のごく小さい数を表すために、非正規化表現も用意されている。
  (アンダーフローギャップを埋めるための重要な仕組み)

 

表現の種類

IEEE 754 では5種類の表現が定義されている。

s = sign (0 or 1)
q = exponent (指数部の符号無し整数表記)
c = significand (仮数部の符号無し整数表記) <=小数ではなく整数として見た場合の値

としたときの計算式と合わせて書くと以下のようになる。

種類	exponent(q)	significand(c)	表している値
ゼロ	0	0	+0, -0 (符号の区別がある)
非正規化数	0	1〜
正規化数	1〜2046	0〜
無限大	2047	0
NaN(非数)	2047	1〜	基本的に符号の区別はない (詳細はWikipedia参照)

 

実装の確認

C言語でも可能だが、手っ取り早く Python で確認してみた。
(PyPIからbitarrayをインストールする) 

出力例

                   sign
      double      : v <exponent > <                   significant                    >
======================================================================================
               0.0: 0 00000000000 0000000000000000000000000000000000000000000000000000
              -0.0: 1 00000000000 0000000000000000000000000000000000000000000000000000
               2.0: 0 10000000000 0000000000000000000000000000000000000000000000000000
               3.0: 0 10000000000 1000000000000000000000000000000000000000000000000000
               1.0: 0 01111111111 0000000000000000000000000000000000000000000000000000
               0.1: 0 01111111011 1001100110011001100110011001100110011001100110011010
               nan: 0 11111111111 1000000000000000000000000000000000000000000000000000
               inf: 0 11111111111 0000000000000000000000000000000000000000000000000000
              -inf: 1 11111111111 0000000000000000000000000000000000000000000000000000
2.22507385851e-308: 0 00000000001 0000000000000000000000000000000000000000000000000001
1.79769313486e+308: 0 11111111110 1111111111111111111111111111111111111111111111111111
2.22507385851e-308: 0 00000000000 1111111111111111111111111111111111111111111111111111
4.94065645841e-324: 0 00000000000 0000000000000000000000000000000000000000000000000001

TopCoder: Setting up KawigiEdit

TopCoder: KawigiEdit のセットアップ手順

 

KawigiEdit とは

Kawigi氏が作成した、TopCoder 用のエディタプラグイン。(最新版は Pivanof 氏がメンテ)
以下の特徴を持つ。

• 全ての言語(Java, C++, C#, VT, Python)に対応
• FileEdit のように外部ファイルと同期できる
• テンプレートからコードを生成できる
• 問題文からシグニチャとテストコードを自動生成できる

SRMでこのようなプラグインを利用するのは許可されており、チートとは見なされない。 
Competing in a Rated Algorithm Competition - TopCoder Wiki

ドキュメント
KawigiEdit Documentation

 

ダウンロード

• Kawigi's TopCoder stuff
  最新版はここから
• About TopCoder - Overview
  TopCoder サイト上のプラグインページ

KawigiEdit_x.x.jar を適当な場所に保存。 (私はDropbox上に置いている)

 

エディタの追加

• Arena アプレットを起動
• メニューから Options -> Editor を選択
• Add ボタンを押下し、以下の設定を入力
• Name: KawigiEdit
• EntryPoint: kawigi.KawigiEdit
• ClassPath: ダウンロードした jar ファイルのパス
• 好みに応じて Default, At Startup のチェックを付けて Save

 

各種設定

• Editor Preferences の画面で KawigiEdit を選択し Configure ボタンを押下
• General/Testing
• 作業ディレクトリの指定
  IDEを使ってコードを書く場合には、そのソースディレクトリを指定するとよい。
• Synchronization with external file
  外部ファイルとの連携。チェックONにする。
• Always prefer external file to TC source
  外部ファイルを優先ソースとする。チェックONに。
• Save problem statement to external file
  外部ファイルにコメントとして問題文を記述。チェックONに。
   

他はデフォルトのままでも基本的に問題なさそう。

テンプレートを変えたい場合は言語ごとに .ket ファイルを作成する。

また、デフォルトのプログラミング言語の変更はこの画面ではなく
Arena のメニューから Options -> Setup User Preferences を開き、
Editors タブ -> Default Language で行うのを忘れがち。

Coding Python in Emacs

Emacs で Python コーディング

 

Emacs で Python 開発環境を整える手順。
ただ挫折しそうになったので今は IntelliJ IDEA (ultimate) がメイン。

対象環境

• Emacs 2.4

プラグインのインストール

• init.el の編集
  以下の内容を追加し、ダウンロード先を追加。

  (require 'package)
  (add-to-list 'package-archives '("melpa" . "http://melpa.milkbox.net/packages/") t)
  (add-to-list 'package-archives '("marmalade" . "http://marmalade-repo.org/packages/"))
  (package-initialize)

• Emacsを起動し、「M-x package-list-packages」でパッケージの一覧を取得
• 「python-mode」「pep8」をインストール
  (C-n などで画面を移動し、Enter、C-x o などのコマンドで遷移。

基本的な操作

• C-c C-c: バッファの内容を実行
• C-c C-z: Pythonプログラムの実行バッファを表示

Flymake などの設定は以下を参照。

References

• EmacsWiki: Python Programming In Emacs

Scala: How to Compare Array Contents

Scala: Array の内容を比較する方法

 

Scala における Array の実装は Java の配列である。

["collections"] - 配列 - Scala Documentation

そのため List などと異なって(*1)、Array どうしを比較した場合、内容が同じでも true が返ることはない。
Array の equals() メソッドが単純な参照の比較しかしないからだ。

scala> val a = Array(1,2,3)
a: Array[Int] = Array(1, 2, 3)

scala> val b = Array(1,2,3)
b: Array[Int] = Array(1, 2, 3)

scala> a == b
res0: Boolean = false

scala> a equals b
res1: Boolean = false

scala> a eq b
res2: Boolean = false

内容の比較を行う際には、以下のように sameElements() を利用するのが最善とされている。

scala> a sameElements b
res3: Boolean = true

deep どうしを比較したり、corresponds を使ったりしても同じことが実現できる。

scala> a.deep == b.deep
res4: Boolean = true

scala> a.corresponds(b)(_ == _)
res5: Boolean = true

 

 

*1: GenSeqLike.scala で equals メソッドがオーバーライドされている。

Scala: Converting From Number List To Cumulative List

Scala: 数列から累積値のリストを作る

 

目的

a[0], a[1], a[2], ... , a[n] のような数値が入ったリストを元に、

b[0] = a[0]
b[1] = a[0] + a[1]
b[2] = a[0] + a[1] + a[2]
...
b[n] = a[0] + a[1] + a[2] + ... + a[n] 

が成り立つ累積値のリスト b[0], b[1], b[2], ... , b[n] を作成したい。

 

コード

scanLeft (scan でも可) メソッドがまさに適役である。

scala> List(1, 3, 5, 2, 4).scanLeft(0)(_ + _)
res0: List[Int] = List(0, 1, 4, 9, 11, 15)

scala> List(1, 3, 5, 2, 4).scanLeft(0)(_ + _).tail
res1: List[Int] = List(1, 4, 9, 11, 15)

初期値 0 を元手に累積的に加算を行った後、tail で先頭の 0 を取り除いている。

 

数値を右から足し込みたい場合には、scanRight が使える。

scala> List(1, 3, 5, 2, 4).scanRight(0)(_ + _).init
res2: List[Int] = List(15, 14, 11, 6, 4)

体感としても、計算量 Θ(n) になっている模様。

C++: How to Count the Frequency of the Elements in a Container

C++: コンテナ中の要素の出現頻度をカウントする

 

コード

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

template <class InputIterator>
std::vector<std::pair<typename InputIterator::value_type, int> >
frequency(InputIterator first, InputIterator last) {
  typedef typename InputIterator::value_type ValType;
  typedef std::map<ValType, int> MapType;
  typedef std::vector<std::pair<ValType, int> > VecType;

  MapType m;
  for (InputIterator it = first; it != last; ++it) {
    if (m.find(*it) == m.end()) {
      m.insert(typename MapType::value_type(*it, 1));
    } else {
      ++m[*it];
    }
  }

  return VecType(m.begin(), m.end());
}

// for utility
template <typename T>
std::ostream & operator<<(std::ostream & stream, std::vector<T> & v) {
  stream << "[";
  for (typeof(v.begin()) i = v.begin(); i != v.end(); ++i) {
    if (i != v.begin()) { stream << ", "; }
    stream << *i;
  }
  stream << "]";
  return stream;
}
template <typename T, typename U>
std::ostream & operator<<(std::ostream & stream, std::pair<T, U> & p) {
  stream << "(" << p.first << ", " << p.second << ")";
  return stream;
}
#define print(a) std::cout << a << std::endl
#define all(a) (a).begin(),(a).end()

// main
using namespace std;

int main(int argc, char **argv) {
  string apple = "apple";
  vector<pair<char, int> > a = frequency(all(apple));
  print(apple << ": " << a);

  int xs[] = { 1, 3, 5, 4, 3, 2 };
  vector<int> v(xs, xs + sizeof(xs) / sizeof(xs[0]));
  vector<pair<int, int> > b = frequency(all(v));
  print(v << ": " << b);
}

 

出力例

apple: [(a, 1), (e, 1), (l, 1), (p, 2)]
[1, 3, 5, 4, 3, 2]: [(1, 1), (2, 1), (3, 2), (4, 1), (5, 1)]

やはり、Scalaとかに比べるとストレスフルだなあ。

Scala: Trimming Trailing Elements - List, Array and Vector

シーケンスから末尾のゼロ要素を削除する処理の性能測定

 

こちらの投稿が気になったので手元でも実験してみる。 

How do I remove trailing elements in a Scala collection? - Stack Overflow

 

計測コード

時間計測用のトレイトと、トリミング関数 2種類を用意した。

トリミング関数に渡す数列は、ランダムな数列の後ろに一定数の「0」を付け加えたもの。
List, Array, Vector のそれぞれで所要時間を計測する。 

10,000回のループを 3セット実行し、実行時間が最も短かった結果を評価する。

import scala.util.Random

trait TimeIt {
  def timeit(description: String = "", repeat: Int = 3, number: Int = 10000)(proc: => Unit) {
    def loop[A](n: Int)(f: => A) { if (n > 0) { f; loop(n - 1)(f) } }

    val elapsed = List.fill(repeat){
      val start = System.currentTimeMillis
      loop(number)(proc)
      System.currentTimeMillis - start
    }.min
    println(s"${description}: ${elapsed} msec")
  }
}

object TrimArray extends TimeIt {
  def trimA[A](a: Seq[A]) = a.reverse.dropWhile(_ == 0).reverse
  def trimB[A](a: Seq[A]) = a.take(a.lastIndexWhere(_ != 0) + 1)

  def main(args: Array[String]) {
    for (
      randoms <- List(10, 100, 1000);
      zeros <- List(10, 100, 1000)
    ) {
      // Create random sequence.
      val list = List.fill(randoms)(Random.nextInt) ++ List.fill(zeros)(0)
      val array = list.toArray
      val vector = list.toVector

      println(s"randoms: ${randoms}, zeros: ${zeros}")
      timeit("[1] List   -> reverse + dropWhile  "){ trimA(list) }
      timeit("[2] List   -> take + lastIndexWhere"){ trimB(list) }
      timeit("[3] Array  -> reverse + dropWhile  "){ trimA(array) }
      timeit("[4] Array  -> take + lastIndexWhere"){ trimB(array) }
      timeit("[5] Vector -> reverse + dropWhile  "){ trimA(vector) }
      timeit("[6] Vector -> take + lastIndexWhere"){ trimB(vector) }
    }
  }
}

 

実行結果

計測してみると、全体的に take + lastIndexWhere バージョンが明らかに速い結果となった。

ただし、List だけは take 処理で性能劣化が発生するため、末尾のゼロ要素が少なければ reverse バージョンの方が逆転して速くなることもあった。(ex. randoms: 1000, zeros: 10)

また、全体のシーケンスが長ければ長いほど、Vector の強さが際立ってくるのが面白い。

randoms: 10, zeros: 10
[1] List   -> reverse + dropWhile  : 11 msec
[2] List   -> take + lastIndexWhere: 4 msec
[3] Array  -> reverse + dropWhile  : 7 msec
[4] Array  -> take + lastIndexWhere: 3 msec
[5] Vector -> reverse + dropWhile  : 12 msec
[6] Vector -> take + lastIndexWhere: 13 msec
randoms: 10, zeros: 100
[1] List   -> reverse + dropWhile  : 22 msec
[2] List   -> take + lastIndexWhere: 13 msec
[3] Array  -> reverse + dropWhile  : 18 msec
[4] Array  -> take + lastIndexWhere: 6 msec
[5] Vector -> reverse + dropWhile  : 38 msec
[6] Vector -> take + lastIndexWhere: 9 msec
randoms: 10, zeros: 1000
[1] List   -> reverse + dropWhile  : 177 msec
[2] List   -> take + lastIndexWhere: 89 msec
[3] Array  -> reverse + dropWhile  : 93 msec
[4] Array  -> take + lastIndexWhere: 28 msec
[5] Vector -> reverse + dropWhile  : 235 msec
[6] Vector -> take + lastIndexWhere: 54 msec
randoms: 100, zeros: 10
[1] List   -> reverse + dropWhile  : 25 msec
[2] List   -> take + lastIndexWhere: 21 msec
[3] Array  -> reverse + dropWhile  : 45 msec
[4] Array  -> take + lastIndexWhere: 12 msec
[5] Vector -> reverse + dropWhile  : 48 msec
[6] Vector -> take + lastIndexWhere: 4 msec
randoms: 100, zeros: 100
[1] List   -> reverse + dropWhile  : 37 msec
[2] List   -> take + lastIndexWhere: 29 msec
[3] Array  -> reverse + dropWhile  : 53 msec
[4] Array  -> take + lastIndexWhere: 15 msec
[5] Vector -> reverse + dropWhile  : 68 msec
[6] Vector -> take + lastIndexWhere: 9 msec
randoms: 100, zeros: 1000
[1] List   -> reverse + dropWhile  : 187 msec
[2] List   -> take + lastIndexWhere: 108 msec
[3] Array  -> reverse + dropWhile  : 130 msec
[4] Array  -> take + lastIndexWhere: 55 msec
[5] Vector -> reverse + dropWhile  : 276 msec
[6] Vector -> take + lastIndexWhere: 59 msec
randoms: 1000, zeros: 10
[1] List   -> reverse + dropWhile  : 235 msec
[2] List   -> take + lastIndexWhere: 244 msec
[3] Array  -> reverse + dropWhile  : 525 msec
[4] Array  -> take + lastIndexWhere: 156 msec
[5] Vector -> reverse + dropWhile  : 385 msec
[6] Vector -> take + lastIndexWhere: 4 msec
randoms: 1000, zeros: 100
[1] List   -> reverse + dropWhile  : 303 msec
[2] List   -> take + lastIndexWhere: 240 msec
[3] Array  -> reverse + dropWhile  : 503 msec
[4] Array  -> take + lastIndexWhere: 152 msec
[5] Vector -> reverse + dropWhile  : 435 msec
[6] Vector -> take + lastIndexWhere: 11 msec
randoms: 1000, zeros: 1000
[1] List   -> reverse + dropWhile  : 406 msec
[2] List   -> take + lastIndexWhere: 314 msec
[3] Array  -> reverse + dropWhile  : 559 msec
[4] Array  -> take + lastIndexWhere: 170 msec
[5] Vector -> reverse + dropWhile  : 659 msec
[6] Vector -> take + lastIndexWhere: 101 msec