Numeric Representations Without Machine Primitives

Question

Synopsis

Post examples in any language of a type that represents integers without making direct use of machine integers. Include mappings to and from the user-defined type. Points for efficiency in space and/or time.

Original Question

In the comments of a certain rather bold answer to a question about object-oriented programming, I stated my belief that machine primitives are not objects, but was unable to really substantiate that claim, in the same way that the poster of that answer was unable to substantiate his claims about the universality and fundamental nature of object-oriented philosophy.

So that got me to thinking. In C++, a language in which machine primitives do not participate in the class hierarchy, is it possible to define an object type—say, Integer—that does not make use of a machine primitive to store its value?

There is this beautiful bit of template hackery that implements Church numerals. Unfortunately, since the conversions between whole numbers and Church numerals occurs strictly at compile time, there's no way to get around using machine integers for, say, user input.

So what I'm looking for is a runtime equivalent of the above, though not necessarily using Church numerals, with reasonable space requirements, that can be implemented in a language such as C++ without higher-order functions. I'd like to see examples in other languages, as well, especially those that make use of fun dynamic typing tricks. Pointers and function pointers shall not count as primitives as long as the stored address is used strictly as such and not for its integral value.

Bonus points for accommodating all integers (i.e., not just whole numbers), and super bonus points for devising a system in which floating-point numbers can also be implemented.

To avoid any unpleasantness down the line, and to encourage polite discussion, I'm making this a community wiki question from the start.

Answer 1

here a class that can be used for positive integers. and could easily be extended to account for negatives as well. it supports addition, subtraction, equality, inequality and multiplication. Division can be implmented based on the existing operators. So all in all I'd say it pretty much represents integers and there's no use of any simple types. Actually the only type the class uses is it self.

The implementation is basically a link list with some optimization so that traversing of the list ain't needed for every operation.

public class MyInt
    {
        private MyInt _previous;
        private MyInt _first;
        private bool isEven;

        private MyInt(MyInt previous)
        {
            next++;
            _previous = previous;
            isEven = previous == null ? true : !previous.isEven;
            getFirst();
            x = next;
        }

        private void getFirst()
        {
            if (_previous == null)
                _first = null;
            else if (_previous._first == null)
                _first = this;
            else
                _first = _previous._first;
        }

        private MyInt(MyInt copy, bool dontuse)
        {
            _previous = copy._previous == null ? null : new MyInt(copy._previous,true);
            getFirst();
            x = copy.x;
        }

        public static MyInt operator +(MyInt lhs, MyInt rhs)
        {
            if (object.ReferenceEquals(lhs, rhs))
                rhs = new MyInt(rhs, true);
            if (lhs == MyInt.Zero)
                return rhs;
            if (rhs == MyInt.Zero)
                return lhs;
            else
            {
                var isEven = rhs.isEven == lhs.isEven;
                var result = new MyInt(rhs, true);
                result._first._previous = lhs;
                result._first = lhs._first;
                result.isEven = isEven;
                return result;
            }
        }

        public static MyInt operator -(MyInt lhs, MyInt rhs)
        {
            if (lhs == rhs)
                return MyInt.Zero;
            if (rhs == MyInt.Zero)
                return lhs;
            if (lhs == MyInt.Zero)
                throw new InvalidOperationException("Negatives not supported");
            else
            {
                return lhs._previous - rhs._previous;
            }
        }

        public static MyInt operator --(MyInt un)
        {
            if (un == MyInt.Zero)
                throw new InvalidOperationException("Negatives not supported");
            return un._previous;
        }

        public static MyInt operator *(MyInt lhs, MyInt rhs)
        {
            if (lhs == MyInt.Zero || rhs == MyInt.Zero)
                return MyInt.Zero;

            var temp = lhs;
            var one = One;
            var two = one + one;
            var zero = MyInt.Zero;
            var dbl = lhs + lhs;
            if (rhs == MyInt.One)
                return lhs;
            if (rhs == two)
                return dbl;
            for (MyInt times = rhs + one; times._previous._previous != zero && times._previous != zero; times = times-two)
            {
                temp = temp + dbl;
            }
            if (rhs.isEven)
                temp = temp - lhs;
            return temp;
        }

        public static bool operator ==(MyInt lhs, MyInt rhs)
        {
            if (object.ReferenceEquals(lhs, null) && object.ReferenceEquals(rhs, null))
                return true;
            if ((object.ReferenceEquals(lhs, null) || object.ReferenceEquals(rhs, null)))
                return false;
            if (object.ReferenceEquals(lhs._previous, null) && object.ReferenceEquals(rhs._previous, null))
                return true;
            if ((object.ReferenceEquals(lhs._previous, null) || object.ReferenceEquals(rhs._previous, null)))
                return false;

            return (lhs._previous == rhs._previous);
        }

        public static bool operator !=(MyInt lhs, MyInt rhs)
        {
            return !(lhs == rhs);
        }

        public override bool Equals(object obj)
        {
            return obj is MyInt && ((MyInt)obj) == this;
        }

        public static MyInt Zero
        {
            get
            {
                return new MyInt(null);
            }
        }

        public static MyInt One
        {
            get
            {
                return new MyInt(new MyInt(null));
            }
        }
    }

Answer 2

There's always Lisp, in which 0 can be represented as () (the empty list), 1 is (()), 2 is (() ()), etc. This was proved way back in the day, but of course no Lisp implementation actually uses that, as it's too slow to believe.