UInt256 / Int256

256 bit符号なし整数UInt256と、2の補数表現による256 bit符号付き整数Int256を提供する。

import atcoder/extra/numeric/int256

概要

UInt256とInt256はいずれも32 byteの値型である。

内部表現は4個の64 bit limbであり、fieldは非公開である。通常はconstructor、変換関数、算術演算子を通して利用する。

Nimの識別子はstyle-insensitiveであるため、UInt256はUint256という綴りでも参照できる。明示的な別aliasは定義していない。

通常の加算、減算、乗算は256 bitでwrapする。

• UInt256は法2^256の算術になる。
• Int256は同じ256 bit列を2の補数として解釈する。
• overflowを検出したい場合はoverflowingAddなどを使う。
• 上限または下限へ固定したい場合はsaturatingAddなどを使う。

値域

UInt256の値域は次のとおりである。

0
...
115792089237316195423570985008687907853269984665640564039457584007913129639935

Int256の値域は次のとおりである。

-57896044618658097711785492504343953926634992332820282019728792003956564819968
...
57896044618658097711785492504343953926634992332820282019728792003956564819967

生成

fromUInt64Words

func fromUInt64Words(
  word3,
  word2,
  word1,
  word0: uint64,
): UInt256

4個の64 bit wordからUInt256を生成する。

argumentは上位wordから下位wordの順である。word0が最下位64 bitとなる。

let x = fromUInt64Words(
  4'u64,
  3'u64,
  2'u64,
  1'u64,
)

fromInt256Bits

func fromInt256Bits(
  word3,
  word2,
  word1,
  word0: uint64,
): Int256

指定した256 bit列をInt256として解釈する。

fromUInt128Halves

func fromUInt128Halves(
  highHalf,
  lowHalf: UInt128,
): UInt256

上位・下位の2個のUInt128からUInt256を生成する。

toUInt256

func toUInt256(value: uint64): UInt256
func toUInt256(value: UInt128): UInt256

小さい符号なし整数をUInt256へ拡張する。

toInt256

func toInt256(value: int64): Int256
func toInt256(value: Int128): Int256

小さい符号付き整数を符号拡張してInt256へ変換する。

bit列の変換と取得

asInt256 / asUInt256

func asInt256(value: UInt256): Int256
func asUInt256(value: Int256): UInt256

bit列を変更せず、符号付き・符号なしの解釈だけを変更する。

low128 / high128

func low128(value: UInt256): UInt128
func high128(value: UInt256): UInt128
func low128(value: Int256): UInt128
func high128(value: Int256): UInt128

下位または上位128 bitを取得する。

word64

func word64(value: UInt256, index: range[0 .. 3]): uint64
func word64(value: Int256, index: range[0 .. 3]): uint64

64 bit wordを取得する。index 0が最下位word、index 3が最上位wordである。

比較

次の比較を利用できる。

cmp(a, b)
a == b
a < b
a <= b
a > b
a >= b

Int256では符号付き整数として比較する。

算術演算

a + b
a - b
-a
a * b
a div b
a mod b

UInt256のdivとmodは通常の符号なし除算である。

Int256のdivは0方向への切り捨て、modはnumeratorと同じ符号を持つ剰余である。

数学的なfloor divisionが必要な場合は次を利用する。

floorDiv(a, b)
floorMod(a, b)

doAssert floorDiv(
  parseInt256("-7"),
  parseInt256("3"),
) == parseInt256("-3")

doAssert floorMod(
  parseInt256("-7"),
  parseInt256("3"),
) == parseInt256("2")

0除算ではDivByZeroDefectが発生する。

wrapping演算

wrappingAdd(a, b)
wrappingSub(a, b)
wrappingMul(a, b)

通常の+、-、*と同じ256 bit wrapping結果を返す。

overflow付き演算

overflowingAdd(a, b)
overflowingSub(a, b)
overflowingMul(a, b)

戻り値は次のtupleである。

tuple[
  value: UInt256,
  overflow: bool,
]

Int256 overloadではvalueの型もInt256になる。

saturating演算

saturatingAdd(a, b)
saturatingSub(a, b)
saturatingMul(a, b)

overflowした場合、UInt256では0または最大値、Int256では最小値または最大値へ固定する。

bit演算

a and b
a or b
a xor b
not a
a shl distance
a shr distance

Int256の右shiftは算術右shiftである。

shift量が256以上の場合、符号なし値と非負の符号付き値は0になる。負のInt256を右shiftした場合は-1になる。

bit count

countLeadingZeroBits(value)
countTrailingZeroBits(value)
popcount(value)

0に対するleading zero countとtrailing zero countは256である。

rotation

rotateLeft(value, distance)
rotateRight(value, distance)

distanceは256で正規化される。負のdistanceも利用できる。

power

pow(base, exponent)
base ^ exponent
pow(base, exponent, modulus)

exponentは非負のintである。負のexponentではValueErrorが発生する。

3 argument版はUInt256のmodular exponentiationである。

doAssert pow(
  parseUInt256("123456789"),
  123,
  parseUInt256("1000000007"),
) == parseUInt256("922271998")

modulusが0の場合はDivByZeroDefectが発生する。

parseと文字列化

parseUInt256(text)
parseInt256(text)
$value

10進文字列をparseする。先頭の+を利用でき、Int256では-も利用できる。

値域外、空文字列、不正文字ではValueErrorが発生する。

補助API

isZero / isNegative

isZero(value)
isNegative(value)

isNegativeはInt256に対して利用する。

abs

abs(value: Int256): Int256

通常は絶対値を返す。

最小値の絶対値は正のInt256に収まらないため、wrapping semanticsにより最小値のままとなる。

小さい整数への変換

toInt(value)
toInt32(value)
toUInt(value)

下位wordを利用する切り詰め変換である。値域検査は行わない。

更新演算

inc value
dec value

value += other
value -= other
value *= other

更新演算も256 bit wrapping semanticsに従う。

hash

hash(value)

UInt256とInt256をhash keyとして利用できる。

内部wide arithmetic

256 bit乗算の完全な512 bit積には内部の8-limb表現を利用している。

この内部UInt512表現はatcoder/extra/numeric/int256のpublic APIとしてexportしない。将来のFloat256実装などから利用するwide arithmetic基盤として分離している。