あらきけいすけのメモ帳

あらきけいすけの雑記帳2

組立除法でcos, sinの3倍角,4倍角,5倍角の公式を求める

授業のための覚書*1。積和の公式*2と、3項間漸化式を組立除法*3で解けることを組み合わせることでn倍角の公式を組立除法で求めることができる:

 \begin{array}{r|llll} 次数n & 3 & 2 & 1 \\  & 1 & 0 & 0 \\\hline 2C  & & 2C  & \\ -1 & & & -1 \\\hline & 1 \ ||& 2C  & -1 \end{array}
 \therefore \cos3x = (2\cos x)(2\cos^2x-1) - \cos x \\ \hspace{3em} = 4\cos^3x - 3\cos x
 \therefore \sin3x = (2\cos x)(2\cos x\sin x) - \sin x

 \begin{array}{r|llll} 次数 n & 4 & 3 & 2 & 1 \\  & 1 & 0 & 0 & 0\\\hline 2C  & & 2C  & 4C^2 \\ -1 & & & -1 & -2C  \\\hline & 1 & 2C  \ ||& 4C^2-1 & - 2C  \end{array}
 \therefore \cos4x = (4\cos^2x - 1)(2\cos^2x -1) - 2\cos x\cos x
 \therefore \sin4x = (4\cos^2x - 1)(2\cos x\sin x) - 2\cos x\sin x

 \begin{array}{r|llll} 次数 n & 5 & 4 & 3 & 2 & 1 \\ & 1 & 0 & 0 & 0 & 0 \\\hline 2 C  & & 2 C  & 4 C^2 & 8 C^3 - 2 C \\ -1 & & & -1 & -2 C & -4 C^2 + 1 \\\hline & 1 & 2C  & 4C^2-1 \ ||& 8C^3 - 4C & -4 C^2 + 1 \end{array}
 \therefore \cos5x = (8\cos^3x - 4\cos x)(2\cos^2x-1)+( - 4\cos^2x + 1)\cos x
 \therefore \sin5x = (8\cos^3x - 4\cos x)(2\cos x\sin x) + (- 4\cos^2x + 1)\sin x

*1:チェビシェフの多項式の次数の低いものを筆算する方法:チェビシェフ多項式 - Wikipedia

*2:三角関数の公式の一覧 - Wikipedia

*3:英語では synthetic division という:Synthetic division - Wikipedia(日本語エントリはない:ホーナー法 - Wikipedia

Windows conio.h の kbhit(), getch() みたいな関数を Linux/Mac gcc で作る

授業のための覚書。コンソールでキーボード入力待ち状態を作り、入力が無い間は「idle process」を表示し、ASCII*1の印字可能文字(printable characters)のキーを押すと「[*]-key was hit」を表示し、ESCキーを押すと終了するイベント駆動型のC言語プログラム。
コード作成の目標はWindowsLinux/Macで同じ呼び出しで動作すること。
参考:linux C言語:ユーザーのライブラリを作る。makefile のテンプレート、getch(),kbhit()を例にとって。 #Linux - Qiita

#include <stdio.h>
#include <stdlib.h>
char keyData = '\0';

//----------------------------------------------
// #include <conio.h>
//----------------------------------------------
// mimic kbhit(), getch() in conio.h in Windows
#include <fcntl.h>
#include <sys/ioctl.h>
#include <termios.h>
#include <unistd.h>
char kbhit(void)
{
    struct termios old, new;
    tcgetattr(STDIN_FILENO, &old);
    new = old;
    new.c_lflag &= ~(ICANON | ECHO);
    tcsetattr(STDIN_FILENO, TCSANOW, &new);
    int oldf = fcntl(STDIN_FILENO, F_GETFL, 0);
    fcntl(STDIN_FILENO, F_SETFL, oldf | O_NONBLOCK);

    int byteswaiting = 0;
    ioctl(STDIN_FILENO, FIONREAD, &byteswaiting);
    keyData = '\0';
    if ( byteswaiting > 0 ) {
        keyData = getchar();
        fflush(stdout);
        printf("\b");
    }
      
    tcsetattr(STDIN_FILENO, TCSANOW, &old);
    fcntl(STDIN_FILENO, F_SETFL, oldf);

    return keyData;
}
char getch (void)
{
    return keyData;
}
//----------------------------------------------
//#include <windows.h>
//----------------------------------------------
// mimic Sleep() in windows.h in Windows
void Sleep (int msec) {
    int usec = msec*1000;
    usleep(usec);
}
//----------------------------------------------

int execLoop = 1;

void keyEventProc(void)
{
    keyData = getch();
    if (keyData == 27) {
        printf("\rquit by [Esc]");
        fflush(stdout);
        execLoop = 0;
    } else if (32 <= keyData && keyData <= 126) {
        printf("\r[%c]-key was hit",keyData);
        fflush(stdout);
	Sleep(1000);
    }
}

void idleProc(void)
{
    printf("\ridle process   ");
    fflush(stdout);
}

int main(void)
{
    while (execLoop) {
        if (kbhit()) {
            keyEventProc();
        } else {
            idleProc();
        }
    }
    return 0;
}

kbhit()に関するChatGPT(3.5)の回答

質問

次のLinux上のC言語プログラムについて、必要なヘッダファイルと、各行の動作について教えてください

回答

このプログラムは、キーボード入力があるかどうかをチェックするための関数を実装しています。いくつかの関数や構造体が使用されていますので、必要なヘッダファイルと各行の動作を解説しますね。

必要なヘッダファイル:

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <termios.h>
#include <fcntl.h>
#include <sys/ioctl.h>

それぞれの行の動作を解説します:

1. `struct termios old, new;`
- `struct termios`は、端末の属性を表す構造体です。`old`と`new`という名前の2つの変数を宣言しています。

2. `tcgetattr(STDIN_FILENO, &old);`
- 現在の端末属性を取得して、`old`構造体に格納しています。

3. `new = old;`
- 現在の端末属性をコピーして、`new`構造体にセットしています。

4. `new.c_lflag &= ~(ICANON | ECHO);`
- `new`構造体の `c_lflag` メンバーから `ICANON`(canonical モード)と `ECHO`(エコーバック)のビットをクリアしています。これにより、通常の入力モードやエコーバックが無効化されます。

5. `tcsetattr(STDIN_FILENO, TCSANOW, &new);`
- `tcsetattr()` 関数を使用して、変更した端末属性を適用します。

6. `int oldf = fcntl(STDIN_FILENO, F_GETFL, 0);`
- ファイルディスクリプタ `STDIN_FILENO`(標準入力)のフラグを取得して、`oldf` 変数に保存します。

7. `fcntl(STDIN_FILENO, F_SETFL, oldf | O_NONBLOCK);`
- `O_NONBLOCK` フラグをセットすることで、入力がなくてもプログラムがブロックされないようにします。

8. `int byteswaiting = 0;`
- 待機しているバイト数を格納する変数を宣言しています。

9. `ioctl(STDIN_FILENO, FIONREAD, &byteswaiting);`
- `FIONREAD` オプションを使用して、待機しているバイト数を取得します。

10. `keyData = '\0';`
- キーデータを格納する変数 `keyData` を初期化しています。

11. `if ( byteswaiting > 0 ) { ... }`
- 待機しているバイト数が0より大きい場合、キー入力があると判断しています。

12. `keyData = getchar();`
- `getchar()` を使用してキー入力を取得し、`keyData` に格納します。

13. `fflush(stdout);`
- 標準出力をフラッシュしています。

14. `printf("\b");`
- バックスペース文字を出力しています。この行は、キーボード入力を読み込んだ後、カーソルを1つ戻しています。

15. `tcsetattr(STDIN_FILENO, TCSANOW, &old);`
- プログラムの最後で、元の端末属性に戻しています。

16. `fcntl(STDIN_FILENO, F_SETFL, oldf);`
- 元のファイルフラグに戻します。

17. `return keyData;`
- キー入力データを返します。

この関数は、非同期でキーボード入力を監視し、キー入力がある場合はそのキーを返します。しかし、この関数は1回の呼び出しで1文字しか処理しません。

忘れてたので探したコマンド

Windows の cmd.exe (コマンドプロンプト)でたたく命令

  • ipconfig /all : 何がネットワークにつながっているか見る。ただしリンクローカルは相手ではなく自分のアドレスが見えている。
  • arp -a : リンクローカルアドレス(169.254.*.*)が見えているか。つないでいる相手のアドレスも探したい。
  • python -m pip install : pip install で動かないとき。

ChatGPT(無料版)に有意味な変数名と無意味な変数名のコードの解読をさせてみた

変数名を無意味化して「Pythonコードを解読」させてみた。変数名を「解読」のきっかけに使っているようだ。(まだ動作の推測をミスリードするような変数名に変える、例えば三角関数関連の名称を変数に使うとどうなるか試していない)コードはNewton法の漸化式:\displaystyle x_{k+1}=\frac{n-1}{n}x_{k}+\frac{a}{nx_{k}^{n-1}}からx_{\infty}=\sqrt[n]{a}を求めている。

これは何をするプログラムでしょうか?

def aaa ( bbb, ccc ) :
  ddd = 1
  while ccc > 0 :
    if ccc % 2 == 1 :
      ddd = ddd * bbb
    bbb = bbb * bbb
    ccc = ccc // 2
  return ddd

def eee ( fff, ggg, hhh ):
  if fff <= 0: return 0
  iii = fff
  jjj = 0
  while jjj/iii - 1 < -hhh or hhh < jjj/iii - 1:
    jjj = iii
    iii = ((ggg-1)*iii)/ggg + fff/(ggg*aaa(iii,ggg-1))
  return iii

fff = 43
ggg = 55
hhh = 1E-12
kkk= eee(fff,ggg,hhh)
print( 'kkk', kkk , aaa(kkk,ggg) )

ANSWER

このプログラムは、数学的な計算を行うものです。

関数 aaa(bbb, ccc) は、指数計算 bbb^ccc を計算するためのアルゴリズムであり、二分法を使用しています。

関数 eee(fff, ggg, hhh) は、方程式 fff = ggg * fff / (ggg-1) + fff / (ggg * (iii^(ggg-1))) を数値的に解く*1ためのアルゴリズムであり、ニュートン法を使用しています。この方程式は、 iii についての非線形方程式であり、この方程式の解が iii になります*2

このプログラムは、 fff = 43、 ggg = 55、 hhh = 1E-12 という値を使用して、関数 eee を呼び出し、 kkk という変数にその戻り値を割り当てています。そして、 kkkggg のべき乗を計算して、それらを表示しています。

このプログラムは、数学的な計算を行うため、実際に何を計算しているのかを理解するには、数学的な背景知識が必要です。

これは何をするプログラムでしょうか

def iPow ( base, exponent ) :
  power = 1
  while exponent > 0 :
    if exponent % 2 == 1 :
      power = power * base
    base = base * base
    exponent = exponent // 2
  return power

def nThRoot ( base, order, EPS ):
  if base <= 0: return 0
  root = base
  rootPrev = 0
  while rootPrev/root - 1 < -EPS or EPS < rootPrev/root - 1:
    rootPrev = root
    root = ((order-1)*root)/order + base/(order*iPow(root,order-1))
  return root

base  = 43
order = 55
EPS   = 1E-12
result= nThRoot(base,order,EPS)
print( 'result', result , iPow(result,order) )

ANSWER

このプログラムは、数学的な計算を行うためのプログラムです。

関数 iPow(base, exponent) は、指数計算 base^exponent を計算するためのアルゴリズムであり、二分法を使用しています。

関数 nThRoot(base, order, EPS) は、 base の order 次の根を数値的に解くためのアルゴリズムであり、ニュートン法を使用しています。このアルゴリズムは、 root の値を変化させていき、 root の order 乗が base に等しい場合に*3収束します。EPS は収束の閾値を表し、許容誤差を設定するために使用されます。

このプログラムは、 base = 43、 order = 55、 EPS = 1E-12 という値を使用して、関数 nThRoot を呼び出し、その戻り値を result という変数に割り当てています。そして、 result と order のべき乗を計算して、それらを表示しています。

このプログラムは、数学的な計算を行うため、実際に何を計算しているのかを理解するには、数学的な背景知識が必要です。

*1:元の式のiiiが不完全にfffにすり替わっている

*2:方程式の解が入る変数はiiiだが「この方程式の」で指示された式がマチガイなので意味が通らない

*3:目的から考えるとウソではないが、収束判定の説明としてはマチガイ

グラフの凹凸と関数の2階微分と平均値の定理

授業のための覚書。数学IIIの高校教科書、学習参考書では、y=f(x)のグラフが「上に凸」「下に凸」であることと2回微分した関数 f''(x) の正負の関係の説明が直感的なものばかりで、高校の範囲内で説明可能なのに「平均値の定理」と結び付けたものが少ないように思われる。

「傾き{\rm PQ} <傾き{\rm QR} 」と「fがなめらか」\Longrightarrow f''>0

下に凸の関数の上では線分は右に行くほど傾きが大きくなる
下に凸の関数と異なる3点を結ぶ線分の関係
\newcommand{\ss}{\small}\newcommand{\ds}{\displaystyle}関数のグラフy=f(x)が「区間[a,\,b]で下に凸」とは、a < p < q < r < bを満たす任意の \ss{\rm P}(p,\,f(p)) , \ss{\rm Q}(q,\,f(q)) , \ss{\rm R}(r,\,f(r)) で「線分\ss{\rm PQ} の傾きより線分\ss{\rm QR} の傾きが必ず大きい」こと、すなわち\ss\ds\frac{f(q)-f(p)}{q-p} < \frac{f(r)-f(q)}{r-q} である。*1
ここで\ss f(x)微分可能ならば、平均値の定理より\ss f'(c_{\rm PQ}) < f'(c_{\rm QR}) , a < p < c_{\rm PQ} < q < c_{\rm QR} < r < bとなるc_{\rm PQ}, c_{\rm QR}が存在する。ここでさらに\ss f'(x)微分可能ならば、平均値の定理より\ss f'(c_{\rm QR}) - f'(c_{\rm PQ}) = f''(c_{\rm PR})(c_{\rm QR} - c_{\rm PQ}) > 0, a < p < c_{\rm PQ} < c_{\rm PR} < c_{\rm QR} < r < bとなるc_{\rm PR}が存在する。ここでc_{\rm QR} - c_{\rm PQ} > 0なので\ss f''(C_{\rm PR}) > 0 となる。これが任意のa < p < q < r < bで成り立つので「区間\ss[a,\,b ]上でなめらかな関数\ss f(x)が下に凸になる十分条件\ss f''(x) > 0」 である。

f''>0 \Longrightarrow 傾き{\rm PQ} <傾き{\rm QR}

\ss f''(x) > 0 のときに\ss\ds\frac{f(r)-f(q)}{r-q} - \frac{f(q)-f(p)}{q-p} > 0 を証明する。証明の方針は\ss q = t r + (1-t) p (\ss 0 < t < 1)と置いて、\ss\rm Q区間\ss(p,\,r)のどこにあっても不等式がなりたつことをグラフを考察して示す。
qをこのようにおくとき\ss\ds\frac{f(r)-f(q)}{r-q} - \frac{f(q)-f(p)}{q-p} \ss\ds=\frac{f(r)-f(tr+(1-t)p)}{r-tr+(1-t)p} - \frac{f(tr+(1-t)p)-f(p)}{tr+(1-t)p-p} \ss\ds=\frac{f(r)-f(tr+(1-t)p)}{(1-t)(r-p)} - \frac{f(tr+(1-t)p)-f(p)}{t(r-p)} \ss\ds=\frac{tf(r)+(1-t)f(p)-f(tr+(1-t)p)}{t(1-t)(r-p)}
この式の分母は正の数なので、分子を\ss F(t):=tf(r)+(1-t)f(p)-f(tr+(1-t)p) と置く。この関数が\ss f''>0のときに\ss F>0となることを示す。
まず\ss F'(t)=f(r)-f(p)-(r-p)f'(tr+(1-t)p), \ss F''(t)=-(r-p)^2f''(tr+(1-t)p)である。
ここで\ss f'(x)は単調増加なので\ss f'(p) < f'(x) < f'(r)である。これらを区間\ss [p ,\, r] 積分すると\ss f'(p)(r-p) < f(r)-f(p) < f'(r)(r-p)
これより\ss F'(0)=f(r)-f(p)-(r-p)f'(p) > 0 , \ss F'(1)=f(r)-f(p)-(r-p)f'(r) < 0 となる。
\ss f''>0なので、\ss F''<0すなわちは\ss F'は単調減少。
\ss F'(0) > 0 , \ss F'(1) < 0 より\ss F(t)の増減は\ss F(0) \nearrow\searrow F(1)となる。
ここで\ss F(0) = F(1) = 0なので、F(t)>0である。

*1:ここまでは必ずしも区間全体でなめらかでなくてもいい。

C言語の文字列 char a[] char *pのふるまい

授業用のコードを書いて困惑したので、C99を読み返す。
初期化を伴う char 型の配列 char a[ ] の宣言によって a は「配列」として使える

The declaration
char s [ ] = "abc", t[3] = "abc";
defines ‘‘plain’’ char array objects s and t whose elements are initialized with character string literals.
This declaration is identical to
char s [ ] = { 'a', 'b', 'c', '\0' }, t [ ] = { 'a', 'b', 'c' };
The contents of the arrays are modifiable.
Programming languages — C, ISO/IEC 9899:TC2, p.130, §6.7.8, 下線はあらき
ところが初期化をともなう char * 型の宣言では p は「配列」としては使えない;
On the other hand, the declaration
char *p = "abc";
defines p with type ‘‘pointer to char’’ and initializes it to point to an object with type ‘‘array of char’’ with length 4 whose elements are initialized with a character string literal. If an attempt is made to use p to modify the contents of the array, the behavior is undefined.
Programming languages — C, ISO/IEC 9899:TC2, p.130, §6.7.8, 下線はあらき
以上を踏まえると、柴田, 『新・明解C言語 入門編』, SB Creative (2014) の「11-1 文字列とポインタ」 p.286ff はかなりミスリーディングに書かれているように思われる;まず初期化をともなう char 型の宣言として配列添字演算子 char s[ ] を用いると、「代入」のつもりで書かれたプログラム

//柴田(2014), p.288, List 11-2, 余計なものは消した
int main (void) {
  char s[] = "ABC";
  s = "DEF";
}

コンパイラがエラーを吐く(手元の MinGW gcc 8.1.0 のエラーメッセージは "assignment to expression with array type")なぜなら(配列 s の各要素 s[0], ... ではなく)配列 s は変更できないから*1。けれども、1文字ずつ「代入」を実行するプログラム

//my code 1
int main (void) {
  char s[] = "ABC";
  s[0] = 'D';
  s[1] = 'E';
  s[2] = 'F';
}

は「sが{'A','B','C','\0'}で初期化された配列」なので「配列の各要素への文字を代入」は期待通りに動作する。
 その一方で、初期化をともなう char 型の宣言として間接演算子 char *p を用いると、「代入(メモリ上のデータ"123"をデータ"456"で上書き)」のように見えるプログラム

//柴田(2014), p.288, List 11-3, 余計なものは消した
#include <stdio.h>
int main (void) {
  char *p = "123";
  p = "456";
  printf("%s",p);
}

はポインタ変数 p に格納されていた「文字リテラル "123" の先頭アドレス」を「(メモリ上の別の場所にいる)文字リテラル "456" の先頭アドレス」で上書きしてしまう操作なので、実行すると「456」(どこかにある '4' '5' '6' '\0')が表示される*2のだが、1文字ずつの「代入」のつもりで書いたプログラム

//my code 2
int main (void) {
  char *p = "123";
  p[0] = '4';
  p[1] = '5';
  p[2] = '6';
}

はC99の仕様書によれば「動作が定義されていない」(手元の MinGW gcc 8.1.0 では生成した実行ファイル a.exe を動かすと"a.exe は動作を停止しました"という表示を出して落ちる)。
次のコード

//my code 3
#include <stdio.h>
int main (void) {
  char *p = "123";
  printf("%c\n",p[1]);
  printf("%s\n",&p[1]);
}

では「 p は文字リテラル '1' '2' '3' '\0' の先頭アドレスの値」であるから、「p[1]は文字リテラルの2個目の要素の値を返す」ので、printf("%c\n",p[1]); は「2」を表示する。さらに「&p[1]は文字リテラルの2個目の要素のアドレスを返す」ので、printf("%s\n",&p[1]); は「23」('2' '3' '\0' すなわち2文字目から後ろの文字リテラル)を表示する。一方で

//my code 4
#include <stdio.h>
int main (void) {
  char s[] = "123";
  printf("%c\n",s[1]);
  printf("%s\n",&s[1]);
}

では「 s は char 型の配列の先頭アドレスの値」であるから、「s[1]は配列の2個目の要素の値を返す」ので、printf("%c\n",s[1]); は「2」を表示する。さらに「&p[1]は配列の2個目の要素のアドレスを返す」ので、printf("%s\n",&s[1]); は「23」(s[1], s[2], s[3], すなわち2個目から後ろの連続した配列の要素を文字リテラルとして)表示する。つまりこの2個のプログラムの動作は見た目が同じになる。
 注意すべきは char *p が配列として使えないのは「文字リテラル」で初期化した場合である。次のコード(文字列"abcde"を逆順"edcba"にする)の b は「配列のように」動作する:

//my code 5
#include <stdio.h>
#include <stdlib.h>
int getLength(char *a){int i=-1; while(a[++i]); return i;}
char *reverseString (char *a) {
  int iMax = getLength(a);
  char *b = (char*) malloc( sizeof(char) * ( iMax + 1 ) );
  if (b) {
    for( int i = 0; i < iMax; i++ ) b[i] = a[ iMax - i - 1 ];
    b[iMax] = '\0';
    return b;
  }
  return 0;
}
int main (void) {
  char *a = "abcde", *b = reverseString(a);
  if (b) {
    b[3] = 'X';
    printf("%s\n%s\n",a,b);
    free(b);
  }
}

このコードでは main() の a, b はどちらも char* 型で宣言されているが、b[3] = 'X' を a[3] = 'X' に書き換えると、とたんにコードが落ちる。

*1:A modifiable lvalue is an lvalue that does not have array type, does not have an incomplete type, does not have a const-qualified type, and if it is a structure or union, does not have any member (including, recursively, any member or element of all contained aggregates or unions) with a const-qualified type. C99 §6.3.2.1 下線はあらき

*2:アドレス情報を失った文字リテラル"123"はプログラムからアクセスできぬままメモリ上に取り残されてしまう。