ternary.rs

// playground for ternary arithmetic
// {-1, 0, 1} are represented by {0b10, 0b00, 0b01} respectively
// 0b11 is unused.

use prettytable::table;
use rand::seq::SliceRandom;

fn main() {
  test_add_1();
  test_add_32(1000);
}

fn test_add_32(n: usize) {
  let f = |a, b| f_bin_32(|a, b| a + b, add_32, a, b);
  for _i in 0..n {
    let a = gen_32();
    let b = gen_32();
    if let Some(x) = f(a, b) {
      println!("{x}");
      return;
    }
  }
  println!("Done");
}

fn gen_32() -> u64 {
  let vs: [u8; 3] = [0b00, 0b01, 0b10];
  let mut o = 0;
  for i in 0..32 {
    let a = vs.choose(&mut rand::thread_rng()).unwrap();
    o |= (*a as u64) << (i * 2);
  }
  o
}

fn test_add_1() {
  let f = |a, b| f_bin_1(|a, b| a + b, add_1, a, b).unwrap_or("OK".to_string());
  let tab = table!(
    ["A\\B", "00", "01", "10"],
    ["00", f(0b00, 0b00), f(0b00, 0b01), f(0b00, 0b10)],
    ["01", f(0b01, 0b00), f(0b01, 0b01), f(0b01, 0b10)],
    ["10", f(0b10, 0b00), f(0b10, 0b01), f(0b10, 0b10)]
  );
  tab.printstd();
}

fn f_bin_32(
  op: impl Fn(i8, i8) -> i8,
  op2: impl Fn(u64, u64) -> u64,
  a: u64,
  b: u64,
) -> Option<String> {
  let c = op2(a, b);
  let t = target_32(op, a, b);
  if c == t {
    return None;
  }

  Some(format!(
    "{:064b} + \n{:064b} = \n{:064b} != \n{:064b}",
    a, b, c, t
  ))
}

fn f_bin_1(
  op: impl Fn(i8, i8) -> i8,
  op2: impl Fn(u8, u8) -> u8,
  a: u8,
  b: u8,
) -> Option<String> {
  let c = op2(a, b);
  let t = target_1(&op, a, b);
  if c == t {
    None
  } else {
    Some(format!("{:02b} != {:02b}", c, t))
  }
}

// 64 / 2 = 32 ternary numbers {-1: 0b10, 0: 0b00, 1: 0b01}
fn add_32(a: u64, b: u64) -> u64 {
  let mut x = a | b;
  let mut mask = ((x & 0xaaaaaaaa_aaaaaaaa) >> 1) & x;
  mask |= mask << 1;
  x ^= mask;
  x
}

fn add_1(a: u8, b: u8) -> u8 {
  let mut x = a | b;

  // mask == 0b11 if x == 0b11, and 0b00 otherwise
  let mut mask = (x >> 1) & x;
  mask |= mask << 1;
  // flip the mask
  x ^= mask;

  // equivalent to:
  // if x == 0b11 { x = 0b00; }
  x
}

fn target_32(op: impl Fn(i8, i8) -> i8, a: u64, b: u64) -> u64 {
  let mut o = 0;
  for i in 0..32 {
    let offset = i * 2;
    let a = a >> offset & 0b11;
    let b = b >> offset & 0b11;
    let c = target_1(&op, a as u8, b as u8);
    o |= (c as u64) << offset;
  }
  o
}

fn target_1(op: &impl Fn(i8, i8) -> i8, a: u8, b: u8) -> u8 {
  let u2i = |v| match v {
    0b00 => 0,
    0b01 => 1,
    0b10 => -1,
    _ => panic!("Invalid input"),
  };
  let i2u = |v| match v {
    0 => 0b00,
    v if v > 0 => 0b01,
    v if v < 0 => 0b10,
    _ => panic!("Invalid input"),
  };
  let aa = u2i(a);
  let bb = u2i(b);
  let cc = op(aa, bb);
  i2u(cc)
}