2014-02-25

goto fail; をコンパイル時に検出する

日本語の記事が見当たらないので書きます。iOS のSSLのバグは、コンパイル時に検出できます。警告オプション -Wunreachable-code をつけて clang でコンパイルすれば良いだけです。

バグの原因

このバグの原因は、意図しない場所に goto 文が書かれていたため、重要な処理をスキップしてしまうというものです。
こちらのブログ記事で紹介されてますが、単純化すると以下のようになります。

error_code important_function()
{
    error_code err;

    // ...

    if (err = some_function(...))
        goto fail;
    if (err = some_function2(...))
        goto fail;
        goto fail; // (A)

    // 重要な処理 (B)
    // ...

fail:
    // 後始末
    // ...

    return err;
}

ご覧の通り、goto 文 (A) で常に重要な処理をスキップしています。err は (B) で失敗を表す値になり得るので、important_function は失敗するはずなのに、実際には成功を表す値を返す場合があります。ここの632行目ですね……。

対策

元コードについてはそもそも、 if 文の statement 部を compound-statement にした方がいいとか、きちんとインデントした方がいいとか突っ込みどころは多いんですが、ひとまず措きます。そういったことは考えず、バグは機械的に見つけたいものです。決して実行されないコードが関数内にあるという事実は、バグの存在を強く示唆しますね。上のコードだと、実行されないコードがあることはコンパイル時に分かるはずです。

上で紹介したブログ記事にも書かれてますが、clang で -Wunreachable-code をつけてコンパイルすれば警告されます。残念ながら -Wall をつけただけでは -Wunreachable-code は有効にはなりませんので明示的につける必要があります。

2012-10-05

続・PFIサマーインターン2011問題

今更ですが、これの続き。
前回は最悪がO(n²)だったので、最悪をO(n)にしました。

#include <assert.h>
#include <algorithm>
#include <string>

char pfi2011(std::string& s)
{
    assert(!s.empty());
    typedef std::string::iterator iter_t;
    iter_t l = s.begin(), r = s.end();
    iter_t const mid = l + s.size()/2;
    for (unsigned char mask = 1; mask; mask <<= 1) {
        iter_t const it =
            std::partition(l, r,
                           [mask](unsigned c) noexcept -> bool {
                               return c & mask;
                           });
        if (it < mid)
            l = it;
        else
            r = it;
    }
    return *mid;
}

書くのは簡単ですね。

2012-05-01

C++で円周率を取得する

Boost.Math 円周率を取得する
普通に逆三角関数を使うのがいいんじゃないでしょうか。

#include <cmath>

using std::acos;
using std::asin;
using std::atan;
using std::atan2;

int main()
{
    double const pi1 = acos(-1.0);
    double const pi2 = 3*acos(0.5);

    double const pi3 = 6*asin(0.5);
    double const pi4 = 2*asin(1.0);

    double const pi5 = 4*atan(1.0);
    double const pi6 = 2*atan2(1.0, 0.0);
}

2012-02-07

ステルスマーケティング

日本語入力を支える技術という本が今日発売されるらしいです。

2012-01-08

Perlで多倍長計算

以下の手順を踏むと、PerlでGMPを使った多倍長計算ができます。

まず Math::BigInt::GMP をインストールします。

cpan Math::BigInt::GMP

Perl スクリプトに

use bignum lib => 'GMP';

と書くと、自動的にGMPで多倍長計算されます。

整数だけ使うなら：

use bigint lib => 'GMP';

参考：
多倍長整数演算の速度比較 - まめめも
 bigint - perldoc.perl.org
bignum - perldoc.perl.org

2011-12-25

Boostの数学関数

この記事はBoost Advent Calendar 2011の参加記事です。

Boostの数学ライブラリの一部を紹介したいと思います。

複素関数としての逆三角関数・逆双曲線関数

C99の逆三角関数・逆双曲線関数を移植したものです。C++11に追加されたので、そのうち新規には使われなくなるかもしれませんが……。

逆三角関数・逆双曲線関数は多価関数なのでどういった分枝を取るかが問題になります。分枝についてBoostのドキュメントに書かれていないので明記しておきます。

arccos

$\cos^{-1}z = \frac{\pi}{2} + i \log{(iz + \sqrt{1-z^2)}$

#include <boost/math/complex/acos.hpp>

template <typename T> 
std::complex<T> acos(const std::complex<T>& z);

$[-1,1]$ 上で、実関数としての $\cos^{-1}z$ と一致し、 $\mathbb{C}\backslash ( (-\infty,-1)\cup(1,\infty) )$ で連続となるように分枝をとります。

arcsin

$\sin^{-1}z = -i\log{(iz + \sqrt{1-z^2})}$

#include <boost/math/complex/asin.hpp>

template <typename T> 
std::complex<T> asin(const std::complex<T>& z);

$[-1,1]$ 上で、実関数としての $\sin^{-1}z$ と一致し、 $\mathbb{C}\backslash ( (-\infty,-1)\cup(1,\infty) )$ で連続となるように分枝をとります。

arctan

$\tan^{-1}z = \frac{i}{2}(\log{(1-iz)} - \log{(iz + 1)}) = -i\tanh^{-1}(iz)$

#include <boost/math/complex/atan.hpp>

template <typename T> 
std::complex<T> atan(const std::complex<T>& z);

実軸上で実関数としての $\tan^{-1}z$ と一致し、 $\mathbb{C}\backslash \{iy| y \leq -1 \vee 1 \leq y\}$ で連続となるように分枝をとります。

arccosh

$\cosh^{-1}z = \log{(z+\sqrt{z-1}\sqrt{z + 1})} = \pm i \cos^{-1}z$

#include <boost/math/complex/acosh.hpp>

template <typename T> 
std::complex<T> acosh(const std::complex<T>& z);

$[1,\infty)$ で実関数としての $\cosh^{-1}z$ と一致し、 $\mathbb{C}\backslash (-\infty, 1)$ で連続となるように分枝をとります。

arcsinh

$\sinh^{-1}z = \log{(z + \sqrt{(z^2 + 1)})} = i\sin^{-1}(-iz)$

#include <boost/math/complex/asinh.hpp>

template <typename T>
std::complex<T> asinh(const std::complex<T>& z);

実軸上で実関数としての $\sinh^{-1}z$ と一致し、 $\mathbb{C}\backslash (\{iy|y \leq -1 \vee 1 \leq y\})$ で連続となるように分枝をとります。

arctanh

$\tanh^{-1}z = \frac{1}{2}(\log{(1 + z)} - \log{(1-z)})$

#include <boost/math/complex/atanh.hpp>

template <typename T>
std::complex<T> atanh(const std::complex<T>& z);

$(-1,1)$ で実関数としての $\tanh^{-1}z$
と一致し、 $\mathbb{C}\backslash ( (-\infty, -1] \cup [1, \infty) )$ で連続となるように分枝をとります。

特殊関数

Boostには特殊関数が大量にあります。数が多いので関数そのものについてはリストをあげるだけにします。

ガンマ関数
階乗と二項係数
ベータ関数
誤差関数
- 誤差関数
- 逆誤差関数
直交多項式
ベッセル関数
楕円積分
ゼータ関数
- リーマンのゼータ関数
指数積分
- 指数積分（En）
- 指数積分（Ei）
対数・冪乗・冪乗根・指数関数
- log1p
- expm1
- 立方根
- sqrt1pm1
- powm1
- hypot
- コンパイル時冪乗
sinc関数とsinhc関数
- sinc関数
- sinhc関数
逆双曲線関数
- arccosh
- arcsinh
- arctanh

ポリシー

Boostの特殊関数ライブラリでは、ポリシークラスで挙動をカスタマイズできます。ポリシーでカスタマイズできるのは

の6つです。最後の2つは特殊関数を扱う上ではほとんど関係ありません。

ポリシーを指定する方法は

の3通りあります。

マクロでデフォルトの挙動を指定するのは最も手軽な方法です。コンパイルオプションでマクロを定義することにより、ソースコードを書き換えずに挙動を変えられるというメリットがあります。しかし、異なる翻訳単位で異なる挙動を指定するとOne Definition Rule違反によりその動作は未定義となってしまうので注意が必要です。

One Definition Rule違反を気にせずカスタマイズしたい場合は、名前空間単位・翻訳単位において挙動を指定します。名前空間fooで指定したい場合は、

#include <boost/math/special_functions.hpp>

namespace foo {
typedef boost::math::policies::policy</* ポリシーの指定 */> my_policy;
BOOST_MATH_DECLARE_SPECIAL_FUNCTIONS(my_policy);
} // namespace foo

のように書きます。こうすると、例えばガンマ関数なら

foo::tgamma(1.0)

のように書くと、指定したポリシーに従った関数を使えます。

広い範囲で指定されたポリシーではなく、個々の関数で異なるポリシーを使いたい場合は、単に関数呼び出しの際に指定するだけです。

その他の数学ライブラリ

今回紹介した数学ライブラリの他に、Boostには

等のライブラリがあります。Boostの非常に充実していますので、是非ご活用ください。

2011-12-25

C++11の数学関数

この記事はC++11 Advent Calendar 2011の参加記事です。（書きかけ）

C++11には、C99の数学関数や浮動小数点数を扱う関数が追加されました。追加された関数のうち便利なものをいくつか紹介したいと思います。

C99との相違点

今回紹介する関数はC99由来のものですが、C++11への追加に際して変更があります。1つ目の変更は関数の名前です。Cでは関数のオーバーロードができないので、float用、double用、long double用の関数が別の名前を使わなければならないのに対し、C++では同じ名前で使えます。例えばC99のガンマ関数は

float tgammaf(float);
double tgamma(double);
long double tgammal(long double);

のようにfloat, long doubleのものには接尾辞が付いてしまいます。一方C++11のガンマ関数は

float tgamma(float);
double tgamma(double);
long double tgamma(long double);

のように同じ名前です。

2つ目の変更はC++の複素数クラスへの対応です。C99ではC++のstd::complexとは異なる複素数型があり、複素数を扱う関数は当然その型を受け取ります。そういった関数をそのままC++に持ってくるだけでは不便なので、std::complexに対応したC99由来の関数がC++11に追加されています。

3つ目の変更は、C99ではマクロだったものがC++11では関数になったものがあることです。

の関数

逆双曲線関数

$\cosh^{-1}x = \log{(x \sqrt{x^2-1})} (x \geq 1)$

float acosh(float);
double acosh(double);
long double acosh(long double);

$\sinh^{-1}x = \log{(x + \sqrt{x^{2} + 1})}$

float asinh(float);
double asinh(double);
long double asinh(long double);

$\tanh^{-1}x = \frac{1}{2}\log{\frac{1+x}{1-x}}$

float atanh(float);
double atanh(double);
long double atanh(long double);

誤差関数

${\rm erf}(x) = \frac{2}{\pi} \int_0^x e^{-t^2}dt$

float erf(float);
double erf(double);
long double erf(long double);

${\rm erfc}(x) = 1 - {\rm erf}(x)$

float erfc(float);
double erfc(double);
long double erfc(long double);

ガンマ関数

$\Gamma(x) = \int_0^\infty t^{x-1}e^{-t}dt(x > 0) \\ \Gamma(x+1) = x\Gamma(x)$

float tgamma(float);
double tgamma(double);
long double tgamma(long double);

$\log{|\Gamma(x)|}$

float lgamma(float);
double lgamma(double);
long double lgamma(long double);

その他の便利な数学関数

$\sqrt[3]{x}$

float cbrt(float);
double cbrt(double);
long double cbrt(long double);

$\log_2{x}$

float log2(float);
double log2(double);
long double log2(long double);

$\lfloor \log_2{x} \rfloor$

float logb(float);
double logb(double);
long double logb(long double);
int ilogb(float);
int ilogb(double);
int ilogb(long double);

fdim(x, y) = x > y ? x - y : 0

float fdim(float x, float y);
double fdim(double x, double y);
long double fdim(long double x, long double y);

fma(x, y, z) = x * y + z

float fma(float x, float y, float z);
double fma(double x, double y, double z);
long double fma(long double x, long double y, long double z);

${\rm hypot}(x, y) = \sqrt{x^2 + y^2}$

float hypot(float x, float y);
double hypot(double x, double y);
long double hypot(long double x, long double y);

${\rm scalbn}(x, n) = x * 2^n$

float scalbn(float x, int n);
double scalbn(double x, int n);
long double scalbn(long double x, int n);
float scalbln(float x, long n);
double scalbln(double x, long n);
long double scalbln(long double x, long n);

浮動小数点数の分類

bool isinfinite(float);
bool isinfinite(double);
bool isinfinite(long double);

bool isnormal(float);
bool isnormal(double);
bool isnormal(long double);

bool isinf(float);
bool isinf(double);
bool isinf(long double);

bool isnan(float);
bool isnan(double);
bool isnan(long double);

bool isunordered(float);
bool isunordered(double);
bool isunordered(long double);

int fpclassify(float);
int fpclassify(double);
int fpclassify(long double);

bool signbit(float);
bool signbit(double);
bool signbit(long double);

複素関数

リーマン球面への投影

template <typename T>
complex<T> proj(complex<T> const&);

$\cos^{-1}x = -i\log{(x + \sqrt{x^2 - 1})}$

template <typename T>
complex<T> acos(complex<T> const&);

$\sin^{-1}x = -i\log{(ix + \sqrt{1-x^2})}$

template <typename T>
complex<T> asin(complex<T> const&);

$\tan^{-1}x = \frac{1}{2i}\log{\frac{1 + ix}{1 - ix}}$

template <typename T>
complex<T> atan(complex<T> const&):

$\cosh^{-1}x = \log{(x + \sqrt{x + 1}\sqrt{x - 1})}$

template <typename T>
complex<T> acosh(complex<T> const&);

$\sinh^{-1}x = \log{(x + \sqrt{x^2 + 1})}$

template <typename T>
complex<T> asinh(complex<T> const&);

$\tanh^{-1}x = \frac{1}{2}\log{\frac{1 + x}{1 - x}}$

template <typename T>
complex<T> atanh(complex<T> const&);