ときどきの雑記帖 RE* (新南口)
PHS
「PHS」Print/Hanko/Scan
という略語があるらしいですが、某社内にあふれているような (頭としっぽに深い関係があるからか?🤔)。
gdtoa
Not only is the Internet dead, it’s starting to smell really bad.:2021年04月09日分
あれ、githubにgdtoaのリポジトリあったような…と思い手元のメモ(not bookmark)から飛んでみると、 名前(と元々の中身)はそうでも別の人のものだった jwiegley/gdtoa: David M. Gay’s floating-point conversion library。
せっかくなので(謎)昨年dtoa.cを調べた(読んだ)ときにメモっていたリンクをダンプしておく。 リンクを集めたきっかけはこの辺。
- 0.1は浮動小数点で正確に表せないのに、printしたときに0.1と表示されるのはなぜか - Qiita
- [B! プログラミング] 0.1は浮動小数点で正確に表せないのに、printしたときに0.1と表示されるのはなぜか - Qiita
以下順不同で、
IEEE 754 doubleを文字列に変換するアルゴリズム? - 初心者向けチュートリアル
解決した方法 # 1
- 浮動小数点数を文字列表現に変換するためにさまざまなソフトウェア環境で使用されるコードは、通常、次の出版物に基づいています(Steel and Whiteの研究は特に頻繁に引用されています):
- Jerome T. Coonen:「浮動小数点演算の標準案の実装ガイド。」コンピュータ、Vol。 13、No。1、1980年1月、68~79ページ
- Guy. L. Steele Jr.およびJ. L. White:「浮動小数点数を正確に印刷する方法」。プログラミング言語の設計と実装に関するACM SIGPLAN ‘90会議の議事録、ホワイトプレーンズ、ニューヨーク、1990年6月、pp.112-126
- David M. Gay:「正しく丸められた2進10進および10進2進変換。」テクニカルレポート90-10、AT&Tベル研究所、1990年11月。
- 関連するフォローアップ作業:
- Robert G. BurgerとR. Kent Dybvig:「浮動小数点数をすばやく正確に印刷する」プログラミング言語の設計と実装に関するACM SIGPLAN 1996会議の議事録、ペンシルベニア州フィラデルフィア、1996年5月、pp.108-116
- Guy L. Steele Jr.およびJon L. White:「回顧:浮動小数点数を正確に印刷する方法」ACM SIGPLAN Notices、Vol. 39、No.4、2004年4月、372~389ページ
- Florian Loitsch:「整数を使用して浮動小数点数を迅速かつ正確に印刷します。」2010 ACM SIGPLAN Conference on Programming Language Design and Implementationの議事録、カナダ、オンタリオ州トロント、2010年6月、pp.233-243
- Marc Andrysco、Ranjit Jhala、およびSorin Lerner:「浮動小数点数の印刷:より高速で常に正しい方法」ACM SIGPLAN Notices、Vol. 51、No.1、2016年1月、pp.555-567
- Ulf Adams: “Ryu:高速なfloatから文字列への変換。“ACM SIGPLAN Notices、Vol. 53、No.4、2018年4月、pp.270-282
Printing Floating-Point Numbers
References
If you’re interested in more details on the subject, these are the primary set of papers.
- How to Print Floating-Point Numbers Accurately by Steele and White in 1990
- The link actually points to a retrospective on the original paper from 2003 followed by the original 1990 document.
- Correctly Rounded Binary-Decimal and Decimal-Binary Conversions by Gay in 1990
- Printing Floating-Point Numbers Quickly and Accurately by Burger and Dybvig in 1996
- Printing Floating-Point Numbers Quickly and Accurately with Integers by Loitsch in 2010
If you’re okay with using code with a less permissive license, these are the correct implementations I’ve been able to find.
- dtoa.c
- Written by David Gay (author of one of the above papers), this seems to be the accepted safe implementation. It has been iterated on since 1991 and is used in everything from Python to MySQL to the Nintendo Wii.
浮動小数点数の書き出し 参考: Guy L. Steele Jr. and Jon L. White, “How to Print Floating-Point Numbers Accurately”, in the Proceedings of ACM SIGPLAN ‘90, pp.112-126, 1990.
Robert G. Burger and R. Kent Dybvig, “Printing Floating-Point Numbers Quickly and Accurately”, PLDI ‘96, pp.108–116, 1996.(2002/04/06 02:29:05 PST) 素直にBurger&Dybvigを実装してみた(number.c, v1.75)が…
(2002/04/06 02:40:26 PST) あ、嘘。rounding modeをちゃんと考慮してなかった。 直した(number.c, v1.76)らちゃんと動いた。
Daily Julia #1 - Moriturus te saluto
Julia ではこれまでマクロによって C++ の実装を叩いていただけであったが、 このたび pure Julia による実装が書かれたということで実にめでたいというお話でした。
- 浮動小数点数の10進指数表示のアルゴリズム-WentWayUp
- Default float formatting is too narrow-minded · Issue #24556 · rust-lang/rust · GitHub
- ryu/ryu at master - ulfjack/ryu - GitHub
- Printing Floating-Point Numbers
- numpy/dragon4.c at master - numpy/numpy - GitHub
- Printing Floating-Point Numbers - Part 2: Dragon4
- Printing Floating-Point Numbers - A Faster, Always Correct Method
- GitHub - abolz/Drachennest: Different algorithms for converting binary to decimal floating-point numbers
- Errol/dragon4.c at master - marcandrysco/Errol - GitHub
- Dragon4 and Grisu3: algorithms to display floating point numbers
- ぼくのかんがえたさいきょうのround関数 - hnwの日記
- How to Print Floating-Point Numbers Accurately (1990) [pdf] | Hacker News
正規表現の文字クラスで]を置くには
awkをプログラミング言語として使う時の技術 - Qiita に
各 awk の処理系の互換性
(略)
BusyBox awk では正規表現の扱いで以下のような違いを見つけました。上の正規表現では [ ] の中にエスケープしても ] を書くことが出来ません。 こちらはバグっぽい気がします。二番目の正規表現は { を量指定子の開始と認識されています。 他の実装では量指定子として不正な場合 { はただの文字として扱われるのに対して BusyBox はエラーとして扱われます。 こちらは未定義による動作の違いではないかと推測しています。
というのがあった。
二番目の「ペアになっていない{
」をどう扱うかは覚えてないけど、
一番目のは「大昔はみんな(ってなんですか)そうだった」という仕様ですね。
文字クラス中で\
を使ったエスケープができるようになったのってPerl辺りからの気がするけど(要確認)、
それにしたってもう「かなりの過去」の話ですな(ひー)。
せっかくなので(謎)busybox のソースをちょっと眺めてみると、awkの正規表現リテラルの解釈はこの辺ですかね
awk.c\editors - busybox - BusyBox: The Swiss Army Knife of Embedded Linux
static void mk_re_node(const char *s, node *n, regex_t *re)
{
n->info = OC_REGEXP;
n->l.re = re;
n->r.ire = re + 1;
xregcomp(re, s, REG_EXTENDED);
xregcomp(re + 1, s, REG_EXTENDED | REG_ICASE);
}
xregcompはbusybox内にある関数でこんな感じ
xregcomp.c\libbb - busybox - BusyBox: The Swiss Army Knife of Embedded Linux
char* FAST_FUNC regcomp_or_errmsg(regex_t *preg, const char *regex, int cflags)
{
int ret = regcomp(preg, regex, cflags);
if (ret) {
int errmsgsz = regerror(ret, preg, NULL, 0);
char *errmsg = xmalloc(errmsgsz);
regerror(ret, preg, errmsg, errmsgsz);
return errmsg;
}
return NULL;
}
void FAST_FUNC xregcomp(regex_t *preg, const char *regex, int cflags)
{
char *errmsg = regcomp_or_errmsg(preg, regex, cflags);
if (errmsg) {
bb_error_msg_and_die("bad regex '%s': %s", regex, errmsg);
}
}
ここで regcomp やregerrorという関数が出てきているけど、 これはシステムのものかあるいは別に用意したライブラリのものを使うようだ。
$ tar tfv busybox-1.32.1.tar.bz2 | grep 'reg'
-rw-r--r-- 0 root root 768 1 01 19:52 busybox-1.32.1/libbb/xregcomp.c
-rw-r--r-- 0 root root 678 1 01 19:52 busybox-1.32.1/include/xregex.h
となると実際に使ったライブラリが何かということにもかかわってくるので、 深追いするのは止めて規格方面に「転進」する。
本来ならきちんとPOSIXのそれを追いかけるべきなんだろうけど あれは有料だったりと色々事情があるので Regular Expressions からひくことでご勘弁を賜りたく。
で、
9.3.5 RE Bracket Expression
A bracket expression (an expression enclosed in square brackets, “[]” ) is an RE that shall match a single collating element contained in the non-empty set of collating elements represented by the bracket expression.
The following rules and definitions apply to bracket expressions:
- A bracket expression is either a matching list expression or a non-matching list expression. It consists of one or more expressions: collating elements, collating symbols, equivalence classes, character classes, or range expressions. The right-bracket ( ‘]’ ) shall lose its special meaning and represent itself in a bracket expression if it occurs first in the list (after an initial circumflex ( ‘^’ ), if any). Otherwise, it shall terminate the bracket expression, unless it appears in a collating symbol (such as “[.].]” ) or is the ending right-bracket for a collating symbol, equivalence class, or character class. The special characters ‘.’, ‘*’, ‘[’, and ‘\’ (period, asterisk, left-bracket, and backslash, respectively) shall lose their special meaning within a bracket expression.
If a bracket expression specifies both ‘-’ and ‘]’, the ‘]’ shall be placed first (after the ‘^’, if any) and the ‘-’ last within the bracket expression.
つまりはそういうことです。
mawk
脱線その1。
正規表現(の仕様)とは直接関係ないけど、mawkの1.3.3では
/[/]/
と書くとブラケットの中の/
を正規表現リテラルの終端と解釈してしまって
エラーになるという「仕様」だったはず(/
に\\
を前置して回避できる)。
あるときこれを「バグだよね?」と作者(Mike Brennan)にメールで問い合わせたことがあるんだけど 「オリジナルのawkもその動作じゃボケ」(チョー訳) という返事が返ってきたなあ(遠い目)。 実際(少なくとも当時のオリジナル == One True Awkは)そうだったんだけど。
mawkに関してもう少し脱線すると いくつかのディストリビューションでは mawk の1.3.4(or greater?) というものが入っているのだけど、 実はこれ元々の開発者であるMike Brennan以外の開発者が(Mike が最後にリリースしていた1.3.3をベースに)作ったもので Mike Brennan 自身は無関係であり、そのことに関して彼は不満を表明してたりする。
その一方で、 ploxiln/mawk-2: Mike Brennan’s new development of his original “mawk” - https://github.com/mikebrennan000/mawk-2 なんてのもあるんだけどこれがまたリポジトリが作られてから絶賛放置中。
I first released mawk 1.0 in 1991 and last released mawk 1.3.3 in 1996. (A few people had mawk 1.3.3.1 with nextfile, 1999.)
Why a 25 and 20 year anniversary release? Because I always knew a few things could be done better and design decisions that were right for the 90’s were wrong for 21st century.
In my absence, there have been other developers that produced mawk 1.3.4-xxx. I started from 1.3.3 and there is no code from the 1.3.4 developers in this mawk, because their work either did not address my concerns or inadequately addressed my concerns or, in some cases, was wrong.
って、あれ、↑のリポジトリmike本人のものじゃないな?
mikebrennan000/mawk-2: A beta release of mawk 2.0.0, derived from mawk 1.3.3 がたぶん本人のものだ。置かれているのがtar玉とpdfだけだけど。
GNU regex
脱線その2。
前述のopengroupの記事を検索したときに下位の方で自分の書いた(訳した)ものが引っかかっていた。
今はgawkなどでもglibcの中にある別実装のもの (正確には Gnulib - GNU Portability Library - GNU Project - Free Software Foundation) が使われているし、消しちゃおうかねえ。
いつ頃書いたものだっけかと確認すると
This document was generated on 28 如月 1998 using the texi2html translator version 1.47.
うはは。前世紀のものだった。
なお、翻訳元のドキュメントのリリースは1992年だったりする。
grepを忘れただけなのに
最近の人気記事から。
「事故」の本筋とは関係ないところで気になった点。
- grepの引数(検索パターン)をクォートしないの?
- なんなら検索パターンに -e オプション付けるよ?
- (ls -l の結果を確認するのに)less (or more or pg) 使わないの?
「なぜそうしないのか(こうすれば事故を防げた)」という指摘(糾弾)ではなく、単なる疑問。
まあシェルのコマンドライン上の引数を律儀にクォートしている人を、特に最近はあまり見かけない気もするしなあ (観測範囲の問題?)。
あと、grepで検索しようとしているのに grep
を入力し忘れたというのを認識できなくて、
「なんでいきなりシェルに食わせてるんだろう」と悩んでしまったのはここだけの話。
たとえばファイルをリストアップして対象を消すなんてときにスクリプト(やバッチファイル)を sedやawkで生成して実行するなんてことは自分もたまにやっているので、 その種の作業でミスったのかと思ったのね。