acl4の開発ログ #09
2026.03.18(水) #0
- （主に自分のために）構想の全体像をまとめておきます。
- [1]ソースコードをプリプロセッサ向きの形式に変換する（tt0003b.cのMiniCompilerの後継の関数がそれをやる）。
- これは上記に雑なサンプルがあるので、雰囲気はわかってもらえると思います。
- [2]ローカル変数・ローカルラベルなどを解決して、すべてグローバルな名前に置換する。
- 関数funcの中のabcというローカル変数なら _@func_@abc とかに置換します（置換ルールは仮のものですが、元の名前が推測できるようなものにはしたいです）。
- [3]改造プリプロセッサにより前方参照とマクロ展開をやる。
- 一時変数の型を決めるためのマクロの適用・型を決めた上での演算に対応したマクロの適用・変数の割り付けなどの処理をやる。
2026.03.18(水) #1
- ちょっと最適化が必要そうだなあと思ったところ：
Add(tmp5, s, tmp4);
Let(s, tmp5);
→ Add(s, s, tmp4);
Add(tmp3, j, 1);
Let(j, tmp3);
→ Add(j, j, 1);
Add(tmp1, i, 1);
Let(i, tmp1);
→ Add(i, i, 1);
- このレベルの最適化だけをぱぱっとやってしまうレイヤ（＝関数）を作ればいいのかな？
2026.03.18(水) #2
- 自分用にアイデアメモ：
- まず変数 i が、 Int:memstk+1234 に変換される。
- Add(i, i, ConstInt:1); が Add_IntMemstk_IntMemstk_ConstInt(1234, 1234, 1); に変換される。
- Mov_RS(EAX,1234); Add_RI(EAX,1); Mov_SR(1234,EAX); に変換される。Sは[ESP+disp]の意味。
2026.03.26(木) #0
- 大変唐突ですが、変数宣言とかしなくてもデフォルトで有理数型を標準的に扱える言語処理系が欲しくなりました（笑）。
- （いや本気で作るわけではないです。ネタです。）
- たぶんここまでで作ったものを生かせば簡単に作れるはず。
- よし今日はそれで遊ぼう！
2026.03.26(木) #1
- Python のライブラリに limit_denominator というメソッドがあるのをさっき知りました。
- 浮動小数点数を与えると、指定した分母の範囲で一番近い有理数を探し出して答えてくれます。
- これはいいなと思いました。これが使えるなら、普段はdoubleで計算しておいて、答えを出すときに有理数に直せばいいからです。
- それなら有理数型はなくても平気です。
- しかもこの関数があれば、sqrt(2)とか円周率とかに対して、適当な有理数で近似するとしたら何がいいのか、みたいな遊びにも使えます。
2026.03.26(木) #2
- とりあえず、こんなプログラムを書いてアルゴリズムが正しいか確認してみました。
// tt0004a.c
#define a_Version 1
#include <acl4.c>
int64_t limit_denominator_sub(int64_t *ary, int n, int64_t *pb)
// nは配列の長さではなく、それよりも1小さい数を渡す. つまり ary[n]が最後のデータ.
{
int i;
int64_t a = ary[n], b = 1, t;
for (i = n - 1; i >= 0; i--) {
t = ary[i] * a + b;
b = a;
a = t;
}
*pb = b;
#if 0
printf("n=%d [", n);
for (i = 0; i <= n; i++) printf("%d ", (int) ary[i]);
printf("] %d/%d\n", (int) a, (int) b);
#endif
return a;
}
int64_t limit_denominator(double x, int64_t bMax, int64_t *pb)
{
if (x == 0.0) { *pb = 1; return 0; }
int sign = 1, i;
if (x < 0.0) { sign = -1; x *= -1.0; }
int64_t ary[1024], a = 0, b = 0, ta, tb;
for (i = 0; i < 1024; i++) {
ary[i] = (int64_t) x;
ta = limit_denominator_sub(ary, i, &tb);
if (tb > bMax) break;
a = ta; b = tb;
if (i == 1023) break;
x -= (double) ary[i];
if (x < 1e-12) break;
x = 1.0 / x;
}
*pb = b;
return a * sign;
}
int main()
{
int64_t a, b;
double x = 3.14159265358979323;
a = limit_denominator(x, 10, &b); printf("%d/%d\n", (int) a, (int) b);
a = limit_denominator(x, 100, &b); printf("%d/%d\n", (int) a, (int) b);
a = limit_denominator(x, 1000, &b); printf("%d/%d\n\n", (int) a, (int) b);
x = sqrt(2);
a = limit_denominator(x, 10, &b); printf("%d/%d\n", (int) a, (int) b);
a = limit_denominator(x, 100, &b); printf("%d/%d\n", (int) a, (int) b);
a = limit_denominator(x, 1000, &b); printf("%d/%d\n\n", (int) a, (int) b);
x = exp(1);
a = limit_denominator(x, 10, &b); printf("%d/%d\n", (int) a, (int) b);
a = limit_denominator(x, 100, &b); printf("%d/%d\n", (int) a, (int) b);
a = limit_denominator(x, 1000, &b); printf("%d/%d\n\n", (int) a, (int) b);
return 0;
}
// 実行結果
>tt0004a
22/7
22/7
355/113
7/5
99/70
1393/985
19/7
193/71
1457/536
- とりあえずそれっぽく動いているので、アルゴリズムは悪くなさそうです。
- このアルゴリズムを一応説明しておくと、与えられた実数を連分数形式に変換して、それを有理数に直して返しています。
- なぜこのアルゴリズムにしたのかというと、計算量が少なそうに思えたからです。
2026.03.26(木) #3
- ということでこれで行けそうと思ったのですが、このページの結果とは少し違っていました。
- https://note.nkmk.me/python-fractions-usage/#pie
- 違うのは、円周率に対して、 print(pi.limit_denominator(100)) をしたときに、 311/99 を返してくれるところです。 tt0004a.c だと 22/7 の次は 333/106 で、その次が 355/113 なので、 311/99 は出てこないのです。
- それ以外の結果は一致しています。
- つまり Python は違うアルゴリズムを採用しているのだと思います。
2026.03.26(木) #4
- この結果を踏まえると、 Python と同じ結果を出すことを頑張るのではなく、少し仕様を変えようと思います。分母の最大値を渡すのではなく、「分母がこの値を超えたら打ち切る」つまり最大値ではなく最小値を渡す感じにしようと思います。
// tt0004b.c
int64_t limit_denominator2(double x, int64_t bMin, int64_t *pb)
{
if (x == 0.0) { *pb = 1; return 0; }
int sign = 1, i;
if (x < 0.0) { sign = -1; x *= -1.0; }
int64_t ary[1024], a, b;
for (i = 0; i < 1024; i++) {
ary[i] = (int64_t) x;
a = limit_denominator_sub(ary, i, &b);
if (b >= bMin || i == 1023) break;
x -= (double) ary[i];
if (x < 1e-12) break;
x = 1.0 / x;
}
*pb = b;
return a * sign;
}
- そもそもは、「無理数をいい感じに近似できる有理数を探す」ことではなく、「真値は有理数なのだけど、浮動小数点演算のせいで多少の誤差があり、それを乗り越えて真値である有理数を求めたい」ということなのです。だから打ち切り条件を厳密に守るために演算量が増えるのは本意ではないのです。
- と思ったのですが、 limit_denominator2() は実用的ではないとわかりました。
- たとえば総当たり方式で解を探すと、 3x=1 に対する仮の答えとして x=0.33 とかが得られるかもしれません。
- ここから有理数に戻そうと limit_denominator2(10) とかすると、 33/100 になってしまうのです。まあ当然ですよね。
- これに対して、 limit_denominator(99) なら正しく 1/3 が得られます。
2026.03.26(木) #5
こめんと欄
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
