「なでしこv3」開発掲示板

なでしこ3を改善するための掲示板
[一覧へ] > (@70) [低] [解決]
@70■ (#245) BigInt の(四則演算の)サポート案 - TumoiYorozu (2023-04-08 12:43) /低 未処理
現行のなでしこ3の数値型は JS の number を使用した float64 が使用されています。
これは整数として考えると 53bit 整数としても使用でき、±2^53 (≒9×10^15)の範囲であれば整数値も正しく計算できます。

しかし、AtCoder や情報オリンピック等の競技プログラミングのコンテストでは、64bit 整数が使用できる事を前提とした問題も多く、53bit までしか使用できない言語であると非本質な実装が増えてしまう問題があります。
例えば以下の問題は、10^18 までの整数かけ算が正しく計算できる言語であれば、素直に解くことができます。
https://atcoder.jp/contests/abc169/tasks/abc169_b


また競技プログラミングのコンテストでは、多倍長整数を使えない言語への配慮も兼ねて、1,000,000,007 という素数で割った余りを求めることを要求する問題もあります。
https://atcoder.jp/contests/abc055/tasks/abc055_b

https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a

整数 A, B のかけ算を M で割った余りは、 A*B%M で求めることができます。
A*B の結果が 10^15 程度までに収まる問題であれば良いのですが、中には A, B ともに 10^9 に近い値で計算する必要のある問題も多く、その場合 float64 では正しく計算できません。上記の qiita でも「割り算」や「二項係数 nCr」で解説されているこれらの操作では、よく A,B ともに巨大な数になりやすく、また問題として要求される機会が非常に多いです。


そこで、JavaScript には bigint という多倍長整数があるので、それをなでしこからも快適に扱えるようにする事で上記の問題をすんなりと解きたい背景があります。


一応、現行のなでしこでも、多少のハックで多倍長整数を使用できます。

```
●(Aを)巨大整数変換とは
  「{A}n」をJS実行。
ここまで

a=「1234567890123456789」を巨大整数変換
b=3を巨大整数変換
a*bを表示
```

これを実行すると「3703703670370370367」と正しく計算できます。

しかし、JS では bigint と number の四則演算をサポートしていないため、以下のような計算はエラーが発生します。
```
a=「1234567890123456789」を巨大整数変換
a*3を表示
```

一部の変数を明示的に巨大整数変換をするのは譲れるとして、計算にかかわるすべての変数を bigint に変換しないといけないのは骨が折れます。
そこで、なでしこcore 側で、bigint と number の四則演算をしようとした時に、現状ではエラーになる動作を、number を自動的に bigint に変換して計算する仕様を追加したいです。

(もしもこの方針に賛同できるけど時間がなければ、私の方でPRを作れないかも試そうかと思います)


(#246) BigIntぜひサポートしたいです - クジラ飛行机 (2023-04-08 20:02) /低 未処理
サポートできたら嬉しいです。
続きは、GitHubで話し合いましょう。

https://github.com/kujirahand/nadesiko3/issues/1448

(#251) サポート - クジラ飛行机 (2023-04-27 18:05) /低 解決
サポートしました。

(#245)へ返信する:

👆お手数ですが、いたずら防止のために、「真夏」の読み方を記入してください。

編集時に使うキーを入力(省略可能)

画像ファイル(最大300KB)を添付可能