Build a numerical library without using any primitive data type The task is to build a numerical library for working with arbitrarily large integers that supports the following operations:


addition
subtraction
multiplication
division
modulo operation


However, the library must not use any primitive data types or arrays, neither directly nor indirectly (including booleans). For example, if you use Java, you can neither use AtomicInteger (because it uses bool internally) nor HashMap (because it uses arrays internally). You'll need to create your own data structures, without using any primitive data types, to represent numbers. (Inherited methods such as Java's hashCode don't count, as long as you don't use them in any way.) The only exception is local use of booleans in order to use conditionals (see the clarification points below).

There is only one exception: In order to make your library actually testable, provide two functions to convert from and to native integer representation. For example:

int toNative(MyNum n) { ... }
MyNum fromNative(int n) { ... }


This is the only part of your code that can use built-in data types, and it must not do anything except the conversion.

If in doubt, please ask.

Criteria: The code should be elegant, readable, concise (but no code-golf, readability is more important than code size),  well documented, and if possible, asymptotically efficient (provide and justify your functions asymptotic time and space complexity). The most up-voted answer in 10 days wins.



Update: Since the puzzle seemed impossible to many people, let me give a hint:

public abstract class Nat {
    public static Nat fromInt(int n) {
        Nat r = new Zero();
        for(int i = 0; i &lt; n; i++)
            r = new Succ(r);
        return r;
    }

    public static int toInt(Nat n) {
        int i = 0;
        for(Nat m = n; m instanceof Succ; m = ((Succ)m).n)
            i++;
        return i;
    }
}

final class Zero extends Nat {
}

final class Succ extends Nat {
    public final Nat n;

    public Succ(Nat n) {
        this.n = n;
    }
}


This allows to represent any natural number without primitive types, even though not very efficiently.

To further clarify:


Pointers are allowed to work with data structures as long as you use them only as opaque references. In particular, you may not use any pointer arithmetic.
NULL/nulls are allowed.
If the language of your choice requires it, you can use booleans (or a similar data type) for conditionals, but only locally in functions/methods, not as fields in your data structures, and you can't use anything beyond boolean operations. Bonus if you manage it without booleans (many languages are capable of that, such as those that use pattern matching).
Higher-level languages are better suited for the puzzle.
Haskell

Haskell is pretty good at defining obvious things from scratch.
Almost all definitions are simple translations of math axioms.
Doesn't support negative numbers, behaves badly on errors (e.g. 1-2 or 1/0).

data MyNum = Zero | S MyNum

toNative :: MyNum -&gt; Integer
toNative Zero = 0
toNative (S n) = (toNative n) + 1
fromNative :: Integer -&gt; MyNum
fromNative 0 = Zero
fromNative n = S $ fromNative $ n-1

-- numIfGE a b c = c if a&gt;=b else 0
numIfGE _ Zero n = n
numIfGE Zero _ n = Zero
numIfGE (S a) (S b) n = numIfGE a b n

instance Num MyNum where
    a + Zero = a
    a + (S b) = S (a + b)

    a - Zero = a
    (S a) - (S b) = a - b

    a * Zero = Zero
    a * (S b) = a + (a*b)

a `divi` b = numIfGE a b (S $ (a - b) `divi` b)
a `modu` b = a - ((a `divi` b) * b)