TypeScript の型システムで10進任意精度整数を扱うライブラリを作りました

最近Type-Challenges をやってみています。TSKaigiのスライドをXで見かけて触発されたためです。¹
現在はMedium までは全問完了して、HardとExtreme をつまみ食いしている状態です。

問題を進めていくうちに、整数を扱う問題が何度か出てきて、毎回同じような型定義を書くのが面倒になってきました。
「もういっそのことライブラリ作ってやろう」ということで、TypeScriptの型システムだけで任意精度の10進整数演算を行うライブラリを作ってしまいました。

モチベーション

TypeScript で整数の演算を扱う最も簡単な方法は、タプル型の長さを使って整数を表現することです。

type THREE = [0, 0, 0]
type FIVE = [0, 0, 0, 0, 0]
type EIGHT = [...THREE, ...FIVE]

const eigth: EIGHT['length'] = 8

このように、タプル型の長さを使って整数を表現することで、整数の演算を行うことができます。

ただし、このようなタプルでは、10桁20桁にもなるような大きな整数を扱うことができません。
実際、このようなタプルを再起的に生成しようとした場合は Typescript のジェネリクスの再帰の深さ制限に引っかかってしまいます。²

そこで、0~9 を要素に持つタプルを使って10進整数を表現することで、任意精度の整数を扱うことができるようにしました。

type THIRTY_FIVE = [3, 5]
type FOURTY = [4, 0]

ライブラリの概要

このライブラリの特徴は以下の通りです：

• コンパイル時演算: 実行時ではなく、TypeScriptのコンパイル時に計算が完了
• 任意精度: JavaScriptの数値制限を超えた大きな整数の演算が可能
• ゼロランタイム: 実行時のオーバーヘッドが一切なし
• 型安全: 全ての演算結果が型レベルで保証

使用例

// 使用例
type Sum = Add<123, 456>;        // 579
type BigSum = Add<"999999999999999999", "1">;  // "1000000000000000000"

これを使えば、例えば以下のような Type-Challenges の整数問題が簡単に解けてしまいます。

476 - Sum

import type {Add} from '../int-base10'

type Sum<
  A extends string | number | bigint,
  B extends string | number | bigint
> = `${Add<A, B>}`

/* _____________ テストケース _____________ */
import type { Equal, Expect } from '@type-challenges/utils'

type cases = [
  Expect<Equal<Sum<2, 3>, '5'>>,
  Expect<Equal<Sum<'13', '21'>, '34'>>,
  Expect<Equal<Sum<'328', 7>, '335'>>,
  Expect<Equal<Sum<1_000_000_000_000n, '123'>, '1000000000123'>>,
  Expect<Equal<Sum<9999, 1>, '10000'>>,
  Expect<Equal<Sum<4325234, '39532'>, '4364766'>>,
  Expect<Equal<Sum<728, 0>, '728'>>,
  Expect<Equal<Sum<'0', 213>, '213'>>,
  Expect<Equal<Sum<0, '0'>, '0'>>,
]

27133 - Square

import type { Mul } from '../int-base10'
type Square<N extends number> = Mul<N,N>

/* _____________ テストケース _____________ */
import type { Equal, Expect } from '@type-challenges/utils'

type cases = [
  Expect<Equal<Square<0>, 0>>,
  Expect<Equal<Square<1>, 1>>,
  Expect<Equal<Square<3>, 9>>,
  Expect<Equal<Square<20>, 400>>,
  Expect<Equal<Square<100>, 10000>>,
  Expect<Equal<Square<101>, 10201>>,

  // Negative numbers
  Expect<Equal<Square<-2>, 4>>,
  Expect<Equal<Square<-5>, 25>>,
  Expect<Equal<Square<-31>, 961>>,
  Expect<Equal<Square<-50>, 2500>>,
]

実装のポイント

以下では、このライブラリの実装のポイントを簡単に説明します。

基本的なデータ構造

整数の内部表現には {p: DIGIT[], n: DIGIT[]} という形式を採用しました。

この表現方法については後ほど詳しく説明します。

type IntBase10Type = {
  // 正と負のどちらかの部分はゼロ(空配列)である
  p: DIGIT[]  // 正の部分
  n: DIGIT[]  // 負の部分
}

// 例
// 10 → {p: [1, 0], n: []}
// -32 → {p: [], n: [3, 2]}
// 0 → {p: [], n: []}

この表現方法については後ほど詳しく説明します。

加算の実装

加算の実装では、実際のコンピューターで使われている全加算器の概念を10進数に適用しました。

減算の実装

減算は補数を使って実装しました。ただし、2進計算で一般的な2の補数ではなく、10進数での9の補数を使用しています。

$$
X - Y = X \, +\, (\,\underbrace{999\ldots9}_{n} - Y\,) \, - \, 1\underbrace{000\ldots0}_{n} \,+\, 1
$$

ただし、n はYの桁数です。
ここで、$(999\ldots9 - Y)$ はYの補数です。これは、繰り下がりが発生しないため、単に各桁を9から引くことで求められます。
あとは、Xのインクリメントとn+1桁目におけるデクリメントを実装すれば実現できます。

このように、和とインクリメント、デクリメントを組み合わせることで減算を実装しています。

乗法と除法

乗算は小学校で習う筆算と同じアルゴリズムを使用しています。
多桁数 × 1桁数の計算を基本単位として、各桁ごとに計算した結果を適切に桁をずらして加算することで、完全な乗算を実現しています。

除算は長除法（ちょうじょほう）と呼ばれる、これも小学校で習う筆算の割り算と同じアルゴリズムを使用しました。
反復減法により各桁の商を求め、余りを次の桁に持ち越すという処理を再帰的に行っています。

負の数の表現方法

負の数の表現については、一般的な「仮数部分 + 符号ビット」ではなく、数学において自然数から整数を構成する方法に近いアプローチを採用しました。

数学では、自然数から整数を構成する際に $(a,b) \in \mathbb{N} \times \mathbb{N}$ という自然数の組で $a-b$ に対応する整数を表し、これらの(a,b)の組みのうち、同じ整数を表すものを同一視することで整数を構成する流儀があります。

正確にいうと、自然数の直積 $\mathbb{N} \times \mathbb{N}$ を、以下の同値関係 $\sim$ によって商集合に分けることで整数を定義します：

$$
\begin{align}
(a,b) \sim (c,d) \iff a+d = b+c \\
\end{align}
$$

これらの「同じ整数を表す(a,b)の組」（同値類）の中から aまたはbの少なくともどちらか一方が0であるものを代表元として選ぶことで、

• $(a,0)$ で正の数 $+a$ を表現
• $(0,b)$ で負の数 $-b$ を表現
• $(0,0)$ でゼロを表現

というように、整数を自然数の組で表現することができます。

このアプローチの利点としては、以下の2点が挙げられます：

1. +0と-0の区別が不要: どちらも $(0,0)$ として表現される
2. 演算の統一: 要素ごとに演算した後に「代表元を取る」操作を行うことで足し算や引き算を実装できる

ただし、2. については、実際の実装では代表元を取る操作（比較1回 + 減算1回）が重い処理になってしまうため、結局は符号ごとに場合分けを行うことになり、あまり意味がなかったかもしれません。

今後の展開

このライブラリは現状では整数のみを扱っていますが、今後は以下のような拡張が考えられます：

• 固定小数点や浮動小数点の演算を追加することで、より実用的な数値計算が可能になります。
• 内部表現を16進数に変更することで、暗号化やハッシュ関数などの実装も型レベルで行えるようになったら面白いかもです。

また、Type-Challanges は文字列の問題も多いので、正規表現ライブラリにも挑戦してみようかなと思いました

まとめ

TypeScriptの型システムだけで10進任意精度整数演算を実装しました。
実用性はともかく、「TypeScriptの型だけでこんなことができる」という一種の技術デモとして、また教育的な価値もあるライブラリになったのではないかと思います。

興味がある方は、ぜひGitHubリポジトリをチェックしてみてください！

1. (https://speakerdeck.com/ysknsid25/type-challengesnixin-siiwen-ti-wozhui-jia-site-type-challengesnomaintainerninatutahua-0fd730df-ec2b-4445-bdc8-e4febe5127b7) ↩

2. https://zenn.dev/eringi_shimeji/articles/f13da3c761e453 ↩