This task is a total immersion zeckendorf task; using decimal numbers will attract serious disapprobation.

The task is to implement addition, subtraction, multiplication, and division using Zeckendorf number representation. Optionally provide decrement, increment and comparitive operation functions.

Addition
Like binary 1 + 1 = 10, note carry 1 left. There the similarity ends. 10 + 10 = 101, note carry 1 left and 1 right. 100 + 100 = 1001, note carry 1 left and 2 right, this is the general case.

Occurrences of 11 must be changed to 100. Occurrences of 111 may be changed from the right by replacing 11 with 100, or from the left converting 111 to 100 + 100;

Subtraction
10 - 1 = 1. The general rule is borrow 1 right carry 1 left. eg:

  abcde
  10100 -
   1000
  _____
    100  borrow 1 from a leaves 100
  + 100  add the carry
  _____
   1001

A larger example:

  abcdef
  100100 -
    1000
  ______
  1*0100 borrow 1 from b
   + 100 add the carry
  ______
  1*1001

Sadly we borrowed 1 from b which didn't have it to lend. So now b borrows from a:

    1001
  + 1000 add the carry
    ____
   10100

Multiplication
Here you teach your computer its zeckendorf tables. eg. 101 * 1001:

  a = 1 * 101 = 101
  b = 10 * 101 = a + a = 10000
  c = 100 * 101 = b + a = 10101
  d = 1000 * 101 = c + b = 101010

  1001 = d + a therefore 101 * 1001 =
 
  101010
   + 101
  ______
 1000100

Division
Lets try 1000101 divided by 101, so we can use the same table used for multiplication.

  1000101 -
   101010 subtract d (1000 * 101)
  _______
     1000 -
      101 b and c are too large to subtract, so subtract a
     ____
        1 so 1000101 divided by 101 is d + a (1001) remainder 1

Efficient algorithms for Zeckendorf arithmetic is interesting. The sections on addition and subtraction are particularly relevant for this task.

 
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"
  )
 
}
 