Urbit: A clean-slate functional OS
You say addition is O(n^2), but I think you can write an O(n) addition with only increment, recursion, and equality testing.<p>In Python syntax:<p><pre><code>  def add(a, b):
    return add_r(a, b, 0)

  def add_r(a, b, c):
    if b == c: 
      return a
    else:
      return add_r(a, b, c+1) +1</code></pre>