Lua 5.3以降の整数型

Lua 5.3の新機能として、整数型があります。Lua 5.2まではLuaの数値は全て浮動小数点数（デフォルトでは幅64ビット・精度53ビットの倍精度）でしたが、Lua 5.3以降での数値は浮動小数点数または整数（デフォルトでは64ビット）のいずれか、となります。

Lua 5.3以降の数値型はデフォルトで浮動小数点数と整数いずれも幅64ビットですが、ビルド時に `luaconf.h` で `LUA_32BITS` マクロを定義することにより、32ビットの浮動小数点数（単精度）と整数を使用することもできます。この記事の以後の部分では、特に断らない限り数値の幅は64ビットであると仮定します。

# 符号付き整数

符号付き64ビット整数では、$-2^{63}=-9223372036854775808$ 以上 $2^{63}-1=9223372036854775807$ 以下の整数を表現できます。

## リテラル

絶対値が $2^{63}-1$ 以下の整数リテラル（小数点や指数部を持たない数値リテラル）は、整数として扱われます。絶対値がこの範囲にない場合の挙動は、Lua 5.3のマニュアルには記載がありません。

Lua 5.3.1と5.3.2では、絶対値が $2^{63}$ 以上の十進整数リテラルは、wrap aroundして64ビット整数として扱われます。

```lua
Lua 5.3.1  Copyright (C) 1994-2015 Lua.org, PUC-Rio
> 9223372036854775808
-9223372036854775808
> 9223372036854775809
-9223372036854775807
> 9223372036854775810
-9223372036854775806
> 18446744073709551616
0
```

一方、Lua 5.3.3以降では、絶対値が $2^{63}$ 以上の十進整数リテラルは、浮動小数点数として扱われます（Lua 5.4ではこの動作がドキュメント化されています）。

```lua
Lua 5.3.3  Copyright (C) 1994-2016 Lua.org, PUC-Rio
> 9223372036854775808
9.2233720368548e+18
> 9223372036854775809
9.2233720368548e+18
> 9223372036854775810
9.2233720368548e+18
> 18446744073709551616
1.844674407371e+19
```

後者の場合、符号付き64ビット整数の最小値 $-9223372036854775808$ は十進整数リテラルとして表現できないので注意してください。その値が欲しい場合は、 $-9223372036854775807$ から1を引くか、 `tonumber` を使うか、 `math.mininteger` を使います。

```lua
> -9223372036854775808
-9.2233720368548e+18
> -9223372036854775807 - 1
-9223372036854775808
> tonumber("-9223372036854775808")
-9223372036854775808
> math.mininteger
-9223372036854775808
```

一方、十六進整数リテラルは、どちらのバージョンでもwrap aroundします（Lua 5.4ではこの動作はドキュメント化されています）。

```lua
Lua 5.3.1  Copyright (C) 1994-2015 Lua.org, PUC-Rio
> 0xCAFECAFECAFECAFE
-3819392238287402242
> 0x10000000000000001
1
```

```lua
Lua 5.3.3  Copyright (C) 1994-2016 Lua.org, PUC-Rio
> 0xCAFECAFECAFECAFE
-3819392238287402242
> 0x10000000000000001
1
```

## 演算子

単項マイナス：$-2^{63}$ に対して適用した場合は、wrap aroundして $-2^{63}$ 自身が返ってきます。

`+`, `-`, `*`: 整数同士の演算でオーバーフローが起きた時は、wrap aroundします。

`/`, `^`: 常に浮動小数点数として結果を返します。

`//`: 商を $-\infty$ 方向に丸めます。つまりfloor divisionです。$-2^{63}$ `//` $-1$ を計算した場合はwrap aroundして $-2^{63}$ を返します。

`&`, `|`, 二項 `~` (xor), 単項 `~` (bitwise not): 符号付き整数を2の補数表現として扱ってビット演算を行います。

`>>`, `<<`: シフト量がビット幅を超える場合は0を返します。右シフトは左側のオペランドを符号なし整数として扱います。いわゆる論理シフトです。

算術シフトを行いたい場合は、2の冪乗による整数除算 `//` を行えば良いでしょう（63ビット以上ずらしたい場合を除く）。

（C言語をご存知の方は、符号付き整数のオーバーフローは未定義動作ではないかと思われるかもしれません。Luaの実装では未定義動作を回避するために、一旦符号なし整数にキャストしてから演算したり、オーバーフローする場合を個別に検査したりしています。）

## 定数と関数

以下の説明で、「整数値」というのは整数もしくは値が整数であるような浮動小数点数を指します。

`math.maxinteger`: 符号付き整数として表現可能な最大値です。デフォルトでは $2^{63}-1$ です。

`math.mininteger`: 符号付き整数として表現可能な最小値です。デフォルトでは $-2^{63}$ です。

`math.type`: 引数が整数なら `"integer"` を、引数が浮動小数点数なら `"float"` を返します。例：

```lua
> math.type(1)
integer
> math.type(1.0)
float
```

`math.ceil` / `math.floor` / `math.modf`: 返す値が64ビット整数で表現できるなら整数で返します。例：

```lua
> math.floor(-0.0)
0
> math.ceil(2^63)
9.2233720368548e+18
> math.ceil(-2^63)
-9223372036854775808
```

`math.tointeger`: 引数が整数値ならその値を整数に変換して返し、引数が整数値でないもしくは符号付き64ビット整数で表現できなかった場合は `nil` を返します。例：

```lua
> math.tointeger(1.0)
1
> math.tointeger(1.1)
nil
> math.tointeger(2^63)
nil
> math.tointeger(-2^63)
-9223372036854775808
```

`math.abs`: 引数が整数なら結果を整数として返します。オーバーフローを起こす場合（引数が $-2^{63}$ の場合）はwrap aroundして $-2^{63}$ を返します。例：

```lua
> math.abs(math.mininteger)
-9223372036854775808
```

`math.max`: 引数が両方整数の場合は整数を返します。両方が整数値の場合にどちらを返すかは実装依存っぽいです。

```lua
> math.max(1.0, 1)
1.0
> math.max(1, 1.0)
1
> math.min(1.0, 1)
1.0
> math.min(1, 1.0)
1
```

`string.format`: 八進表記 `%o` や十六進表記 `%x` は引数を符号なし整数として扱うので注意してください。

# 符号なし整数

時には符号なしの64ビット整数を扱いたい時があります。Luaの整数は符号付きですが、mod $2^{64}$ で考えることにより 0 以上 $2^{64}-1$ の符号なし整数と思うことができます。

## リテラル

十進リテラルはLuaのバージョン次第でwrap aroundしたり浮動小数点数になったりするので、$2^{63}$ 以上の大きな値は十六進リテラルとして表記するのが無難でしょう。

## 演算

比較演算には `math.ult` が使えます。`math.ult` は引数を符号なし整数とみなした時の `<` を返します。

```lua
> math.ult(0xFFFFFFFFFFFFFFFE, 0xFFFFFFFFFFFFFFFF)
true
> math.ult(0x7FFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF)
true
> math.ult(0x7FFFFFFFFFFFFFFF, 0x8000000000000000)
true
```

`+`, `-`, `*` はwrap aroundするのでそのまま使えます。ビット演算もそのまま使えます。

除算と剰余は一工夫必要です。[Programmin in Lua 第4版](https://www.lua.org/pil/)には除算の実装例が載っています。有償の書籍に載っているコードをそのまま貼って良いものか怪しいので、ここではアルゴリズムを載せてお茶を濁すことにします。

符号なし除算のアルゴリズム：

* $2^{63}\le d$ の場合（符号付きと解釈した時に $d$ が負の場合）
    * 符号なしで $n<d$ が成り立てば（`math.ult(n, d)` ならば）商は 0, 余りは $n$
    * そうでなければ（$d\le n<2^{64}$ ならば）商は 1, 余りは $n-d$
* $d<2^{63}$ の場合
    * 計算したい商 $q$ と余り $r$ は $q=\lfloor n/d\rfloor$, $r=n-qd$, $0\le r<d$ である。
    * 仮の商 $\hat{q}:=2 \bigl\lfloor\lfloor n/2\rfloor/d\bigr\rfloor$ を計算する。$\lfloor n/2\rfloor$ は `n >> 1` として計算でき、結果は $2^{63}$ 未満なので符号付きとして扱っても正となる。なので $d$ による除算は `//` を使って良い。
    * 真の商 $q$ と仮の商 $\hat{q}$ の間には $q-1\le \hat{q}\le q$ という関係が成り立つ。つまり、真の商と仮の商の差は高々1である。
        * 細かい証明は自分でやってほしい。$\bigl\lfloor\lfloor n/2\rfloor/d\bigr\rfloor=\bigl\lfloor\lfloor n/d\rfloor/2\bigr\rfloor$ が成り立つことに注意する。
    * 仮の余り $\hat{r}:=n-\hat{q}d$ を計算する。$\hat{q}=q$ であれば $\hat{r}=r$ なので $0\le \hat{r}<d$ が成り立ち、$\hat{q}=q-1$ であれば $\hat{r}=r+d$ なので $d\le\hat{r}<2d$ が成り立つ。
    * つまり、 $\hat{r}<d$ であれば $(q,r)=(\hat{q},\hat{r})$ で、そうでなければ $(q,r)=(\hat{q}+1,\hat{r}-d)$ である。ここで $\hat{r}<d$ は `math.ult` を使って判定する（$\hat{r}$ が $2^{63}$ 以上かもしれないので）。

これを自分で実装するのは面倒なのでJavaの `divideUnsigned` / `remainderUnsigned` みたいなやつが標準で欲しかったですね。

文字列化は `string.format` の `%u` フォーマットを使うと十進で文字列化ができます。`%o`, `%x`, `%X` も引数を符号なしとして扱ってくれます。

```lua
> string.format("%u", -1)
18446744073709551615
> string.format("%o", -1)
1777777777777777777777
> string.format("%x", -1)
ffffffffffffffff
> string.format("%X", -1)
FFFFFFFFFFFFFFFF
```

浮動小数点数への変換は、 `x % 0x1p64` でできます。絶対値が $2^{53}$ より大きい整数を浮動小数点数に変換する際は精度が失われることに注意してください。

浮動小数点数からの変換は、

* `x` が $2^{63}$ 未満であれば `math.tointeger(x)`
* `x` が $2^{63}$ 以上であれば `math.tointeger(x - 0x1p63) + 0x8000000000000000` 

と計算すれば良いでしょう。（Programming in Luaにも浮動小数点数から変換するコードが載っていますが、入力が小さい整数値の場合に精度が失われる処理になっています）