34

Cirdec's answer to a largely unrelated question made me wonder how best to represent natural numbers with constant-time addition, subtraction by one, and testing for zero.

Why Peano arithmetic isn't good enough:

Suppose we use

data Nat = Z | S Nat

Then we can write

Z + n = n
S m + n = S(m+n)

We can calculate m+n in O(1) time by placing m-r debits (for some constant r), one on each S constructor added onto n. To get O(1) isZero, we need to be sure to have at most p debits per S constructor, for some constant p. This works great if we calculate a + (b + (c+...)), but it falls apart if we calculate ((...+b)+c)+d. The trouble is that the debits stack up on the front end.

One option

The easy way out is to just use catenable lists, such as the ones Okasaki describes, directly. There are two problems:

  1. O(n) space is not really ideal.

  2. It's not entirely clear (at least to me) that the complexity of bootstrapped queues is necessary when we don't care about order the way we would for lists.

Community
  • 1
  • 1
dfeuer
  • 48,079
  • 5
  • 63
  • 167
  • 2
    What is `n` in `O(n)`? The magnitude of the number or the length of an input for it? What are the "catenable lists" Okasaki describes? – Cirdec Feb 25 '15 at 21:55
  • @Cirdec, good question. If you neglect decrements, it's the length of the input for it. With decrements, ... I'm not sure. – dfeuer Feb 25 '15 at 21:58
  • 2
    @Cirdec, I wouldn't be surprised if it were impossible to improve the space usage, now that I think more about it. O(1) addition is a very stringent requirement! – dfeuer Feb 25 '15 at 22:16
  • 2
    You can't get constant time addition. You can only get constant time if you limit the size of the numbers. – augustss Feb 25 '15 at 23:35
  • 2
    @augustss, how's that? Okasaki's catenable lists support O(1) append and O(1) decrement. – dfeuer Feb 25 '15 at 23:39
  • 3
    Not saying this is inappropriate for SO, but you might consider [compsci](http://scicomp.stackexchange.com/) as well. – Brett Hale Feb 26 '15 at 01:42
  • I'm not going to to read into that right now, but chapter 6 of _Purely Functional Data Structures_ is called "Numerical Representations" and deals, I think, with encoding list representations into number representations. Probably some insight can be gained from that. – phipsgabler Feb 26 '15 at 10:14
  • Are those queues real constant time or just amortized? – Niklas B. Feb 26 '15 at 15:37
  • 1
    @NiklasB., these are amortized, but real-time versions exist too. – dfeuer Feb 26 '15 at 15:38
  • Interesting. I think the o(n) space restriction might be a killer here, but not necessarily – Niklas B. Feb 26 '15 at 15:39
  • Can we assume the RAM model (i.e. O(1) operations for integers that fit into the words size w) and log log n = O(w)? – Niklas B. Feb 26 '15 at 15:59
  • Or in other words, can we assume that log log n fits into an `Int` – Niklas B. Feb 26 '15 at 16:07
  • 1
    @NiklasB., given the FP context, I would feel more comfortable with a pointer machine model (O(1) constructor application and pattern matching, with no other primitive operations), but even a slightly over-powered one would be interesting. – dfeuer Feb 26 '15 at 16:24
  • Singly linked lists should give you a simpler O(n) space solution. If you use `f (x:xs) (y:xs) = x : y : f xs ys` as the addition operation, this should give you O(1) amortized ops – Niklas B. Feb 26 '15 at 16:45
  • @NiklasB., can you explain that a bit more? In particular, how will that give the right bounds if you double a number repeatedly and then start decrementing? – dfeuer Feb 26 '15 at 17:05
  • The idea is that for every evaluation caused by a pattern match, there has to be at least one add operation before that whose thunk is not yet evaluated. It's a bit tough for me to prove amortized bounds in a lazy setting, but I think you can define the potential function in terms of the number of nodes in the DAG of thunks – Niklas B. Feb 26 '15 at 17:23
  • FWIW, here's a practical example of a repeated number of function applications: http://ideone.com/oe1uOv In particular since we don't evaluate the representation of 2^100000 completely, it doesn't take up a lot of space. In general we take at most O(min(n, m)) space where m is the number operations that lead to the representation the number or something like that. Take these bounds with a grain of salt, I find this analysis pretty confusing – Niklas B. Feb 26 '15 at 17:30
  • Nevermind, my analysis is wrong, although I can't find a sequence of operations that causes a degradation. – Niklas B. Feb 26 '15 at 18:41
  • 2
    @dfeuer: the other big player is the Church-encoded numbers, which represent lists as `flip (flip . foldr) list` and which acts like natural numbers if the underlying list has type `[()]`. It seems like the underlying `foldr` would give you O(1) appends and O(1) `isZero`, and you'd just need to throw amortization arguments at the predecessor function. – CR Drost Feb 26 '15 at 20:44
  • 1
    This threw me off completely at first: I was thinking of constant time addition in terms of security/timing attacks :) But it got me thinking, addition should be trivial constant time and linear space in base 1. But everything else is terrible in base 1! So why? I would like to know more about why this is an interesting problem. – starmole Mar 03 '15 at 06:21

3 Answers3

5

As far as I know, Idris (a dependently-typed purely functional language which is very close to Haskell) deals with this in a quite straightforward way. Compiler is aware of Nats and Fins (upper-bounded Nats) and replaces them with machine integer types and operations whenever possible, so the resulting code is pretty effective. However, that's not true for custom types (even isomorphic ones) as well as for compilation stage (there were some code samples using Nats for type checking which resulted in exponential growth in compile-time, I can provide them if needed).

In case of Haskell, I think a similar compiler extension may be implemented. Another possibility is to make TH macros which would transform the code. Of course, both of options aren't easy.

Yuuri
  • 1,858
  • 1
  • 16
  • 26
  • 1
    It is eagerly evaluated, so no matter how similar the type system, it's not going to be that similar. There are a lot of styles which are highly efficient in a lazy environment which are awful in an eager environment, and vice-versa. – Marcin Sep 08 '15 at 14:31
  • 2
    Idris naturals offer only logarithmic time operations once they exceed the machine word! – dfeuer Sep 08 '15 at 14:42
  • Indeed, machine integer types are logarithmic, not _O(1)_. They only appear to be constant-time for "small" enough numbers (that fit into a machine word). – Petr Oct 31 '15 at 20:49
4

My understanding is that in basic computer programming terminology the underlying problem is you want to concatenate lists in constant time. The lists don't have cheats like forward references, so you can't jump to the end in O(1) time, for example.

You can use rings instead, which you can merge in O(1) time, regardless if a+(b+(c+...)) or ((...+c)+b)+a logic is used. The nodes in the rings don't need to be doubly linked, just a link to the next node.

Subtraction is the removal of any node, O(1), and testing for zero (or one) is trivial. Testing for n > 1 is O(n), however.

If you want to reduce space, then at each operation you can merge the nodes at the insertion or deletion points and weight the remaining ones higher. The more operations you do, the more compact the representation becomes! I think the worst case will still be O(n), however.

  • 2
    The `n` in the problem description is the magnitude of the number, not the number of bits. I am very well aware that standard binary addition is O(log m+log n). This question is not talking about that form of addition at all. – dfeuer Mar 06 '15 at 14:58
  • Thank you, have revised based on the feedback. –  Mar 06 '15 at 15:39
  • 2
    Could be more specific about the data structure you're proposing? The question is about immutable, functional data structures, so in particular mutable pointers aren't allowed. Also, could you expand about weighting nodes? Normally you'd use numbers for weights, but of course here we're trying to represent numbers, assuming we don't have any yet. – Petr Mar 07 '15 at 08:22
3

We know that there are two "extremal" solutions for efficient addition of natural numbers:

  1. Memory efficient, the standard binary representation of natural numbers that uses O(log n) memory and requires O(log n) time for addition. (See also Chapter "Binary Representations" in the Okasaki's book.)

  2. CPU efficient which use just O(1) time. (See Chapter "Structural Abstraction" in the book.) However, the solution uses O(n) memory as we'd represent natural number n as a list of n copies of ().

    I haven't done the actual calculations, but I believe for the O(1) numerical addition we won't need the full power of O(1) FIFO queues, it'd be enough to bootstrap standard list [] (LIFO) in the same way. If you're interested, I could try to elaborate on that.

The problem with the CPU efficient solution is that we need to add some redundancy to the memory representation so that we can spare enough CPU time. In some cases, adding such a redundancy can be accomplished without compromising the memory size (like for O(1) increment/decrement operation). And if we allow arbitrary tree shapes, like in the CPU efficient solution with bootstrapped lists, there are simply too many tree shapes to distinguish them in O(log n) memory.

So the question is: Can we find just the right amount of redundancy so that sub-linear amount of memory is enough and with which we could achieve O(1) addition? I believe the answer is no:

Let's have a representation+algorithm that has O(1) time addition. Let's then have a number of the magnitude of m-bits, which we compute as a sum of 2^k numbers, each of them of the magnitude of (m-k)-bit. To represent each of those summands we need (regardless of the representation) minimum of (m-k) bits of memory, so at the beginning, we start with (at least) (m-k) 2^k bits of memory. Now at each of those 2^k additions, we are allowed to preform a constant amount of operations, so we are able to process (and ideally remove) total of C 2^k bits. Therefore at the end, the lower bound for the number of bits we need to represent the outcome is (m-k-C) 2^k bits. Since k can be chosen arbitrarily, our adversary can set k=m-C-1, which means the total sum will be represented with at least 2^(m-C-1) = 2^m/2^(C+1) ∈ O(2^m) bits. So a natural number n will always need O(n) bits of memory!

Community
  • 1
  • 1
Petr
  • 62,528
  • 13
  • 153
  • 317
  • 2
    @dfeuer Because each of them is of the magnitude of _(m-k)_ bits, there are _2^(m-k)_ such numbers, so we need _(m-k)_ bits of information to distinguish them - we can't get beyond that. We could use some kind of compression and use less actual bits for some numbers, but then we'd need more bits for other numbers. And since this needs to hold for any sum, [obviously](http://www.netfunny.com/rhf/jokes/90q2/obvious.html) the adversary can choose summands that have _(m-k)_ bits or more. – Petr Nov 01 '15 at 08:10