9.29.2013

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〜 NewImage
正規化数 1〜2046 0〜 NewImage
無限大 2047 0 NewImage
NaN(非数) 2047 1〜 基本的に符号の区別はない (詳細はWikipedia参照)

 

実装の確認

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

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import struct
from bitarray import bitarray
def double_to_bitstring(d):
b = bitarray()
b.frombytes(struct.pack('!d', d))
s = b.to01()
return '%s %s %s' % (s[0], s[1:12], s[12:])
def bitstring_to_double(bs):
return struct.unpack('!d', bitarray(bs).tobytes())[0]
def print_header():
print(' ' * 19 + 'sign')
print('double'.center(18) + ': v <exponent > < ' + 'significant'.center(48) + ' >')
print('=' * 86)
def print_double(d):
print('%18s: ' % d + double_to_bitstring(d))
if __name__ == '__main__':
print_header()
print_double(0.0)
# 負のゼロというものも存在する
print_double(-0.0)
print_double(2.0)
print_double(3.0)
print_double(1.0)
# 2進数の小数では有限で表現できないため、誤差が発生する
print_double(0.1)
# 非数
print_double(float('nan'))
# 無限
print_double(float('inf'))
print_double(float('-inf'))
# 正規化数の限界
print_double(2.225073858507202e-308)
print_double(1.7976931348623157e+308)
# 非正規化数
print_double(2.225073858507201e-308)
print_double(5e-324)
# バイナリからの逆引き
# print(bitstring_to_double('0' + '0' * 10 + '0' + '0' * 51 + '1'))
# print(bitstring_to_double('0' + '0' * 10 + '1' + '0' * 51 + '1'))
# print(bitstring_to_double('0' + '1' * 10 + '0' + '1' * 52))
# print(bitstring_to_double('1' + '1' * 10 + '1' + '1' * 52))
# print(bitstring_to_double('1' + '0' * 10 + '1' + '1' + '0' * 51))
# print(bitstring_to_double('1' + '0' * 10 + '0' + '1' + '0' * 51))
view raw floating_point_numbers.py hosted with ❤ by GitHub
出力例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
                   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
投稿者 mog project 時刻: 14:22 0 コメント
ラベル: ,

9.28.2013

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

 

ダウンロード

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 で行うのを忘れがち。

投稿者 mog project 時刻: 15:46 0 コメント
ラベル: ,

9.17.2013

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
投稿者 mog project 時刻: 1:54 0 コメント
ラベル: ,

9.12.2013

Scala: How to Compare Array Contents

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

 

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

["collections"] - 配列 - Scala Documentation

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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() を利用するのが最善とされている。

1
2
scala> a sameElements b
res3: Boolean = true

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

1
2
3
4
5
scala> a.deep == b.deep
res4: Boolean = true
 
scala> a.corresponds(b)(_ == _)
res5: Boolean = true

 

 

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

投稿者 mog project 時刻: 23:35 0 コメント
ラベル:

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 でも可) メソッドがまさに適役である。

1
2
3
4
5
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 が使える。

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

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

投稿者 mog project 時刻: 23:34 0 コメント
ラベル:

9.08.2013

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

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

 

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#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);
}

 

出力例

1
2
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とかに比べるとストレスフルだなあ。

投稿者 mog project 時刻: 18:43 0 コメント
ラベル:

9.04.2013

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セット実行し、実行時間が最も短かった結果を評価する。

TrimArray.scala
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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 の強さが際立ってくるのが面白い。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
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
投稿者 mog project 時刻: 2:00 0 コメント
ラベル:
登録: 投稿 (Atom)