Help us understand the problem. What is going on with this article?

[Rust] 整数型のべき乗の引数はなぜ u32 なのか

Rust の整数型のべき乗の引数はすべて u32 になっています (例えば u64::pow であってもべき指数は u32 で指定する, ちなみに浮動小数点数の powii32). これはなぜか, という StackOverflow での jdborg 氏の質問 Why does Rust's u64.pow expect a u32?trentcl 氏が丁寧な回答を寄せていたので全訳します. StackOverflow の投稿って CC BY-SA なんですね (そして Qiita に CC BY-SA を投稿できる).

要約すると, (1) べき乗はハードウェアサポートがないので引数を同じ型に揃えなければならないというハードウェア的要求がない, (2) 引数に 64 bit も取るのは無駄である (そんなに大きなべきを計算しても u64 で表せる範囲に収まらない), (3) とはいえ 8 bit や 16 bit まで小さくしてもご利益がないので 32 bit がちょうど良かろう. という趣旨のことを述べています.

trentcl 氏の回答の全訳

なぜたいていの演算では引数は同じ型なのか?

人間にとっては 2i32 + 2i644i64 になるべきなのは明らかです. しかし, CPU にとっては 2i322i64 は完全に異質でまったく関係のないものに見えます. CPU の中では足し算はハードウェア的に実装されていて, たいてい「2 つの 32 bit 数の入力」または「2 つの 64 bit 数の入力」をサポートしています. ですから i32i64 を足すためには, その値を演算装置に入れる前に i32 を 64 bit 数へと変換する必要があるのです.

一般に同じことがほとんどの整数および浮動小数点数の算術に当てはまります. 異なる型の間で演算を行うには型変換が必要なのです. C言語では通常コンパイラがすべてのオペランド (算術演算の引数) がともに同じ型を持つように bit 数を拡張します. この暗黙の型変換は文脈に応じて「汎整数拡張」 (integer promotion) あるいは「通常の算術変換」 (usual arithmetic conversion) と呼ばれます. ところが Rust ではコンパイラは同じ型の演算しか扱えないため, 人間がオペランドの変換方法を指定することでどのような演算をしてほしいのか選ぶ必要があります. Rust を好んでいる人はこのことを良いことだと考える傾向にあるようです (注1).

なぜそれが u64::pow に当てはまらないのか?

ハードウェアで実装されているものも含め, すべての算術演算が同じ型の引数を受け付ける訳ではありません. シフト演算は引数のビット数を上回った部分はしばしばハードウェア的に無視されます (これはC言語で整数のサイズより大きなシフト操作が未定義動作を引き起こす理由です). LLVM が提供する powi 演算は浮動小数点数の整数べきを計算します.

これらの演算は入力が非対称という点で他の演算とは異なっていて, 設計者はこの非対称性を利用してハードウェアを速くかつ小さくします. u64::pow に関して言うと, これはハードウェア的に実装されていないのです. この関数は std 内で Rust により実装されています. このことを考慮すれば, 指数部分に u64 はまったく必要ないということは明らかでしょう. Schwern の回答で指摘されているように, 正確な答えが期待される u64 のべきは u32 の範囲で十分なのであり, 余計な 32 bit は意味がないのです.

それで, なぜ u32 なのか?

この最後の主張は u16u8 であっても成立するでしょう. つまり, u64 は 2 の 255 乗ですら表せないので, 指数部には u8 で十分であり u32 でさえ無駄に大きな bit を持っていることになります. ただ, 次のことを考慮する必要があります. 多くの呼び出し規約ではレジスタに関数の引数を渡すようにしていて, なので 32 bit (かより大きい) プラットフォームではそれより小さな bit を用いる利点は見当たらないでしょう. 多くの CPU は 8 bit や 16 bit の算術もネイティブサポートしていないため, exponentiation-by-squaring アルゴリズムを実装する際には, 引数に先に述べたような 32 bit への拡張を行う必要があります. 私は u32 が選ばれた理由そのものを知っている訳ではないのですが, 標準ライブラリの設計時にこれらのことが考慮されたのだろうと思います.

注1: C言語の規則は過去の経緯, そして古いハードウェアを含む広い範囲の機器をサポートするということに制約されています. Rust は LLVM だけをターゲットとしているため, コンパイラは対象のハードウェアが 8 bit プリミティブの加算機構を持っているかどうかを考える必要がありません. Rust は単に 8 bit の足し算を呼ぶだけでよく, LLVM がプリミティブ演算にコンパイルすべきか 32 bit 演算で 8 bit 演算をエミュレートすべきかどうかを判断します. これが C 言語では char + charint であるのに Rust では i8 + i8i8 である理由です.

ライセンス表記

「trentcl 氏の回答の全訳」節の内容は trentcl 氏が CC BY-SA 4.0 ライセンスのもとで https://stackoverflow.com/a/57120777 にて 2019-07-20 に英語で公開したものを日本語訳したものです. ライセンスに従い, 本記事もまた CC BY-SA 4.0 ライセンスとします (©osanshouo 2020-01-14).

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away