C言語では malloc は初期化されていない

どうしても計算があわず1時間悩んだが

malloc の説明を十分読まずに使ってしまったが, malloc は各要素の値が 0 である保証はない.すべての値を 0 にしたい場合は calloc (clear allocation)を使う.勝手な思い込みはバグの元だ.

size_t* buffer = malloc(len * sizeof *buffer);

の代わりに

size_t* buffer = calloc(len, sizeof *buffer);

C言語で巨大な配列を確保するときは malloc を使う

10^7の要素数をもつ配列を用意しようとしたら

#include <stdio.h>
#include <stdlib.h>

enum { max_number = 10000000 };

int main(int argc, char* argv[argc+1]) {
  size_t numbers[max_number] = { 0 };
  return EXIT_SUCCESS;
}

これを実行しようとすると Segmentation fault: 11 になってしまった.スタック領域のサイズは限られているため巨大な配列を扱うことができない.巨大な配列を使いたい場合は malloc/free を使う.

#include <stdio.h>
#include <stdlib.h>

enum { max_number = 10000000 };

int main(int argc, char* argv[argc+1]) {
  size_t* numbers = malloc(max_number * sizeof *numbers);
  free(numbers);
  return EXIT_SUCCESS;
}

malloc はヒープ領域に確保され,スタック領域よりも大きなオブジェクトも扱うことができる.

きょうの作業記録:JavaScript関連インストール

フロントエンドは詳しくない.ここ数年でガラッと環境が変わっている.全くキャッチアップできていないが,基本的なツールのインストールをしたのでメモしておく.覚えること多くて初学者は大変な気がする.

anyenv / nodenv

anyenv - All in one for **env | anyenv.github.io

環境の切り替えができるように,anyenvを導入する.anyenvはさまざまな環境切り替えツール(*env)を管理するツール.

$ brew install anyenv
$ anyenv init
$ echo 'eval "$(anyenv init -)"' >>  ~/.bash_profile
$ anyenv install --init

nodenvをインストールしておく.

$ anyenv install nodenv
$ exec $SHELL -l

Node.js

Node.js
本家サイトの指示にしたがって,インストールしてもいいが,複数のバージョン,パッケージ構成を管理したいため,nodenv経由でインストールする.

# 利用可能なバージョン一覧を確認
$ nodenv install -l
$ nodenv install 10.16.1
# シェル全体のバージョンを設定
$ nodenv global 10.16.1

ESLint

ESLint - Pluggable JavaScript linter

$ npm install eslint --save-dev

webpack

webpack

$ npm install webpack --save-dev
$ npm install webpack-cli --save-dev

TypeScript

TypeScript - JavaScript that scales.
Microsoft製のJavaScriptの拡張.静的型付けがある.

$ npm install typescript --save-dev
$ ./node_modules/typescript/bin/tsc greeter.ts 

Babel

Babel · The compiler for next generation JavaScript
JavaScriptコンパイラ.ブラウザが対応していないようなECMAScript 2015以降の文法で書いて,古い文法に変換するときに使う.

npm install --save-dev @babel/core @babel/cli @babel/preset-env

Redux

fluxアーキテクチャを推し進めたもの.

$ npm install --save redux

React

Next.js

Jens Gustedt『Modern C』(レベル2まで)を読んで

ポインター

double のオブジェクト d0 と d1を入れ替える double_swap という関数を使って考える.

double_swap(&d0, &d1);

アドレス演算子 & を使うことで,アドレスを通してオブジェクトにアクセスできる.アドレス演算子が返す型はポインター型とよばれ,* をつけて表す.関数定義の中ではポインター p0 と p1 がオブジェクトのアドレスになる.オブジェクトを参照するためにオブジェクト演算子 * をつけて,*p0 や *p1 のように使う.

通常,「間接参照演算子」(indirection operator)とよぶが,著者は「オブジェクト演算子」(object-of operator)というようだ.

void double_swap(double* p0, double* p1) {
  double tmp = *p0;
  *p0 = *p1;
  *p1 = tmp;
}

ポインターを使わずに書くこともできて,それは以下のようになる.

void double_swap(double p0[static 1], double p1[static 1]) {
  double tmp = p0[0];
  p0[0] = p1[0];
  p1[0] = tmp;
}

ポインターは有効,ナル,または不定の状態しかない.ナルまたは不定ポインターに * を使ったときのふるまいは未定義である.不定の場合は,メモリー上のランダムなオブジェクトを書き換えてしまい追跡の難しい不具合の原因になる.ナルの場合は,プログラムがクラッシュする.

double sum0(size_t len, double const* a) {
  double ret = 0.0;
  for (size_t i = 0; i < len; ++i) {
    ret += *(a + i);
  }
  return ret;
}

これは次のように書き直すことができる.

double sum1(size_t len, double const* a) {
  double ret = 0.0;
  for (double const* p = a; p < a+len; ++p) {
    ret += *p;
  }
}
double sum2(size_t len, double const* a) {
  double ret = 0.0;
  for (double const*const aStop = a+len; a < aStop; ++a) {
    ret += *a;
  }
  return ret;
}

レベル1で触れられていたが const の説明を見ると, const 修飾子を左結合として書く.

char const* const path_name;

最初の constchar にかかり, * は char const 型のポインターであり, 2つ目の constchar const 型のポインターにかかる. const 修飾子は名前が紛らわしいが定数をつくるためのものではなく,読み込み専用にするためのものである.

ポインターから元の配列の長さを知ることはできない.ポインターに対しては sizeof 演算子は使えない.だから,関数には配列の長さを渡して上げる必要がある.したがって,ポインターと配列はちがうということを覚えておく.

そこで,著者は以下のようにポインターインターフェイスとして配列を使う方法を好んでいる.

double sum0(size_t len, double const a[len]);
double sum1(size_t len, double const a[len);
double sum2(size_t len, double const a[len]);

これで配列の長さとして len が必要ということがわかりやすくなる.

ポインターに適切なオブジェクトがないときは 0 で初期化しておく.ポインターの差は2つのポインターが同じ配列の要素を指しているときのみ求めることができる.

double A[4] = { 0.0, 1.0, 2.0, -3.0, };
double *p = &A[1];
double *q = &A[3];
assert(p-q == -2);

これまでサイズを表す型として size_t 型を使ってきたが,ポインターの差に対しては専用の型 ptrdiff_t を使う.

構造体とポインターに関しては割愛.

つぎに,ポインターと配列の関係をくわしく見る. A[i] と *(A+i) は同じである.ここで, A はポインターでも配列でもよい. A が配列のとき, *(A+i) は配列からポインターへの劣化(decay)という.一般的な日本語訳はあるのかな.配列からポインターになると配列に関する情報が失われる.

ここまで NULL というマクロを使ってこなかった. NULL はCの標準で明確に規定されておらず,Cのコンパイラは以下のいずれかの値を使う.

展開
0U unsigned
0, '\0', 0(enum) signed
0UL unsigned long
0L signed long
0ULL unsigned long long
0LL signed long
(void*)0 void*

一般的なのは 0 ,0L , (void)* 0 である.著者はまずは NULL を使わないようにしようと主張している. NULL はプラットフォーム依存であり,熟知していないプラットフォームで使うのは危険である(具体的はセクション17で触れる).ポインターと明記したいのであれば, (void*)0 を使えばよい.

関数ポインターについて.始まりの括弧のない関数 f は関数の始まりに対するポインターに劣化(decay)する.

typedef void atexit_function(void);
// 同等の2通りの定義
typedef atexit_type* atexit_function_pointer;
typedef void (*atexit_function_pointer)(void);
// 同等な5通りの宣言
void atexit(void f(void));
void ateixt(void (*f)(void));
void atexit(atexit_function f);
void atexit(atexit_function* f);
void atexit(atexit_function_pointer f);

さすがにわかりにくい. stdlib.h では探索の bsearch ,ソートの qsort などが関数ポインターを引数としてとる.

typedef int compare_function(void const*, void const*);

void* bsearch(void const* key, void const* base,
              size_t n, size_t size,
              compare_function* compar);
void qsort(void* base,
           size_t n, size_t size,
           compare_function* compar);

操作する対象は base である.ポインターvoid 型なので型の情報がすべて失われてしまう.そこで,各要素の大きさを size で,配列の長さを n で受けている.

int comapare_unsigned(void const* a, void const* b) {
  unsigned const* A = a;
  unsigned const* B = b;
  if (*A < *B) return -1;
  else if (*A > *B) return +1;
  else return 0;
}

ソートするときはこのように, a が b よりも小さいならば負を,a が b よりも大きいなら正,等しいならば 0 を返す関数を渡す.カプセル化して使うとよい.

extern int compare_unsigned(void const*, void const*);

inline
unsigned const* bsearch_unsigned(unsigned const key[static 1],
                 size_t n, unsigned const base[nmeb]) {
  return bsearch(key, base, nmeb, sizeof base[0], compare_unsigned);

inline
void qsort_unsigned(size_t n, unsigned base[nmeb]) {
  qsort(base, nmeb, sizeof base[0], compare_unsigned);
}

bsearch (二分探索)は key[0] と等しいものを探しなければナルポインターを返す. base は比較する関数によりソートされていることを前提に処理される.比較の関数の呼び出しは \lceil \log_{2}(n) \rceil を超えない. bsearch は探している要素が見つかるとその要素へのポインターを返すが, const がついていない.そこでこの例のように, unsigned const* に変換して返している.

Cのメモリーモデル

union を使いメモリ上の順序を調べる話も面白いが割愛.

double blub(double const* a, double* b);

int main(void) {
  double c = 35;
  double d = 3.5;
  printf("blub is %g\n", blub(&c, &d));
  printf("after blub the sum is %g\n", c + d);
}

定義のわからない blub 関数があったとする.関数のなかで引数がどうなったかわからない.とくに, d がどうなったかがわからないし, c + d がどうなるか不明である.たとえば,定義は以下だったとする.

double blub(double const* a, double* b) {
  double myA = *a;
  *b = 2*myA;
  return *a;
}

見たところ, myA と同じ値が返されるように見えるがどうだろうか.実は同じ引数を与えると,つまり blub(&c, &c) の場合,*b を変えると *a も書き換わってしまう.このように,同じオブジェクトを異なるポインターでアクセスすることをエイリアス(別名)という.エイリアスは最適化を妨げる原因になる.エイリアスを避けるために, & 演算子を避けた方がよい.

どんなオブジェクトのポインターvoid* から変換することができるし, void* に変換することができる. void* にすると型の情報がなくなるため, void* は避けた方がいい.

暗黙の型変換と明確な型変換.

unsigned big = -1;

この場合, int の -1 が unsigned の UINT_MAX に変換されている.

unsigned char highC = 1;
unsigned high  highU = (highC << 31); // 未定義のふるまい

単純に見えるが実は罠がある.1行目はよいが,2行目の右辺に問題がある.狭い整数型は算術計算の前に変換される.ここでは, int に変換され左シフト演算が行なわれる.31ビットシフトすると最上位のビット,つまり符号のビットになってしまう.このようなことを避けるため,算術をするときは算術のできる型を選ぶ.狭い整数型は限られた状況だけで使えばよい.たとえば,メモリを節約するとき.数百万や数十億の長さの小さい数の配列を扱うときなどである. char 型を使うのは文字か文字列を扱うときだけであって,それ以外では使うべきではない.
ポインターの型変換はさらに注意が必要になる.

float f = 37.0;         // float への変換
double a = f;           // double に戻す変換
float* pf = &f;         // 同じ型
float const* pdc = &f;  // 修飾子の追加
void* pv = &f;          // void* への変換
float* pfv = pv;        // void* からの変換
float* pd = &a;         // エラー
double* pdv = pv;       // 使用した場合,ふるまいは未定義

pd への代入はコンパイル時にエラーになる.しかしながら, pdv への代入は文法上は正しいためエラーにならない.キャストにより型変換をコンパイラに強制することができるが,たいていはコンパイラのエラーの方がただしく,キャストを使わないといけない場合はそもそもの設計に誤りがあると考えたほうがよい.したがって,キャストは使うべきではない.

割当て,初期化,破壊

増えていくデータに対し,必要に応じて,ストレージを確保する方法として動的メモリー割当てがある. stdlib.h には以下のような関数が用意されている.

#include <stdlib.h>
void* malloc(size_t size);
void free(void* ptr);
void* calloc(size_t nmemb, size_t size);
void* realloc(void* ptr, size_t size);
void* aligned_alloc(size_t alignment, size_t size);

malloc でメモリーを確保し(memory allocateに由来), free で解放できる.ほかの3つの関数は malloc の特別なバージョンになる. calloc はclear allocateに由来し,すべてのビットを 0 で確保する. realloc はオブジェクトを増やしたり減らしたりすることに使う.

size_t length =livingPeople();
double* largeVec = malloc(length * sizeof *largeVec);
for (size_t i = 0; i < length; ++i) {
  largeVec[i] = 0.0;
}
...
free(largeVec);

malloc の引数では sizeof *largeVec のようにポインターの型を渡すことができる.このようにすることで,あとで largeVec の型が変わったとしても, malloc の引数を変更せずに使える.

double* largeVec = malloc(sizeof(double[length]));

のように書くこともできる. malloc の戻り値をキャストする必要はない.キャストすると問題の原因になる. stdlib.h をインクルードし忘れたとき,昔のCコンパイラーでは戻り値として int を想定するので,誤った型変換が発生し,クラッシュを引き起こす.

/* stdlib.h をインクルードし忘れた場合 */
int malloc();
...
double* largeVec = (void*)malloc(sizeof(double[length]));

malloc は確保に失敗するとナルポインターを指すのでチェックする.また,malloc により確保されたメモリーは初期化されていないので,初期化すること.

この後も結構内容があるが,ひとまずここまで.

Jens Gustedt『Modern C』(レベル1まで)を読んで

Jens Gustedtの『Modern C』を読んだ感想をメモ.

f:id:sujimodern:20190716190800j:plain
ケン・トンプソン(写真左)とデニス・リッチー(写真右)

size_t の多用

初学者には int ではなく, size_tを使うことを勧めている.size_t は[0, SIZE_MAX]の範囲から外れないからだ.なお,SIZE_MAXは,stdint.hで定義されている.符号なし整数型は桁溢れ(オーバーフロー)すると時計のように元に戻って,決して範囲から外に出ることがない. size_t なら%(SIZE_MAX+1)を計算したのと同じ結果になる.

基本の型

大分類 小分類 システム上の名前 別名
整数 符号なし _Bool(注) bool
unsigned char(注)
unsigned short(注)
unsigned int unsigned
unsigned long
符号付き・なし char(注)
符号付き signed char(注)
signed short(注) short
signed int signed or int
signed long long
signed long long long long
浮動小数 実数 float
double
long double
複素数 float _Complex float complex
double _Complex double complex
long double _Complex long double complex

(注)は算術計算ができない.計算するときは昇格する.C言語の標準では,型の精度については定めておらず,実装に依存している.
文字列リテラルは続くと,結合されるというのは知っておくと便利だ.

puts("first␣line\n"
     "another␣line\n"
     "first␣and␣"
     "second␣part␣of␣the␣third␣line");

数値リテラルを記述するには,10進整数(123),8進整数(077),16進整数(0xFFFF,大文字小文字は区別しない),10進浮動小数点(1.7E-13),16進浮動小数点(0x1.7aP-13)がある.豆知識として, 0 は8進整数である.数値リテラルは常に正である.-34,-1.5E-23と書いてあっても,正の数にマイナスの演算子がかかっているだけで,負の数ではない.そのいっぽうで,10進整数リテラル自体は signed になっている.どの型になるかはもっとも適切な型が採用される.たとえば,あるプラットフォームで signed の最小値が -215 = -32768 ならば, 32768 は範囲外なので, signed long が採用される.これからわかるように, -32768 という数は signed long である.つまり,ある符号付き型の最小値は決してその型のリテラルで書くことができない.16進整数リテラルはもう少し複雑である.符号付き型にあわない場合は,符号なしの型になる.先ほどの例を使うと 0x7FFF は 32767 なので, signed である.いっぽうで, 0x8000 つまり 32768 は unsigned になる.もちろん, -0x8000 も unsignedである.負の数を表す場合は,10進整数リテラルを用いるのが好ましい.
また,型を明記することもできる.U,L,LLをつけることでそれぞれの型を明示できる.1U は unsigned だし,1L は signed longだし, 1ULL は unsigned long long である.C言語において, 0 は特別な値であり,0,0x0,'\0' はすべて等価で, signed intである.実は0を10進整数リテラルで記述することはできない.
異なるリテラルでも同じ値であることがある.浮動小数点は,端数部は切り取られるか丸められているので,近似値でしかない.たとえば, 0.2 と 0.2000000000000000111 は同じ値である.さいごに,浮動小数点も末尾に記号を書くことで型を明記できる.F は float, L は long double, 何もなければ double になる.

初期化

あらゆる変数は初期化されるべきである.数値型は,そのまま値を代入すればいい.初期化子の波括弧{ }で囲んでもよい.

double a = 7.8;
double c = { 7.8 };

その他の型は初期化子{ }で囲む.配列の長さが明記されていない場合は,初期化のタイミングで決定される.

double A[] = { 7.8, };

ある型 T の初期化の仕方がわからなければ,デフォルト初期化子 T a = { 0 }を使えばよい.

2進表現

非負の整数については,2進数で表現するだけである.b0,b1,…,bp-1が0または1の値(ビットという)があるとすると,
\displaystyle \sum_{i=0}^{p-1} b_{i}2^{i}
のように表現できる.ここで, p を精度という.この式からわかるように,ある型の最大値は,2p-1 であり,ある型で2pは表現できない.
ビット集合とビット演算について.ビット集合は,ビット表現のうち1であるもののiをとった集合であり,{0, ..., p-1}の集合Vの部分集合である.ビット演算には,|,&,^がある.それぞれ,集合の和A∪B,集合の積A∩B,集合の対称差A△Bである.

ビット演算 16進数 b15...b0
V 65535 0xFFFF 1111111111111111
A 240 0x00F0 0000000011110000
~A 25295 0xFF0F 1111111100001111
-A 65296 0xFF10 1111111100010000
B 287 0x011F 0000000100011111
A|B 511 0x01FF 0000000111111111
A&B 16 0x0010 0000000000010000
A^B 495 0x01EF 0000000111101111

またシフト演算というのもある.左シフト演算子<<は2の冪乗するのと同じになる.A = 240 なら, A << 2 は 240・22 = 240・4 = 960 である.ビット集合から外れたものは無視される.だから, A << 9 は, {13, 14, 15, 16} (値は122880)だが,16番目のビットはないので, {13, 14, 15} (値は57344)になる.つまり,シフト演算をするときは,精度より小さい必要がある.同様に右シフト演算子>>は2の冪乗で割るのと同じになる.
ブール値については, stdbool.h をインクルードすることで, bool 型が使える.定数は false または true である.ただし,初期のC言語にブール値がなかったため,熟練のCプログラマーはこれらの値を使わない.
つぎに,負の整数の2進表現はどうか.負の場合は,正の場合は0,負の場合は1になる符号ビットがある.負数を表現する方式はいくつかあり,C言語では3種類(符号と大きさ,1の補数,2の補数)が認められているが,現代では2の補数を使う以外使われていない.
Cの標準では,最小の精度しか規定されていないので.これだと不便なことがあるので,正確に精度を保証する型が stdint.h にある. uintN_t 型はN ビットでかつ精度もNである符号なし整数である.同様に, intN_t 型はNビットでかつ精度が N - 1 の符号あり整数である.リテラルを特定の型に変換するためのマクロがあり,たとえば, uint64_t が unsigned long のプラットフォームでは, INT64_C(1) は 1UL に変換される.
最後に浮動小数点についてみる.浮動小数点でも整数同様に最大値,最小値の定数がある. float.h を読み込めば,たとえば, double については DBL_MAX と DBL_MIN が使える.ただし, DBL_MIN は 0.0 よりも大きい最小の値であり, double の最小値は, -DBL_MAXである.実数を現実のシステムで表現するのは難しい.というのも,実数のなかには無限小数など数字が終わらないものもあるからだ.そこで,C言語をはじめとしたプログラミング言語では,小数の展開をある時点で打ち切る.展開を打ち切る位置が流動的(floating)なので,浮動小数点(floating point)という.まず以下のような記号を定義すると

記号 内容
s 符号(±1)
e 指数部
f1...fp 0 or 1,仮数部のビット

浮動小数点は次にように計算できる.
\displaystyle s \cdot 2^{e} \cdot \sum_{k=1}^{p} f_{k} 2^{-k}
精度p や e の範囲は型に依る.マクロを使えば知ることができて, DBL_MANT_DIG (通常,53),DBL_MIN_EXP (-1021), DBL_MAX_EXP(-1024)である.たとえば,s = -1 , e = -2 , f1 = 1 , f2 = 0 , f3 = 1 ならば,
\displaystyle -1 \cdot 2^{-2} \cdot ( f_{1} 2^{-1} + f_{2} 2^{-2} + f_{3} 2^{-3} ) = -1 \cdot \frac{1}{4} \cdot ( \frac{1}{2} + \frac{1}{8} ) = -1 \cdot \frac{1}{4} \cdot \frac{4 + 1}{8} = \frac{-5}{32}
である.浮動小数点の計算は都度打ち切るので,数学でいう結合法則,交換法則,分配法則のいずれも満たさない.そのため,大きさが極端に異なる数同士を操作する際に問題が生じる.たとえば, -p 乗よりも小さい浮動小数点 x に y > 1 を加えると,結果は y になる.したがって,浮動小数点の値が近いかどうか言うことはできても,等しいとは決して言うことできない.

複合データの型

その他の型は基本的な型を寄せ集めたものである.配列,ポインター,構造体,共用体がある.ポインターは込み入っているため議論を後に回す.共用体は現代では特定の分野でしか用いられることがなくCのメモリーモデルを熟知している必要があるのでここでは省く.
著者はここで,ポインターを導入せず配列の説明を試みている.また,配列はポインターではないことを強調している.
配列の配列を作ることができ,これを多次元配列という.

double C[M][N];
double (D[M])[N];

CもDも double[N] 型のオブジェクトがM個ある配列である.配列の演算は特徴的である.まず,配列を条件式で評価すると true になる.これは array decay に由来する.配列には,固定長配列(fixed length array,FLA)と可変長配列(variable length array,VLA)がある.FLA はC言語の初期からあるが,VLA は C99 で導入されたものでいくつか制約がある.VLA は初期化子を持つことができず,関数の外で宣言することもできない.FLA の長さは整数定数式(integer constant expression,ICE)または初期化子により決定される.配列の長さが指定されない場合は,初期化時に決定される.その他の配列は VLA である.配列 A の長さは (sizeof A / sizeof A[0]) である.
文字列は0終端された char の配列である."hello" は目に見える文字以外に 0 という値があるので,配列の長さは 6 である. string.h ヘッダーには char の配列や文字列を扱う関数が用意されている.配列を扱う関数はmemはじまり,文字列を扱う関数はstrはじまりである.

関数 説明
memcpy(target, source, len) 配列を別の配列にコピー
memcmp(s0, s1, len) 2つの配列を比較.先頭からチェックして異なるときは値の差を返す
memchr(s, c, len) 配列sの中に文字cがあるか検索する
strlen(s) 文字列sの長さを返す.0までの長さを返すだけで配列の長さではない
strcpy(target, source) sourceの長さだけコピーする
strcmp(s0, s1) s0またはs1どちらかの0終端まで比較する
strchr(s, c) 文字列sから文字cを検索する

文字列関数を文字列以外で使った場合のふるまいは未定義である.strlen のプロトタイプ宣言は以下のようになる.

size_t strlen(char const s[static 1]);

static 1はC99から導入された書き方で,少なくとも長さが1ある配列を意味している.また,memcpy のプロトタイプ宣言は

void* memcpy(void* target, void const* source, size_t len);

である. void* は未知の型に対するポインターだがくわしくはレベル2で扱う.

不透明型(opaque types)としてのポインター

ポインターは,有効,ナル,または不定(indeterminate)のいずれかの状態をとる.ナルは 0 であり,false になる.0 による初期化や代入により,ポインターはナルになる.ナル状態にあるポインターをナルポインターとよぶ.ポインターの評価はナルのときだけ, false として扱われる.したがって,このような方法では有効なポインター不定ポインターを区別することはできない.不定ポインターはやっかいなのである.不定ポインターにより未定義のふるまいになる.これを避けるために,常にポインターは初期化することを心がける.

構造体と typedef の話は割愛.

関数

Cライブラリ関数

Cライブラリ関数では,特別な戻り値で失敗を示す.

if (puts("hello world") == EOF) {
  perror("can't output to terminal:");
  exit(EXIT_FAILURE);
}

このように,ファイルの終わり(end-of-file)を意味するEOFでチェックすることがある.C言語では,errno という変数を使ってエラーの状態を保持することがある.
数学関連の関数は math.h にある.ただし,型ジェネリックである tgmath.h に比べ単純な関数である.型ジェネリックでありば,引数の型を調べ,その型と同じ型の戻り値を返す.現代の数学の関数は,効率的で精度に気を配って実装されている.プロセッサーにある sqrt や sin の近似値を計算したりする命令を使っていることもある.十分な知識なく自分で実装すべきではない.
ファイルに出力するときはストリーム用に FILE* という型を使い,以下のような関数を使う.

int fputc(int c, FILE* stream);
int fputs(char const s[static 1], FILE* stream);

ストリームにはあらかじめ stdout と stderr が用意されている.通常の出力は stdout に行ない,緊急のものは stderr にする.
ファイルに書き込む場合は, fopen を使う.

FILE* fopen(char const path[static 1], char const mode[static 1]);
FILE* freopen(char const path[static 1], char const mode[static 1], FILE *stream);

使用例は以下.

int main(int argc, char* argv[argc + 1]) {
  FILE* logfile = fopen("mylog.txt", "a");
  if (!logfile) {
    perror("fopen failed");
    return EXIT_FAILURE;
  }
  fputs("feeling fine today\n", logfile);
  return EXIT_SUCCESS;
}

この perror は stderr に fputs するようなものである.モードと修飾子(modifier)というのがある.

モード 意味 fopen 後の状態
'a' append w ファイルはそのままで末尾に位置
'w' write w ファイルの中身を消去
'r' read r ファイルはそのままで先頭に位置
修飾子 意味 属性
'+' update rw 読み込み,書き込み用に開く
'b' binary バイナリーファイルとして開く
'x' exclusive ファイルが存在しなければ作成する

ほかに, freopen , fclose , fflush という基本的な関数がある. freopen はすでにあるストリームに別のファイルを結びつけるために使う.
通常,テキストの出力はバッファーされる.物理的に書き込むことを遅らせることでリソースを効率化するのである. fclose でストリームを閉じると, flush させる(書き出させる). fflush は任意のタイミングで出力するときに使う.バッファーは行バッファーされることが多い.つまり,行末に達したときに出力する.そのため, fputs のように1行を出力する関数だと即座に出力され,バッファーされていることがわからない.
出力のフォーマットについて.これまで printf を使ってきたが,ストリームに書き込む fprintf というのもある.

int printf(char const format[static 1], ...);
int fprintf(FILE* stream, char const format[static 1], ...);

末尾の...は任意の引数を取れることを示している.ただし, '%' 指定子(specifier)と同じ数だけで,それ以外の場合のふるまいは未定義である.フォーマット指定子は %[FF][WW][.PP][LL]SS という仕様になっている.それぞれ,フラグ,幅,精度,修飾子,指定子である.

記号 説明
FF フラグ
WW 最小の幅
PP 精度
LL
SS 指定子.出力の形式を選択
形式 説明
'd' or 'i' 10進数 signed integer
'u' 10進数 unsigned integer
'o' 8進数 unsigned integer
'x' or 'X' 16進数 unsigned integer
'e' or 'E' [-]d.ddd e±dd floating point
'f' or 'F' [-]d.ddd floating point
'g' or 'G' eまたはf floating point
'a' or 'A' [-]0xh.hhhh p±d floating point
'%' %
'c' 文字 integer
's' 文字列 string
'p' アドレス void* pointer
記号 意味
"#" 0xをつける
"0" ゼロ埋め
"-"
" " 正なら' '負なら'-'
"+" 正なら'+'負なら'-'

文字の入力には 1文字では fgetc 文字列には fgets を使う.かつては puts に対応した gets があったが,安全ではないため,現在では使われていない.fgetc はエラーやファイルの最後で EOF を返す.本当にファイルの末尾かどうかを確認するには feof を使う.

文字列の関数についても一部割愛.Cでは文字列から数値に変換するのに, strtod , strtoul , strtol ,strtoumax , strtoimax , strtoull , strtoll , strtold , strtof がある.u は unsigned だし, l は long , d は double ,f は float を表す. [i|u]max は intmax_t と uintmax_t である.

unsigned long int strtoul(char const nptr[restrict],
                          char** restrict endptr,
                          int base);

3番目の引数 base で基数を指定することができる.ここでは,0,8,10,16が使える.0はその他3つのいずれかで,"7"なら10進数,"007"なら8進数,"0x7"なら16進数として解釈する.2番目の引数は残りのデータの位置を示すために使われるが,まだ(ポインターの)説明をしていないので,さしあたり0を渡す.

時刻に関する話も割愛.

プログラムの終わり方について. main 関数は return で終わらせる. main 関数の中で exit を使う理由はない( return を使えばよい).

反省

メモ書きからはじめたのだが,面白く,覚えておきたいポイントが多かったので部分訳のようになってしまった.引用と感想が混ざってしまったことを反省.書き方については改善したい.

フェルマーの定理(『代数系入門』より)

f:id:sujimodern:20190706211331j:plain
Pierre de Fermat(1607 - 1665)
ある集合Sについて,Sの元の対がa \sim bで表される関係が定義されており,次の3の条件が満たされるとき,それを同値関係という.
ER1 任意のa \in Sに対し,a \sim a.(反射律)
ER2 a \sim bに対し,b \sim a.(対称律)
ER3 a \sim bかつb \sim cならば,a \sim c.(推移律)
いま集合Sにおいて,同値関係\simが与えられているとすると,Sのある元aに対し,a \sim xとなるようなSの元xの集合をaの類という.Sは,同値関係によって,互いに交わらないいくつかの類に分割することができる.この分割を類別といい,類に属する元を代表という.
mを正の整数とする.a, bを整数とするとき,a - bmで割り切れるならば,a, bmを法として合同であるといい,
\displaystyle
a \equiv b \pmod m
と書く.この関係は整数\mathbb{Z}において同値関係である.mを法とする合同関係による\mathbb{Z}の類は法mに関する剰余類とよばれる.法mに関するm個の剰余類からそれぞれ1つずつ代表をとって作ったm個の整数の組を,法mに関する完全剰余系という.たとえば,0, 1, \cdots, m -1は完全剰余系である.
補題D mを正の整数とし,(a, m) = 1とする.x_1, \cdots, x_mを法mに関する完全剰余系とすると,ax_1, \cdots, ax_mも法mに関する完全剰余系である.
証明 ax_i \equiv ax_j \pmod mなるi, j(i \neq j)があるとすると,ax_i - ax_j = a(x_i - x_j)である.いま(a, m) = 1なので,(x_i - x_j)mで割り切れる.すなわち,x_i \equiv x_j \pmod mとなる.しかしながら,これは仮定に反する.ゆえに,a_x1, \cdots, ax_mは法mに関する完全剰余系である.□
ここでオイラーの関数\varphi(n)を導入する.\varphi(n)は,任意の正の整数nに対し,1, 2, \cdots, nの中でnと互いに素であるものの個数である.たとえば,\varphi(1) = 1, \varphi(2) = 1, \cdots, \varphi(8) = 4である.剰余類に関していえば,法nに関するある剰余類の代表がnと互いに素であれば,その剰余類に属するすべての元も互いに素である.このような剰余類を法nに関する既約剰余類とよぶことにすると,\varphi(n)は法nに関する既約剰余類の個数ということができる.既約剰余類から1つずつ代表をとって作った\varphi(n)個の組を,法nに関する既約剰余系という.
補題F m \gt 0として,(a, m) = 1とする.x_1, \cdots, x_l(l = \varphi(m))が法mに関する既約剰余系ならば,ax_1, \cdots, ax_lも法mに関する既約剰余系である.
証明 補題Dにより,ax_1, \cdots, ax_lは法mに関して互いに合同ではない.さらに,仮定からax_iはすべてmと互いに素である.ゆえに,示された.□
定理12(オイラーの定理 m > 0とし,(a, m) = 1ならば,
\displaystyle
a^{\varphi(m)} \equiv 1 \pmod m
が成り立つ.
証明 x_1, \cdots, x_l(l = \varphi(m))を法mに関する既約剰余系とする.補題Fからax_1, \cdots, ax_lも法mに関する既約剰余系である.これはx_1, \cdots, x_lを適当に並び替えたx_{\pi(1)}, \cdots, x_{\pi{l}}とそれぞれ法mに関して合同である.ただし,\pi(1), \cdots, \pi(l)は適用な順列を表すものとする.
\displaystyle
\begin{eqnarray}
ax_1 &\equiv& x_{\pi(1)} \pmod m \\
ax_2 &\equiv& x_{\pi(2)} \pmod m \\
\cdots \\
ax_l &\equiv& x_{\pi(l)} \pmod m
\end{eqnarray}
それぞれの合同式の両辺を掛け合わせると,
\displaystyle
a^{l} x_1\cdots x_l \equiv x_{\pi(1)} \cdots x_{\pi(l)} = x_1 \cdots x_l \pmod m
を得る.x_1 \cdots x_lmと互いに素なので約すことができる.したがって,a^{l} = a^{\varphi(m)} \equiv 1 \pmod mが示された.□
とくに,m素数pのとき,次に系が得られる.
系(フェルマーの定理) p素数かつ(a, p) = 1ならば,
\displaystyle 
a^{p - 1} \equiv 1 \pmod p
では,プログラムに書き起こしてみる.p = 11, a=8のばあい.

Fermat's little theorem

ユークリッドの互除法(『代数系入門』より)

f:id:sujimodern:20190706122857j:plain
エウクレイデス(紀元前3世紀ごろ?)
a_{1}, \cdots, a_{n}の最大公約数を(a_{1}, \cdots, a_{n})で表す.
補題B 整数a,bの差a - bm(\neq 0)で割り切れるならば,(a, m) = (b, m)である.
証明 a - bmで割り切れるので,a - b = mqとおける.変形すると,a = b + mqまたはb = a - mqである.したがって,b, mの公約数はaの約数であり,同時にa, mの公約数はbの約数である.つまり,b, ma, mの公約数の全体は一致する.とくに,その公約数の最大のものは等しい.□
つぎに,補題Bを使って,正の整数a, bの最大公約数を求める手続きを導く.いま,a > bと仮定して,次のような系列を考える.
\displaystyle
\begin{eqnarray}
a &=& bq_1 + r_2, \quad 0 \lt r_2 \lt b \\ 
b &=& r_2 q_2 + r_3, \quad 0 \lt r_3 \lt r_2 \\
r_2 &=& r_3 q_3 + r_4, \quad 0 \lt r_4 \lt r_3 \\
\cdots \\
r_{n-2} &=& r_{n-1} q_{n-1} + r_{n}, \quad 0 \lt r_{n} \lt r_{n-1} \\
r_{n-1} &=& r_n q_n
\end{eqnarray}
この系列におけるb, r_2, r_3, \cdots, r_nは減少数列で,高々b個しかないので,必ず割り切れる.補題Bより,
\displaystyle
(a, b) = (b, r_2) = (r_2, r_3) = \cdots = (r_{n-2}, r_{n-1}) = (r_{n-1}, r_{n})
なので,(r_{n-1}, r_{n})の最大公約数が(a, b)の最大公約数である.いまr_{n}r_{n-1}を割り切るから,(r_{n-1}, r_{n}) = r_{n}であり,(a, b) = r_{n}になる.この手続きをユークリッドの互除法という.
では,これをプログラムに書き下してみよう.

Euclidean algorithm in c