整数 (Int) とリストを使ってシンプルな無符号多倍長整数 (Bignum) を実装します。基数を 65536 とし、リストの先頭が下位の桁、末尾を上位の桁とします。簡単な例を示します。
0 => List(0) 1 => List(1) 65535 => List(0xFFFF) 65536 => List(0, 1) 4294967295 => List(0xFFFF, 0xFFFF) 4294967296 => List(0, 0, 1)
整数 (Long) を多倍長整数に変換する関数 toBignum と、多倍長整数を整数 (Long) に変換する関数 bignumToLong を定義してください。
type Bignum = List[Int] def toBignum(n: Long): Bignum def bignumToLong(xs: Bignum): Long
Scala> toBignum(0) val res0: bignum.Bignum = List(0) Scala> toBignum(65535) val res1: bignum.Bignum = List(65535) Scala> toBignum(65536) val res2: bignum.Bignum = List(0, 1) Scala> toBignum(4294967295L) val res3: bignum.Bignum = List(65535, 65535) Scala> toBignum(4294967296L) val res4: bignum.Bignum = List(0, 0, 1) Scala> bignumToLong(List(0)) val res5: Long = 0 Scala> bignumToLong(List(1)) val res6: Long = 1 Scala> bignumToLong(List(65535)) val res7: Long = 65535 Scala> bignumToLong(List(0, 1)) val res8: Long = 65536 Scala> bignumToLong(List(0, 0, 1)) val res9: Long = 4294967296 Scala> bignumToLong(List(0, 0, 0, 1)) val res10: Long = 281474976710656 Scala> bignumToLong(List(0, 0, 0, 0x7fff)) val res11: Long = 9223090561878065152
2 つの多倍長整数 xs, ys の論理積を求める関数 bignumAND, 論理和を求める関数 bignumOR, 排他的論理和を求める関数 bignumXOR を定義してください。
def bignumAND(xs: Bignum, ys: Bignum): Bignum def bignumOR(xs: Bignum, ys; Bignum): Bignum def bignumXOR(xs: Bignum, ys: Bignum): Bignum
Scala> bignumAND(List(1, 1, 1), List(0)) val res0: bignum.Bignum = List(0) Scala> bignumAND(List(1, 1, 1), List(1)) val res1: bignum.Bignum = List(1) Scala> bignumAND(List(1, 2, 1), List(3, 3, 3)) val res2: bignum.Bignum = List(1, 2, 1) Scala> bignumAND(List(1, 2, 1), List(3, 3, 2)) val res3: bignum.Bignum = List(1, 2) Scala> bignumAND(List(1, 2, 1), List(3, 0, 2)) val res4: bignum.Bignum = List(1) Scala> bignumOR(List(1, 1, 1), List(0)) val res5: bignum.Bignum = List(1, 1, 1) Scala> bignumOR(List(1, 1, 1), List(2, 2, 2)) val res6: bignum.Bignum = List(3, 3, 3) Scala> bignumOR(List(1, 1, 1), List(2, 2, 2, 2, 2, 2)) val res7: bignum.Bignum = List(3, 3, 3, 2, 2, 2) Scala> bignumXOR(List(0, 1, 2, 3), List(1)) val res8: bignum.Bignum = List(1, 1, 2, 3) Scala> bignumXOR(List(0, 1, 2, 3), List(1, 2, 3, 4)) val res9: bignum.Bignum = List(1, 3, 1, 7) Scala> bignumXOR(List(0, 1, 2, 3), List(0, 1, 2, 3)) val res10: bignum.Bignum = List(0)
多倍長整数 xs を左へビットシフトする関数 bignumShiftLeft と、右へビットシフトする関数 bignumShiftRight を定義してください。
def bignumShiftLeft(xs: Bignum, n: Int): Bignum def bignumShiftRight(xs: Bignum, n: Int): Bignum
Scala> bignumShiftLeft(List(1), 0) val res0: bignum.Bignum = List(1) Scala> bignumShiftLeft(List(1), 1) val res1: bignum.Bignum = List(2) Scala> bignumShiftLeft(List(1, 1, 1, 1), 15) val res2: bignum.Bignum = List(32768, 32768, 32768, 32768) Scala> bignumShiftLeft(List(1, 1, 1, 1), 16) val res3: bignum.Bignum = List(0, 1, 1, 1, 1) Scala> bignumShiftLeft(List(1, 1, 1, 1), 32) val res4: bignum.Bignum = List(0, 0, 1, 1, 1, 1) Scala> bignumShiftRight(List(0, 1), 0) val res5: bignum.Bignum = List(0, 1) Scala> bignumShiftRight(List(0, 1), 1) val res6: bignum.Bignum = List(32768) Scala> bignumShiftRight(List(0, 1), 15) val res7: bignum.Bignum = List(2) Scala> bignumShiftRight(List(0, 1), 16) val res8: bignum.Bignum = List(1) Scala> bignumShiftRight(List(0, 1), 17) val res9: bignum.Bignum = List() Scala> bignumShiftRight(List(0, 0, 1), 32) val res10: bignum.Bignum = List(1)
多倍長整数を比較する関数 bignumEQ, bignumNE, bignumGT, bignumGE, bignumLT, bignumLE を定義してください。
def bignumEQ(xs: Bignum, ys: Bignum): Boolean // xs == ys def bignumNE(xs: Bignum, ys: Bignum): Boolean // xs != ys def bignumGT(xs: Bignum, ys: Bignum): Boolean // xs > ys def bignumLT(xs: Bignum, ys: Bignum): Boolean // xs < ys def bignumGE(xs: Bignum, ys: Bignum): Boolean // xs >= ys def bignumLE(xs: Bignum, ys: Bignum): Boolean // xs <= ys
Scala> bignumEQ(List(1, 1, 1), List(1, 1, 1)) val res0: Boolean = true Scala> bignumEQ(List(1, 1, 1), List(1, 0, 1)) val res1: Boolean = false Scala> bignumNE(List(1, 1, 1), List(1, 1, 1)) val res2: Boolean = false Scala> bignumNE(List(1, 1, 1), List(0, 1, 1)) val res3: Boolean = true Scala> bignumGT(List(0, 0, 1), List(0, 1)) val res4: Boolean = true Scala> bignumGT(List(0, 0, 1), List(0, 0, 2)) val res5: Boolean = false Scala> bignumGE(List(0, 0, 1), List(0, 0, 1)) val res6: Boolean = true Scala> bignumGE(List(0, 0, 2), List(0, 0, 1)) val res7: Boolean = true Scala> bignumGE(List(0, 0, 1), List(0, 0, 2)) val res8: Boolean = false Scala> bignumLT(List(0, 0, 2), List(0, 0, 1)) val res9: Boolean = false Scala> bignumLT(List(0, 2), List(0, 0, 1)) val res10: Boolean = true Scala> bignumLE(List(0, 0, 1), List(0, 0, 1)) val res11: Boolean = true Scala> bignumLE(List(0, 0, 1), List(0, 0, 2)) val res12: Boolean = true Scala> bignumLE(List(0, 0, 1), List(0, 2)) val res13: Boolean = false
多倍長整数 xs と基数未満の整数 n を加算する関数 bignumAddInt を定義してください。
def bignumAddInt(xs: Bignum, n: Int): Bignum
Scala> bignumAddInt(List(65535, 65535), 0) val res0: bignum.Bignum = List(65535, 65535) Scala> bignumAddInt(List(65535, 65535), 1) val res1: bignum.Bignum = List(0, 0, 1) Scala> bignumAddInt(List(65535, 65535), 65535) val res2: bignum.Bignum = List(65534, 0, 1)
多倍長整数 xs, ys を加算する関数 bignumAdd を定義してください。
def bignumAdd(xs: Bignum, ys: Bignum): Bignum
Scala> bignumAdd(List(0, 65535), List(65535, 1)) val res0: bignum.Bignum = List(65535, 0, 1) Scala> bignumAdd(List(65535, 65535), List(65535, 65535)) val res1: bignum.Bignum = List(65534, 65535, 1) Scala> bignumAdd(List(65535, 65535), List(1,0,1)) val res2: bignum.Bignum = List(0, 0, 2)
多倍長整数 xs と基数未満の整数 n を減算する関数 bignumSubInt を定義してください。
def bignumSubInt(xs: Bignum, n: Int): Bignum
Scala> bignumSubInt(List(1), 0) val res0: bignum.Bignum = List(1) Scala> bignumSubInt(List(1), 1) val res1: bignum.Bignum = List(0) Scala> bignumSubInt(List(1), 2) java.lang.Exception: bignum: underflow ・・・ 省略 ・・・ Scala> bignumSubInt(List(0, 0, 0, 0, 1), 1) val res2: bignum.Bignum = List(65535, 65535, 65535, 65535) Scala> bignumSubInt(List(0, 0, 0, 0, 1), 65535) val res3: bignum.Bignum = List(1, 65535, 65535, 65535)
多倍長整数 xs, ys を減算する関数 bignumSub を定義してください。
def bignumSub(xs: Bignum, ys: Bignum): Bignum
Scala> bignumSub(List(0, 0, 1), List(65535, 65535)) val res0: bignum.Bignum = List(1) Scala> bignumSub(List(0, 0, 1), List(0, 0, 1)) val res1: bignum.Bignum = List(0) Scala> bignumSub(List(0, 0, 1), List(0, 1)) val res2: bignum.Bignum = List(0, 65535) Scala> bignumSub(List(0, 0, 1), List(1, 0, 1)) java.lang.Exception: bignum: underflow ・・・ 省略 ・・・
多倍長整数 xs と基数未満の整数 n を乗算する関数 bignumMulInt を定義してください。
def bignumMulInt(xs: Bignum, n: Int): Bignum
Scala> bignumMulInt(List(1, 2, 3, 4, 5), 0) val res0: bignum.Bignum = List(0) Scala> bignumMulInt(List(1, 2, 3, 4, 5), 1) val res1: bignum.Bignum = List(1, 2, 3, 4, 5) Scala> bignumMulInt(List(1, 2, 3, 4, 5), 2) val res2: bignum.Bignum = List(2, 4, 6, 8, 10) Scala> bignumMulInt(List(65535, 65535), 65535) val res3: bignum.Bignum = List(1, 65535, 65534)
多倍長整数 xs, ys を乗算する関数 bignumMul を定義してください。
def bignumMul(xs: Bignum, ys: Bignum): Bignum
Scala> bignumMul(List(1, 1, 1), List(1, 1, 1)) val res4: bignum.Bignum = List(1, 2, 3, 2, 1) Scala> bignumMul(List(65535, 65535, 65535), List(1, 1, 1)) val res5: bignum.Bignum = List(65535, 65534, 65534, 0, 1, 1) Scala> bignumMul(List(65535, 65535, 65535), List(65535, 65535, 65535)) val res6: bignum.Bignum = List(1, 0, 0, 65534, 65535, 65535)
多倍長整数 xs と基数未満の整数 n を除算する関数 bignumDivInt を定義してください。返り値は商と剰余をタプルで返すものとします。
def bignumDivInt(xs: Bignum, n: Int): (Bignum, Bignum)
Scala> bignumDivInt(List(2, 4, 6, 8, 10), 1) val res0: (bignum.Bignum, bignum.Bignum) = (List(2, 4, 6, 8, 10),List(0)) Scala> bignumDivInt(List(2, 4, 6, 8, 10), 2) val res1: (bignum.Bignum, bignum.Bignum) = (List(1, 2, 3, 4, 5),List(0)) Scala> bignumDivInt(List(2, 4, 6, 8, 10), 3) val res2: (bignum.Bignum, bignum.Bignum) = (List(21846, 1, 2, 21848, 3),List(0)) Scala> bignumDivInt(List(2, 4, 6, 8, 10), 4) val res3: (bignum.Bignum, bignum.Bignum) = (List(0, 32769, 1, 32770, 2),List(2)) Scala> bignumDivInt(List(2, 4, 6, 8, 10), 65535) val res4: (bignum.Bignum, bignum.Bignum) = (List(28, 24, 18, 10),List(30)) Scala> bignumDivInt(List(2, 4, 6, 8, 10), 0) java.lang.Exception: bignum: divide by zero ・・・ 省略 ・・・
多倍長整数 xs, ys を除算する関数 bignumDiv を定義してください。返り値は商と剰余をタプルに格納して返すものとします。
def bignumDiv(xs: Bignum, ys: Bignum): (Bignum, Bignum)
Scala> bignumDiv(List(0, 0, 0, 1), List(0, 0, 0,1)) val res0: (bignum.Bignum, bignum.Bignum) = (List(1),List(0)) Scala> bignumDiv(List(0, 0, 0, 1), List(0, 0, 1)) val res1: (bignum.Bignum, bignum.Bignum) = (List(0, 1),List(0)) Scala> bignumDiv(List(1, 0, 0, 1), List(0, 0, 1)) val res2: (bignum.Bignum, bignum.Bignum) = (List(0, 1),List(1)) Scala> bignumDiv(List(0, 0, 0, 1), List(65535, 65535)) val res3: (bignum.Bignum, bignum.Bignum) = (List(0, 1),List(0, 1))
多倍長整数 xs を文字列に変換する関数 bignumToString と、文字列 s を多倍長整数に変換する関数 stringToBignum を定義してください。r は基数を表す整数値 (r <= 16) です。
def bignumToString(xs: Bignum): String def stringToBignum(s: String): Bignum
Scala> bignumToString(List(0, 0, 0, 1), 10)
val res0: String = 281474976710656
Scala> bignumToString(List(0, 0, 0, 1), 16)
val res1: String = 1000000000000
Scala> bignumToString(List(65535, 65535, 65535), 10)
val res2: String = 281474976710655
Scala> bignumToString(List(65535, 65535, 65535), 16)
val res3: String = FFFFFFFFFFFF
Scala> stringToBignum("1234567890", 10)
val res4: bignum.Bignum = List(722, 18838)
Scala> stringToBignum("FFFFFFFFFFFF", 16)
val res5: bignum.Bignum = List(65535, 65535, 65535)
Scala> stringToBignum("1234567890ABCDEF", 16)
val res6: bignum.Bignum = List(52719, 37035, 22136, 4660)
Scala> stringToBignum("12345678901234567890", 10)
val res7: bignum.Bignum = List(2770, 60191, 43404, 43860)
リスト : 整数と多倍長整数の変換
type Bignum = List[Int]
val Base: Int = 0x10000 // 基数
def toBignum(n: Long): Bignum =
if (n < 0) throw new Exception("toBignum: domain error")
else if (n < Base) List(n.toInt)
else (n % Base).toInt :: toBignum(n / Base)
def bignumToLong(xs: Bignum): Long =
xs.foldRight(0L)((x: Int, a: Long) => a * Base + x)
toBignum は簡単です。n が基数 Base よりも小さければ n.toInt をリストに格納して返します。あとは、整数 n を Base で割り算していき、剰余を toBignum の返り値 (リスト) に追加していくだけです。bignumToLong も簡単です。引数 xs を foldRight で末尾から畳み込むだけです。
リスト : 多倍長整数の論理積
def dropWhileRight[A](f: A => Boolean, xs: List[A]): List[A] =
xs.reverse.dropWhile(f).reverse
def bignumAND(xs: Bignum, ys: Bignum): Bignum = {
val zs = dropWhileRight((_: Int) == 0, xs.zip(ys).map(z => z._1 & z._2))
if (zs == Nil) List(0) else zs
}
bignumAND は xs と ys の要素の論理積を zip と map で求め、末尾から連続する 0 を関数 dropWhileRight で取り除きます。その結果、zs が空リストになったならば List(0) を返します。そうでなければ zs をそのまま返します。
リスト : 多倍長整数の論理和
def bignumLogical(f: (Int, Int) => Int, xs: Bignum, ys: Bignum): Bignum =
(xs, ys) match {
case (_, Nil) => xs
case (Nil, _) => ys
case (x::xs1, y::ys1) => f(x, y) :: bignumLogical(f, xs1, ys1)
}
def bignumOR(xs: Bignum, ys: Bignum): Bignum =
bignumLogical(_ | _, xs, ys)
bignumOR と bignumXOR の処理は関数 bignumLogical で行います。bignumLogical は xs と ys の要素を順番に取り出して関数 f を適用し、その結果を bignumLogical の返り値 (リスト) に追加します。ys が空リストになった場合は xs を返し、xs が空リストになった場合は ys を返します。両方とも空リストの場合は空リストを返します。
リスト : 多倍長整数の排他的論理和
def bignumXOR(xs: Bignum, ys: Bignum): Bignum = {
val zs = dropWhileRight((_: Int) == 0, bignumLogical(_ ^ _, xs, ys))
if (zs == Nil) List(0) else zs
}
bignumXOR は bignumLogical を呼び出して、リストの要素を排他的論理和を求め、dropWhileRight で末尾から連続する 0 を取り除きます。その結果、zs が空リストになったら List(0) を返します。そうでなければ zs をそのまま返します。
リスト : 多倍長整数の左シフト
val BaseBit: Int = 16
def bignumShiftLeft16(xs: Bignum, n: Int, c: Int = 0): Bignum =
xs match {
case Nil => if (c > 0) List(c) else Nil
case x::xs1 => ((x << n) | c) :: bignumShiftLeft16(xs1, n, x >> (BaseBit - n))
}
def bignumShiftLeft(xs: Bignum, n: Int): Bignum =
if (n == 0 || xs == List(0)) xs
else if (n < BaseBit) bignumShiftLeft16(xs, n)
else List.fill(n / BaseBit)(0) ::: bignumShiftLeft16(xs, n % BaseBit)
bignumShiftLeft は引数 n が 0 または xs が List(0) の場合は xs をそのまま返します。n が BaseBit 未満の場合は関数 bignumShiftLeft16 を呼び出します。そうでなければ、xs を (n % BaseBit) ビットシフトした結果に (n / BaseBit) 個の 0 を先頭に追加します。
実際のビットシフトは bignumShiftLeft16 で行います。引数 c には左ビットシフトしたときに溢れたビットをセットします。x を n ビット左シフトした値 と c の論理和を求め、それを再帰呼び出しの返り値 (リスト) に追加します。溢れたビットは x を右へ (BaseBit - n) ビットシフトすれば求めることができます。
リスト : 多倍長整数の右シフト
val mask: Int = 0xffff
def bignumShiftRight16(xs: Bignum, n: Int): Bignum = {
val (ys, _) = xs.foldRight((Nil: Bignum, 0))((x, a) =>
((a._2 | (x >> n)) :: a._1, mask & (x << (BaseBit - n))))
dropWhileRight((_: Int) == 0, ys)
val zs = dropWhileRight((_: Int) == 0, ys)
if (zs == Nil) List(0) else zs
}
def bignumShiftRight(xs: Bignum, n: Int): Bignum =
if (n == 0 || xs == List(0)) xs
else if (n < BaseBit) bignumShiftRight16(xs, n)
else {
val ys = xs.drop(n / BaseBit)
if (ys == Nil) List(0)
else bignumShiftRight(ys, n % BaseBit)
}
bignumShiftRight は引数 n が 0 または xs が List(0) の場合は xs をそのまま返します。n が BaseBit 未満の場合は関数 bignumShiftRight16 を呼び出します。そうでなければ、xs の先頭から (n / BaseBit) 個の要素を取り除き、それを ys にセットします。もし ys が空リストならば List(0) を返します。そうでなければ、bignumShiftRigth16 を呼び出して、ys を (n % BaseBit) ビット右へシフトします。
実際のビットシフトは bignumShiftRight16 で行います。foldRight で xs の末尾から順番に要素を n ビット右シフトしていきます。累積変数 a はタプルで、第 1 要素が Bignum, 第 2 要素が溢れたビットです。要素 x を n ビット右シフトして、それと a._2 との論理和を求め、それを a._1 の先頭に追加します。溢れたビットは x を (BaseBit - n) ビット左シフトして、下位 16 ビットを取り出すだけです。最後に、末尾から連続する 0 を dropWhileRight で削除します。その結果が空リストならば List(0) を返します。
リスト : 多倍長整数の比較
def bignumCompare(xs: Bignum, ys: Bignum): Int =
(xs, ys) match {
case (Nil, Nil) => 0
case (Nil, _) => -1
case (_, Nil) => 1
case (x::xs1, y::ys1) =>
bignumCompare(xs1, ys1) match {
case 0 => x - y
case r => r
}
}
def bignumEQ(xs: Bignum, ys: Bignum): Boolean = bignumCompare(xs, ys) == 0
def bignumNE(xs: Bignum, ys: Bignum): Boolean = bignumCompare(xs, ys) != 0
def bignumGT(xs: Bignum, ys: Bignum): Boolean = bignumCompare(xs, ys) > 0
def bignumLT(xs: Bignum, ys: Bignum): Boolean = bignumCompare(xs, ys) < 0
def bignumGE(xs: Bignum, ys: Bignum): Boolean = bignumCompare(xs, ys) >= 0
def bignumLE(xs: Bignum, ys: Bignum): Boolean = bignumCompare(xs, ys) <= 0
関数 bignumCompare は 2 つのリストを順番にたどっていき、xs が先に空リストになったら -1 を、ys が先に空リストになったら 1 を返します。両方とも空リストになった場合は 0 を返します。xs, ys がリストの場合、bignumCompare を再帰呼び出しして、その結果が 0 の場合は x - y を返します。そうでなければ、返り値 r をそのまま返します。あとは、各関数から bignumCompare を呼び出して結果を 0 と比較するだけです。
リスト : 多倍長整数と整数の加算
def integerAdd(x: Int, y: Int, c: Int): (Int, Int) = {
val n = x + y + c
if (n < Base) (n, 0) else (n - Base, 1)
}
def bignumAddInt(xs: Bignum, n: Int): Bignum =
(xs, n) match {
case (_, 0) => xs
case (Nil, _) => if (n == 0) Nil else List(n)
case (x::xs1, _) => {
val (y, c) = integerAdd(x, 0, n)
y :: bignumAddInt(xs1, c)
}
}
bignumAddInt は最下位の桁と引数 n を加算し、桁上がりがあればそれを上位の桁に加算します。あとは、桁上げの処理を繰り返すだけです。整数同士の加算は関数 integerAdd で行います。引数 x, y, c を加算し、その値 n が base 未満であれば n と 0 をタプルで返します。そうでなければ、n - base と 1 をタプルで返します。
リスト : 多倍長整数の加算
def bignumAdd(xs: Bignum, ys: Bignum, c: Int = 0): Bignum =
(xs, ys) match {
case (Nil, _) => bignumAddInt(ys, c)
case (_, Nil) => bignumAddInt(xs, c)
case (x::xs1, y::ys1) => {
val (n, c1) = integerAdd(x, y, c)
n :: bignumAdd(xs1, ys1, c1)
}
}
bignumAdd の第 3 引数 c は桁上がりを表します。xs または ys が空リストの場合は bignumAddInt を呼び出して、もう一方の値と c を加算します。そうでなければ、xs と ys の要素と c を integerAdd で加算します。あとは、bignumAdd の第 3 引数に c1 を渡してを再帰呼び出しし、その返り値に n を追加するだけです。
リスト : 多倍長整数と整数の減算
def integerSub(x: Int, y: Int, c: Int): (Int, Int) = {
val n = Base + x - y - c
if (n < Base) (n, 1) else (n - Base, 0)
}
def bignumSubInt(xs: Bignum, n: Int): Bignum = {
val (ys, c) = xs.foldLeft((Nil: Bignum, n))((a, x) => {
val (y, c) = integerSub(x, 0, a._2)
(y::a._1, c)})
if (c != 0) throw new Exception("bignum: underflow")
else {
val zs = ys.dropWhile(_ == 0)
if (zs == Nil) List(0) else zs.reverse
}
}
bignumSubInt は最下位の桁と引数 n を減算し、桁借りがあればそれを上位の桁から減算します。あとは、桁借りの処理を繰り返すだけです。実際の処理は foldLeft で行います。累積変数 a はタプルで、第 1 要素が Bignum, 第 2 要素が桁借りを表します。計算結果の Bignum は逆順になることに注意してください。
結果は変数 (ys, c) で受け取ります。c が 0 でなければ、結果は負になるのでエラーを送出します。そうでなければ、先頭から連続する 0 を dropWhile で取り除き、その結果が Nil ならが List(0) を返します。空リストでなければ、zs を reverse で反転して返します。
integerSub は base + x から y と c を減算して変数 n にセットします。もし、n が base よりも小さい場合、n と桁借りを表す 1 をタプルで返します。そうでなければ、n - base と 0 をタプルで返します。
リスト : 多倍長整数の減算
def bignumSub(xs: Bignum, ys: Bignum): Bignum = {
def iter(xs: Bignum, ys: Bignum, c: Int): Bignum =
(xs, ys) match {
case (Nil, _) => if (ys == Nil && c == 0) Nil
else throw new Exception("bignum: underflow")
case (_, Nil) => bignumSubInt(xs, c)
case (x::xs1, y::ys1) => {
val (n, c1) = integerSub(x, y, c)
n :: iter(xs1, ys1, c1)
}
}
val zs = dropWhileRight((_: Int) == 0, iter(xs, ys, 0))
if (zs == Nil) List(0) else zs
}
bignumSub の処理は局所関数 iter で行います。iter は xs と ys の要素と桁借りを表す引数 c を integerSub で減算し、その結果を iter の返り値 (リスト) に格納していきます。xs が空リストの場合、ys が空リストで c が 0 であれば空リストを返します。そうでなければ、結果は負になるのでエラーを送出します。ys が空リストで xs が空リストでない場合、bignumSubInt で xs から c を減算します。最後に、dropWhileEnd で末尾から連続する 0 を取り除き、その結果 zs が空リストであれば List(0) を、そうでなければ zs を返します。
リスト : 多倍長整数と整数の乗算
def integerMul(x: Long, y: Long, c: Long): (Int, Int) = {
val n = x * y + c
if (n < Base) (n.toInt, 0)
else ((n % Base).toInt, (n / Base).toInt)
}
def bignumMulInt(xs: Bignum, n: Int): Bignum =
n match {
case 0 => List(0)
case 1 => xs
case _ => {
val (ys, c) = xs.foldLeft((Nil: Bignum, 0: Int))((a, x) => {
val (y, c1) = integerMul(x, n, a._2)
(y :: a._1, c1)
})
(if (c > 0) c::ys else ys).reverse
}
}
bignumMulInt は引数 n が 0 ならば List(0) を、1 ならば xs をそのまま返します。それ以外の場合、最下位の桁から順番に x と掛け算します。この処理を foldLeft で行います。計算結果は変数 (ys, c) で受け取ります。ys は逆順になることに注意してください。c が 0 以上であれば、ys の先頭に c を追加します。最後に ys を reverse で反転して返します。
整数の乗算は関数 integerMul で行います。Int のまま乗算するとオーバーフローする場合があるので、引数の型を Long に設定しています。引数 x, y が乗算する整数、c が桁上がりで加算する値です。x * y + c を n にセットし、値が Base 未満であれば n と 0 をタプルで返します。そうでなければ、n と Base の剰余と商をタプルで返します。
リスト : 多倍長整数の乗算
def bignumMul(xs: Bignum, ys: Bignum): Bignum =
(xs, ys) match {
case (x::Nil, _) => bignumMulInt(ys, x)
case (_, y::Nil) => bignumMulInt(xs, y)
case (_, _) => {
val (zs, _) = (ys.foldLeft((List(0): Bignum, xs))((a, y) =>
(bignumAdd(a._1, bignumMulInt(a._2, y)), 0::a._2)))
zs
}
}
多倍長整数同士の乗算は筆算と同じ方法で行います。簡単な例を示しましょう。
xs : (4 3 2 1)
ys : (7 6 5)
1 2 3 4
* 5 6 7
----------------------
7 14 21 28
6 12 18 24 0
5 10 15 20 0 0
----------------------
5 16 34 52 45 28
図 : 多倍長整数の乗算
上図のように、xs を 16 ビット左シフトしながら ys の要素を掛け算し、その値を加算していけばいいわけです。
bignumMul は引数 xs, ys が Base 未満の整数であれば、bignumMulInt を呼び出して計算します。この処理を foldLeft で行います。累積変数 a はタプルで、第 1 要素が乗算の値、第 2 要素が要素 y に掛け算する値です。a._2 と y の乗算を bignumMulInt で求め、累積変数 a._1 にその値を bignumAdd で加算します。ys の次の要素を乗算するとき、累積変数 a._2 の先頭に 0 を挿入して 16 bit 左シフトします。
なお、今回の方法は桁数が多くなると遅くなります。これよりも高速な方法として「Karatsuba 法」や「高速フーリエ変換」を使った方法があります。これらのアルゴリズムについては、Fussy さん の 乗算処理の高速化, 高速フーリエ変換、M.Kamada さん の 離散フーリエ変換を用いた多倍長乗算の話 が参考になると思います。
リスト : 多倍長整数と整数の除算
def integerDiv(x: Int, y: Int, c: Int): (Int, Int) = {
val n = c * Base + x
(n / y, n % y)
}
def bignumDivInt(xs: Bignum, n: Int): (Bignum, Bignum) =
n match {
case 0 => throw new Exception("bignum: divide by zero")
case 1 => (xs, List(0))
case _ => {
val (ys, c) = xs.foldRight((Nil: Bignum, 0))((x, a) => {
val (p, q) = integerDiv(x, n, a._2)
(if (p == 0 && a._1 == Nil) a._1 else p::a._1, q)
})
if (ys == Nil) (List(0), List(c)) else (ys, List(c))
}
}
bignumDivInt は引数 x が 0 の場合はエラーを送出し、1 の場合は xs と List(0) をタプルで返します。それ以外の場合は、xs の上位の桁から順番に整数 x で除算していきます。この処理を foldRight で行います。累積変数 a はタプルで、第 1 要素が商で、第 2 要素が余りを表します。あとは、関数 integerDiv で xs の要素と n の除算を行います。
bignumDivInt は上位の桁から処理を行うため、リストの末尾に 0 が付加されないように工夫する必要があります。商 p が 0 で、かつ累積変数 a._1 が空リストの場合、p を a._1 に追加しません。それ以外の場合は p を a に追加します。最後に、計算結果 ys が空リストであれば List(0) と List(c) を、そうでなければ ys と List(c) をタプルで返します。
多倍長整数の除算は筆算と同じ方法で行いますが、かなり複雑な処理になります。ここではアルゴリズムの概略を説明するだけにとどめます。詳細は 参考文献 をお読みください。
リスト : 多倍長整数の除算 (擬似コード)
xs = (x1 x2 ... xn), ys = (y1 y2 ... ym) とし、xs / ys の商と剰余を求める
Base / 2 <= ym * d < Base を満たす d を求め、(xs * d) / (ys * d) を計算する
xs1 = xs * d とする
xs1 と同じ桁数になるよう (ys * d) の下位に 0 を追加たものを ys1 とする
このとき、追加した 0 の個数を s とする
qs = ()
while( s >= 0 ){
xs1 / ys1 の仮の商 q' を求める。
(1) xs1 が ys1 よりも少ない桁数の場合、q' は 0 である
(2) xs1 と ys1 の桁数 (n) が同じ場合、q' = xn / yn とする
(3) xs1 が n 桁, ys1 が n - 1 桁の場合、q' = min( (xn * Base + xn-1) / yn-1, Base - 1 ) とする
if( q' > 0 ){
ys2 = ys1 * q'
while( xs1 < ys2 ){
q' = q' - 1
ys2 = ys2 - ys1
}
xs1 = xs1 - ys2
}
q' を qs に追加する
ys1 の最下位から 0 を取り除く
s = s - 1
}
商は qs, 剰余は xs1 / d となる。
ポイントは仮の商 q' を求める処理です。ys1 の最上位の桁 ym が条件 (A) Base / 2 <= ym < Base を満たしている場合、(2) であれば q' は 0 か 1 になります。(3) であれば xs1 の上位 2 桁と ys1 の上位 1 桁 (ym) から仮の商を求めます。このとき、真の商を q とすると、条件 (A) を満たしているならば次の式が成り立ちます。
q <= q' <= q + 2
したがって、q の値は q', q' - 1, q' - 2 のどれかになります。ys2 = ys1 * q' を計算し、xs1 < ys2 であれば q' から 1 を、ys2 から ys1 を引き算します。これを xs1 >= ys2 になるまで繰り返しますが、最悪でも 2 回の繰り返しで済むわけです。
商 q が q' - 1 と q' - 2 になる例を示します。
xs1 = [65535, 65535, 32767] ys1 = [65535, 32768] q' = (32767 * Base + 65535) / 32768 = 65535 ys2 = [65535, 32768] * 65535 = [1, 32766, 32768] > xs1 q' = q' - 1 = 65534 ys2 = ys2 - ys1 = [2, 65533, 32767] < xs1 q' = 65534, xs1 = xs1 - ys2 = [65533, 2] ----------------------------------------------------- xs1 = [65535, 0, 32767] ys1 = [65535, 32768] q' = (32767 * Base + 0) / 32768 = 65534 ys2 = [65535, 32768] * 65534 = [2, 65533, 32767] > xs1 q' = q' - 1 ys2 = ys2 - ys1 = [3, 32764, 32767] > xs1 q' = q' - 1 ys2 = ys2 - ys1 = [4, 65531, 32766] < xs1 q' = 65532, xs1 = xs1 - ys2 = [65531, 5]
なお、(3) を満たしているとき、より高い精度で仮の商 q' を求める方法があります。有名なクヌース先生のアルゴリズムＤはこの方法を使っています。除算のアルゴリズムについては、参考文献 [2] がわかりやすくまとまっていると思います。また、乗算の処理が高速な場合、ニュートン法で ys の逆数 1 / ys を求め、xs * (1 / ys) を計算することで除算を高速に実行することができます。
擬似コードをそのままプログラムすると次のようになります。
リスト : 多倍長整数の除算
val halfBase = 0x8000
// シフトするビット数を求める
def getShiftBit(n: Int, c: Int = 0): Int =
if (n >= halfBase) c
else getShiftBit(n * 2, c + 1)
// 仮の商を求める
def getQuot(xs: Bignum, ys: Bignum): Int =
(xs, ys) match {
case (x::Nil, y::Nil) => x / y
case (x1::x2::Nil, y::Nil) => (x2 * Base + x1) / y
case (_::xs1, _::ys1) => getQuot(xs1, ys1)
case (_, _) => throw new Exception("bignum; getQuot error")
}
def bignumDiv(xs: Bignum, ys: Bignum): (Bignum, Bignum) =
ys match {
case y::Nil => bignumDivInt(xs, y)
case _ if (bignumLT(xs, ys)) => (List(0), xs)
case _ => {
val d = getShiftBit(ys.last)
var xs1 = bignumShiftLeft(xs, d)
var s = xs1.length - ys.length
var ys1 = bignumShiftLeft(ys, s * BaseBit + d)
var q: Bignum = Nil
while (s >= 0) {
var quot = getQuot(xs1, ys1) min (Base - 1)
if (quot > 0) {
var ys2 = bignumMulInt(ys1, quot)
while (bignumLT(xs1, ys2)) {
quot -= 1
ys2 = bignumSub(ys2, ys1)
}
q = quot :: q
xs1 = bignumSub(xs1, ys2)
} else if (q != Nil) q = 0 :: q
s -= 1
ys1 = ys1.tail
}
(q, bignumShiftRight(xs1, d))
}
}
関数 getShiftBit は ys の最上位の値が base / 2 以上になるよう、左シフトするビット数を求めます。関数 getQuot は仮の商を求めます。xs が空リストならば、xs の桁は ys よりも少ないので 0 を返します。ys が末尾の要素で、かつ xs も末尾の要素であれば、同じ桁数なので x / y を返します。そうでなければ、xs の上位 2 桁を求め、それを y で割り算します。関数 bignumDiv は説明をそのままプログラムしただけなので、とくに難しいところはないと思います。
リスト : 多倍長整数を文字列に変換する
val charTable = "0123456789ABCDEF"
def bignumToString(xs: Bignum, r: Int, s: String = ""): String =
if (xs == List(0)) s
else {
val (ys, List(m)) = bignumDivInt(xs, r)
bignumToString(ys, r, charTable(m).toString ++ s)
}
bignumToString は簡単です。bignumDivInt で xs を基数 r で割り算し、charTable から m 番目の要素を求め、それを累積変数 a のリストに追加します。この処理を xs が List(0) になるまで繰り返し、最後に a を返します。
リスト : 文字列を多倍長整数に変換する
def stringToBignum(s: String, r: Int, a: Bignum = List(0)): Bignum =
if (s.isEmpty) a
else {
val n = charTable.indexOf(s(0).toUpper)
if (n < 0) throw new Exception("stringToBignum: illegal char")
stringToBignum(s.tail, r, bignumAddInt(bignumMulInt(a, r), n))
}
stringToBignum も簡単です。先頭から 1 文字ずつ順番に取り出し、関数 indexOf で文字を数値 n に変換します。このとき、文字をメソッド toUpper で英大文字に変換しています。文字が見つからない場合はエラーを送出します。あとは、bignumMulInt で累積変数 a と基数 r を掛け算し、bignumAddInt で n を加算していくだけです。最後に a を返します。
//
// bignum.scala : 無符号多倍長整数
//
// Copyright (C) 2014-2021 Makoto Hiroi
//
object bignum {
// Q63
type Bignum = List[Int]
val Base: Int = 0x10000
val BaseBit: Int = 16
def toBignum(n: Long): Bignum =
if (n < 0) throw new Exception("toBignum: domain error")
else if (n < Base) List(n.toInt)
else (n % Base).toInt :: toBignum(n / Base)
def bignumToLong(xs: Bignum): Long =
xs.foldRight(0L)((x: Int, a: Long) => a * Base + x)
// Q64
def dropWhileRight[A](f: A => Boolean, xs: List[A]): List[A] =
xs.reverse.dropWhile(f).reverse
def bignumAND(xs: Bignum, ys: Bignum): Bignum = {
val zs = dropWhileRight((_: Int) == 0, xs.zip(ys).map(z => z._1 & z._2))
if (zs == Nil) List(0) else zs
}
def bignumLogical(f: (Int, Int) => Int, xs: Bignum, ys: Bignum): Bignum =
(xs, ys) match {
case (_, Nil) => xs
case (Nil, _) => ys
case (x::xs1, y::ys1) => f(x, y) :: bignumLogical(f, xs1, ys1)
}
def bignumOR(xs: Bignum, ys: Bignum): Bignum =
bignumLogical(_ | _, xs, ys)
def bignumXOR(xs: Bignum, ys: Bignum): Bignum = {
val zs = dropWhileRight((_: Int) == 0, bignumLogical(_ ^ _, xs, ys))
if (zs == Nil) List(0) else zs
}
// Q65
val mask: Int = 0xffff
def bignumShiftLeft16(xs: Bignum, n: Int, c: Int = 0): Bignum =
xs match {
case Nil => if (c > 0) List(c) else Nil
case x::xs1 => ((x << n) | c) :: bignumShiftLeft16(xs1, n, x >> (BaseBit - n))
}
def bignumShiftLeft(xs: Bignum, n: Int): Bignum =
if (n == 0 || xs == List(0)) xs
else if (n < BaseBit) bignumShiftLeft16(xs, n)
else List.fill(n / BaseBit)(0) ::: bignumShiftLeft16(xs, n % BaseBit)
def bignumShiftRight16(xs: Bignum, n: Int): Bignum = {
val (ys, _) = xs.foldRight((Nil: Bignum, 0))((x, a) =>
((a._2 | (x >> n)) :: a._1, mask & (x << (BaseBit - n))))
dropWhileRight((_: Int) == 0, ys)
val zs = dropWhileRight((_: Int) == 0, ys)
if (zs == Nil) List(0) else zs
}
def bignumShiftRight(xs: Bignum, n: Int): Bignum =
if (n == 0 || xs == List(0)) xs
else if (n < BaseBit) bignumShiftRight16(xs, n)
else {
val ys = xs.drop(n / BaseBit)
if (ys == Nil) List(0)
else bignumShiftRight(ys, n % BaseBit)
}
// Q66
def bignumCompare(xs: Bignum, ys: Bignum): Int =
(xs, ys) match {
case (Nil, Nil) => 0
case (Nil, _) => -1
case (_, Nil) => 1
case (x::xs1, y::ys1) =>
bignumCompare(xs1, ys1) match {
case 0 => x - y
case r => r
}
}
def bignumEQ(xs: Bignum, ys: Bignum): Boolean = bignumCompare(xs, ys) == 0
def bignumNE(xs: Bignum, ys: Bignum): Boolean = bignumCompare(xs, ys) != 0
def bignumGT(xs: Bignum, ys: Bignum): Boolean = bignumCompare(xs, ys) > 0
def bignumLT(xs: Bignum, ys: Bignum): Boolean = bignumCompare(xs, ys) < 0
def bignumGE(xs: Bignum, ys: Bignum): Boolean = bignumCompare(xs, ys) >= 0
def bignumLE(xs: Bignum, ys: Bignum): Boolean = bignumCompare(xs, ys) <= 0
// Q67
def integerAdd(x: Int, y: Int, c: Int): (Int, Int) = {
val n = x + y + c
if (n < Base) (n, 0) else (n - Base, 1)
}
def bignumAddInt(xs: Bignum, n: Int): Bignum =
(xs, n) match {
case (_, 0) => xs
case (Nil, _) => if (n == 0) Nil else List(n)
case (x::xs1, _) => {
val (y, c) = integerAdd(x, 0, n)
y :: bignumAddInt(xs1, c)
}
}
// Q68
def bignumAdd(xs: Bignum, ys: Bignum, c: Int = 0): Bignum =
(xs, ys) match {
case (Nil, _) => bignumAddInt(ys, c)
case (_, Nil) => bignumAddInt(xs, c)
case (x::xs1, y::ys1) => {
val (n, c1) = integerAdd(x, y, c)
n :: bignumAdd(xs1, ys1, c1)
}
}
// Q69
def integerSub(x: Int, y: Int, c: Int): (Int, Int) = {
val n = Base + x - y - c
if (n < Base) (n, 1) else (n - Base, 0)
}
def bignumSubInt(xs: Bignum, n: Int): Bignum = {
val (ys, c) = xs.foldLeft((Nil: Bignum, n))((a, x) => {
val (y, c) = integerSub(x, 0, a._2)
(y::a._1, c)})
if (c != 0) throw new Exception("bignum: underflow")
else {
val zs = ys.dropWhile(_ == 0)
if (zs == Nil) List(0) else zs.reverse
}
}
// Q70
def bignumSub(xs: Bignum, ys: Bignum): Bignum = {
def iter(xs: Bignum, ys: Bignum, c: Int): Bignum =
(xs, ys) match {
case (Nil, _) => if (ys == Nil && c == 0) Nil
else throw new Exception("bignum: underflow")
case (_, Nil) => bignumSubInt(xs, c)
case (x::xs1, y::ys1) => {
val (n, c1) = integerSub(x, y, c)
n :: iter(xs1, ys1, c1)
}
}
val zs = dropWhileRight((_: Int) == 0, iter(xs, ys, 0))
if (zs == Nil) List(0) else zs
}
// Q71
def integerMul(x: Long, y: Long, c: Long): (Int, Int) = {
val n = x * y + c
if (n < Base) (n.toInt, 0)
else ((n % Base).toInt, (n / Base).toInt)
}
def bignumMulInt(xs: Bignum, n: Int): Bignum =
n match {
case 0 => List(0)
case 1 => xs
case _ => {
val (ys, c) = xs.foldLeft((Nil: Bignum, 0: Int))((a, x) => {
val (y, c1) = integerMul(x, n, a._2)
(y :: a._1, c1)
})
(if (c > 0) c::ys else ys).reverse
}
}
// Q72
def bignumMul(xs: Bignum, ys: Bignum): Bignum =
(xs, ys) match {
case (x::Nil, _) => bignumMulInt(ys, x)
case (_, y::Nil) => bignumMulInt(xs, y)
case (_, _) => {
val (zs, _) = (ys.foldLeft((List(0): Bignum, xs))((a, y) =>
(bignumAdd(a._1, bignumMulInt(a._2, y)), 0::a._2)))
zs
}
}
// Q73
def integerDiv(x: Int, y: Int, c: Int): (Int, Int) = {
val n = c * Base + x
(n / y, n % y)
}
def bignumDivInt(xs: Bignum, n: Int): (Bignum, Bignum) =
n match {
case 0 => throw new Exception("bignum: divide by zero")
case 1 => (xs, List(0))
case _ => {
val (ys, c) = xs.foldRight((Nil: Bignum, 0))((x, a) => {
val (p, q) = integerDiv(x, n, a._2)
(if (p == 0 && a._1 == Nil) a._1 else p::a._1, q)
})
if (ys == Nil) (List(0), List(c)) else (ys, List(c))
}
}
// Q74
val halfBase = 0x8000
// シフトするビット数を求める
def getShiftBit(n: Int, c: Int = 0): Int =
if (n >= halfBase) c
else getShiftBit(n * 2, c + 1)
// 仮の商を求める
def getQuot(xs: Bignum, ys: Bignum): Int =
(xs, ys) match {
case (x::Nil, y::Nil) => x / y
case (x1::x2::Nil, y::Nil) => (x2 * Base + x1) / y
case (_::xs1, _::ys1) => getQuot(xs1, ys1)
case (_, _) => throw new Exception("bignum; getQuot error")
}
def bignumDiv(xs: Bignum, ys: Bignum): (Bignum, Bignum) =
ys match {
case y::Nil => bignumDivInt(xs, y)
case _ if (bignumLT(xs, ys)) => (List(0), xs)
case _ => {
val d = getShiftBit(ys.last)
var xs1 = bignumShiftLeft(xs, d)
var s = xs1.length - ys.length
var ys1 = bignumShiftLeft(ys, s * BaseBit + d)
var q: Bignum = Nil
while (s >= 0) {
var quot = getQuot(xs1, ys1) min (Base - 1)
if (quot > 0) {
var ys2 = bignumMulInt(ys1, quot)
while (bignumLT(xs1, ys2)) {
quot -= 1
ys2 = bignumSub(ys2, ys1)
}
q = quot :: q
xs1 = bignumSub(xs1, ys2)
} else if (q != Nil) q = 0 :: q
s -= 1
ys1 = ys1.tail
}
(q, bignumShiftRight(xs1, d))
}
}
// Q75
val charTable = "0123456789ABCDEF"
def bignumToString(xs: Bignum, r: Int, s: String = ""): String =
if (xs == List(0)) s
else {
val (ys, List(m)) = bignumDivInt(xs, r)
bignumToString(ys, r, charTable(m).toString ++ s)
}
def stringToBignum(s: String, r: Int, a: Bignum = List(0)): Bignum =
if (s.isEmpty) a
else {
val n = charTable.indexOf(s(0).toUpper)
if (n < 0) throw new Exception("stringToBignum: illegal char")
stringToBignum(s.tail, r, bignumAddInt(bignumMulInt(a, r), n))
}
}