はじめに
最近競技プログラミングを始めました。
普段の仕事で64ビットでは扱えないような天文学的な値や細かすぎる浮動小数点数に触れることって滅多に無いのですが、競技プログラミングではそのような機会がちょくちょくあります。
うまく回避する方法を検討するのも醍醐味ですが、初心者は巨大な値に慣れるところから勝負です。
今回は競プロ初心者として得た知見をメモします。
数値型における64ビットの最大値は変数の限界であって計算の限界ではない
まずは下記のコードをご覧ください。
package main
import (
"fmt"
)
func main() {
num := int64(9223372036854775808)
fmt.Println(num)
}
最近は仕事でGoを書いているので競プロもGoで解いています。
これを実行すると下記のようなエラーが出力されます
./main.go:8:14: constant 9223372036854775808 overflows int64
64ビット符号付き整数配列の最大値は9,223,372,036,854,775,807なので整数オーバーフローが発生します。
では下記の場合は...?
package main
import (
"fmt"
)
func main() {
num := int64(9223372036854775808 / 9223372036854775808)
fmt.Println(num)
}
1
64ビットの最大値を超えた値同士の計算ですが問題なく１が出力されます。
これはどこまで値が大きくなっても最終的な計算結果が9223372036854775807以下であれば変わりません。
(常軌を逸した値同士を計算したら何か起こるかもしれませんが)
※2020/08/05追記: Goの実装を漁ってみて確認しました13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084095
(512ビットで表現できる値の最大値)まで対応しているようです。
念のためC++でも書いてみましたが同様の結果でした
なおC++は9999999999999999999まで耐えましたが桁が増えるとエラーが発生しました...
※2020/8/5追記: 嘘ですね、こちらも64ビット符号なしで表現できる限界である18446744073709551615まで計算可能です。
大きな値が扱えても2のN乗が閾値になる辺りからコンピュータがビットの塊である事が伺えます、面白いですね。
#include <iostream>
using namespace std;
int main(void){
long long x = 9223372036854775808LL / 9223372036854775808LL;
std::cout << x << std::endl;
}
結論
仮にbit値をbyteに変換して表示する下記のようなコードが64ビットの限界を超えて動かなくなったとします。(具体例としては少々苦しいですが)
package main
import (
"fmt"
)
func main() {
bit := int64(9223372036854775808)
byte := bit / 1024
fmt.Println(byte)
}
途中結果がオーバーフローするような巨大な値でも、変数に格納する前に必要な計算を実行するだけで動かせる場合があるという事です。
package main
import (
"fmt"
)
func main() {
byte := int64(9223372036854775808 / 1024)
fmt.Println(byte)
}
追記
Goはconstであれば64ビット以上の値も格納できるそうです。
@Nabetani さん、ご指摘いただきありがとうございます。
試してみたらconstも512ビットまで使えるみたいです。
package main
import (
"fmt"
)
const huge0 = (1 << 127) - 1
const huge1 = 0x987654321abcdef0
func main() {
v0 := huge0 / (1 << 64)
v1 := huge1 / (1 << 16)
fmt.Printf("v0=%x v1=%x\n", v0, v1) //=> v0:7fffffffffffffff v1=987654321abc
}