import scala.collection.mutable.ListBuffer object ZeckendorfArithmetic extends App { val elapsed: (=> Unit) => Long = f => { val s = System.currentTimeMillis f (System.currentTimeMillis - s) / 1000 } val add: (Z, Z) => Z = (z1, z2) => z1 + z2 val subtract: (Z, Z) => Z = (z1, z2) => z1 - z2 val multiply: (Z, Z) => Z = (z1, z2) => z1 * z2 val divide: (Z, Z) => Option[Z] = (z1, z2) => z1 / z2 val modulo: (Z, Z) => Option[Z] = (z1, z2) => z1 % z2 val ops = Map(("+", add), ("-", subtract), ("*", multiply), ("/", divide), ("%", modulo)) val calcs = List( (Z("101"), "+", Z("10100")) , (Z("101"), "-", Z("10100")) , (Z("101"), "*", Z("10100")) , (Z("101"), "/", Z("10100")) , (Z("-1010101"), "+", Z("10100")) , (Z("-1010101"), "-", Z("10100")) , (Z("-1010101"), "*", Z("10100")) , (Z("-1010101"), "/", Z("10100")) , (Z("1000101010"), "+", Z("10101010")) , (Z("1000101010"), "-", Z("10101010")) , (Z("1000101010"), "*", Z("10101010")) , (Z("1000101010"), "/", Z("10101010")) , (Z("10100"), "+", Z("1010")) , (Z("100101"), "-", Z("100")) , (Z("1010101010101010101"), "+", Z("-1010101010101")) , (Z("1010101010101010101"), "-", Z("-1010101010101")) , (Z("1010101010101010101"), "*", Z("-1010101010101")) , (Z("1010101010101010101"), "/", Z("-1010101010101")) , (Z("1010101010101010101"), "%", Z("-1010101010101")) , (Z("1010101010101010101"), "+", Z("101010101010101")) , (Z("1010101010101010101"), "-", Z("101010101010101")) , (Z("1010101010101010101"), "*", Z("101010101010101")) , (Z("1010101010101010101"), "/", Z("101010101010101")) , (Z("1010101010101010101"), "%", Z("101010101010101")) , (Z("10101010101010101010"), "+", Z("1010101010101010")) , (Z("10101010101010101010"), "-", Z("1010101010101010")) , (Z("10101010101010101010"), "*", Z("1010101010101010")) , (Z("10101010101010101010"), "/", Z("1010101010101010")) , (Z("10101010101010101010"), "%", Z("1010101010101010")) , (Z("1010"), "%", Z("10")) , (Z("1010"), "%", Z("-10")) , (Z("-1010"), "%", Z("10")) , (Z("-1010"), "%", Z("-10")) , (Z("100"), "/", Z("0")) , (Z("100"), "%", Z("0")) ) val iadd: (BigInt, BigInt) => BigInt = (a, b) => a + b val isub: (BigInt, BigInt) => BigInt = (a, b) => a - b // just for result checking: import Z._ val imul: (BigInt, BigInt) => BigInt = (a, b) => a * b val idiv: (BigInt, BigInt) => Option[BigInt] = (a, b) => if (b == 0) None else Some(a / b) val imod: (BigInt, BigInt) => Option[BigInt] = (a, b) => if (b == 0) None else Some(a % b) val iops = Map(("+", iadd), ("-", isub), ("*", imul), ("/", idiv), ("%", imod)) case class Z(var zs: String) { import Z._ require((zs.toSet -- Set('-', '0', '1') == Set()) && (!zs.contains("11"))) //--- fa(summand1.z,summand2.z) -------------------------- val fa: (BigInt, BigInt) => BigInt = (z1, z2) => { val v = z1.toString.toCharArray.map(_.asDigit).reverse.padTo(5, 0).zipAll(z2.toString.toCharArray.map(_.asDigit).reverse, 0, 0) val arr1 = (v.map(p => p._1 + p._2) :+ 0).reverse (0 to arr1.length - 4) foreach { i => //stage1 val a = arr1.slice(i, i + 4).toList val b = a.foldRight("")("" + _ + _) dropRight 1 val a1 = b match { case "020" => List(1, 0, 0, a(3) + 1) case "030" => List(1, 1, 0, a(3) + 1) case "021" => List(1, 1, 0, a(3)) case "012" => List(1, 0, 1, a(3)) case _ => a } 0 to 3 foreach { j => arr1(j + i) = a1(j) } } val arr2 = arr1.foldRight("")("" + _ + _) .replace("0120", "1010").replace("030", "111").replace("003", "100").replace("020", "101") .replace("003", "100").replace("012", "101").replace("021", "110") .replace("02", "10").replace("03", "11") .reverse.toArray (0 to arr2.length - 3) foreach { i => //stage2, step1 val a = arr2.slice(i, i + 3).toList val b = a.foldRight("")("" + _ + _) val a1 = b match { case "110" => List('0', '0', '1') case _ => a } 0 to 2 foreach { j => arr2(j + i) = a1(j) } } val arr3 = arr2.foldRight("")("" + _ + _).concat("0").reverse.toArray (0 to arr3.length - 3) foreach { i => //stage2, step2 val a = arr3.slice(i, i + 3).toList val b = a.foldRight("")("" + _ + _) val a1 = b match { case "011" => List('1', '0', '0') case _ => a } 0 to 2 foreach { j => arr3(j + i) = a1(j) } } BigInt(arr3.foldRight("")("" + _ + _)) } //--- fs(minuend.z,subtrahend.z) ------------------------- val fs: (BigInt, BigInt) => BigInt = (min, sub) => { val zmvr = min.toString.toCharArray.map(_.asDigit).reverse val zsvr = sub.toString.toCharArray.map(_.asDigit).reverse.padTo(zmvr.length, 0) val v = zmvr.zipAll(zsvr, 0, 0).reverse val last = v.length - 1 val zma = zmvr.reverse.toArray val zsa = zsvr.reverse.toArray for (i <- (0 to last).reverse) { val e = zma(i) - zsa(i) if (e < 0) { zma(i - 1) = zma(i - 1) - 1 zma(i) = 0 val part = Z(((i to last).map(zma(_))).foldRight("")("" + _ + _)) val carry = Z("1".padTo(last - i, "0").foldRight("")("" + _ + _)) val sum = part + carry val sums = sum.z.toString (1 to sum.size) foreach { j => zma(last - sum.size + j) = sums(j - 1).asDigit } if (zma(i - 1) < 0) { for (j <- (0 until i).reverse) { if (zma(j) < 0) { zma(j - 1) = zma(j - 1) - 1 zma(j) = 0 val part = Z(((j to last).map(zma(_))).foldRight("")("" + _ + _)) val carry = Z("1".padTo(last - j, "0").foldRight("")("" + _ + _)) val sum = part + carry val sums = sum.z.toString (1 to sum.size) foreach { k => zma(last - sum.size + k) = sums(k - 1).asDigit } } } } } else zma(i) = e zsa(i) = 0 } BigInt(zma.foldRight("")("" + _ + _)) } //--- fm(multiplicand.z,multplier.z) --------------------- val fm: (BigInt, BigInt) => BigInt = (mc, mp) => { val mct = mt(Z(mc.toString)) val mpxi = mp.toString.reverse.toCharArray.map(_.asDigit).zipWithIndex.filter(_._1 != 0).map(_._2) mpxi.foldRight(Z("0"))((fi, sum) => sum + mct(fi)).z } //--- fd(dividend.z,divisor.z) --------------------------- val fd: (BigInt, BigInt) => BigInt = (dd, ds) => { val dst = dt(Z(dd.toString), Z(ds.toString)).reverse var diff = Z(dd.toString) val zd = ListBuffer[String]() 0 until dst.length foreach { i => if (dst(i) > diff) zd += "0" else { diff = diff - dst(i) zd += "1" } } BigInt(zd.mkString) } val fasig: (Z, Z) => Int = (z1, z2) => if (z1.z.abs > z2.z.abs) z1.z.signum else z2.z.signum val fssig: (Z, Z) => Int = (z1, z2) => if ((z1.z.abs > z2.z.abs && z1.z.signum > 0) || (z1.z.abs < z2.z.abs && z1.z.signum < 0)) 1 else -1 var z: BigInt = BigInt(zs) override def toString: String = "" + z + "Z(i:" + z2i(this) + ")" def size: Int = z.abs.toString.length def ++ : Z = { val za = this + Z("1") this.zs = za.zs this.z = za.z this } def +(that: Z): Z = if (this == Z("0")) that else if (that == Z("0")) this else if (this.z.signum == that.z.signum) Z((fa(this.z.abs.max(that.z.abs), this.z.abs.min(that.z.abs)) * this.z.signum).toString) else if (this.z.abs == that.z.abs) Z("0") else Z((fs(this.z.abs.max(that.z.abs), this.z.abs.min(that.z.abs)) * fasig(this, that)).toString) def -- : Z = { val zs = this - Z("1") this.zs = zs.zs this.z = zs.z this } def -(that: Z): Z = if (this == Z("0")) Z((that.z * (-1)).toString) else if (that == Z("0")) this else if (this.z.signum != that.z.signum) Z((fa(this.z.abs.max(that.z.abs), this.z.abs.min(that.z.abs)) * this.z.signum).toString) else if (this.z.abs == that.z.abs) Z("0") else Z((fs(this.z.abs.max(that.z.abs), this.z.abs.min(that.z.abs)) * fssig(this, that)).toString) def %(that: Z): Option[Z] = if (that == Z("0")) None else if (this == Z("0")) Some(Z("0")) else if (that == Z("1")) Some(Z("0")) else if (this.z.abs < that.z.abs) Some(this) else if (this.z == that.z) Some(Z("0")) else this / that match { case None => None case Some(z) => Some(this - z * that) } def *(that: Z): Z = if (this == Z("0") || that == Z("0")) Z("0") else if (this == Z("1")) that else if (that == Z("1")) this else Z((fm(this.z.abs.max(that.z.abs), this.z.abs.min(that.z.abs)) * this.z.signum * that.z.signum).toString) def /(that: Z): Option[Z] = if (that == Z("0")) None else if (this == Z("0")) Some(Z("0")) else if (that == Z("1")) Some(Z("1")) else if (this.z.abs < that.z.abs) Some(Z("0")) else if (this.z == that.z) Some(Z("1")) else Some(Z((fd(this.z.abs.max(that.z.abs), this.z.abs.min(that.z.abs)) * this.z.signum * that.z.signum).toString)) def <(that: Z): Boolean = this.z < that.z def <=(that: Z): Boolean = this.z <= that.z def >(that: Z): Boolean = this.z > that.z def >=(that: Z): Boolean = this.z >= that.z } object Z { // only for comfort and result checking: val fibs: LazyList[BigInt] = { def series(i: BigInt, j: BigInt): LazyList[BigInt] = i #:: series(j, i + j) series(1, 0).tail.tail.tail } val z2i: Z => BigInt = z => z.z.abs.toString.toCharArray.map(_.asDigit).reverse.zipWithIndex.map { case (v, i) => v * fibs(i) }.foldRight(BigInt(0))(_ + _) * z.z.signum var fmts: Map[Z, List[Z]] = Map(Z("0") -> List[Z](Z("0"))) //map of Fibonacci multiples table of divisors // get division table (division weight vector) def dt(dd: Z, ds: Z): List[Z] = { val wv = new ListBuffer[Z] wv ++= mt(ds) var zs = ds.z.abs.toString val upper = dd.z.abs.toString while ((zs.length < upper.length)) { wv += (wv.toList.last + wv.toList.reverse.tail.head) zs = "1" + zs } wv.toList } // get multiply table from fmts def mt(z: Z): List[Z] = { fmts.getOrElse(z, Nil) match { case Nil => val e = mwv(z) fmts = fmts + (z -> e) e case l => l } } // multiply weight vector def mwv(z: Z): List[Z] = { val wv = new ListBuffer[Z] wv += z wv += (z + z) var zs = "11" val upper = z.z.abs.toString while ((zs.length < upper.length)) { wv += (wv.toList.last + wv.toList.reverse.tail.head) zs = "1" + zs } wv.toList } } println("elapsed time: " + elapsed { calcs foreach { case (op1, op, op2) => println("" + op1 + " " + op + " " + op2 + " = " + { (ops(op)) (op1, op2) match { case None => None case Some(z) => z case z => z } } .ensuring { x => (iops(op)) (z2i(op1), z2i(op2)) match { case None => None == x case Some(i) => i == z2i(x.asInstanceOf[Z]) case i => i == z2i(x.asInstanceOf[Z]) } }) } } + " sec" ) }