Numeric representations without machine primitives

Question

Summary

Publication of examples in any language of the type representing integers, without the direct use of machine integers. Include mappings in and out of the user type. Points for efficiency in space and / or time.

Original question

In the comments, some rather bold answer to the question about object-oriented programming, I stated my belief that machine primitives are not objects, but could not really confirm this statement in the same way as the poster of this answer could not substantiate my claims about universality and the fundamental nature of object-oriented philosophy.

So that made me think. In C ++, a language in which machine primitives do not participate in the class hierarchy, you can determine the type of object: mdash, say, Integer & mdash, which does not use the machine primitive to store its value?

There is this beautiful bit of a pattern hacker that implements church numbers. Unfortunately, since conversions between integers and Church numbers occur strictly during compilation, there is no way to get around using machine integers, for example, for user input.

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

Bonus points for placing all integers (i.e., not only integers), and bonus points for developing a system in which floating point numbers can also be implemented.

To avoid troubles in the queue and encourage a polite discussion, I have been doing this with the wiki community question from the very beginning.

Answer 1

here is a class that can be used for positive integers. and it could easily be extended to negatives. it supports addition, subtraction, equality, inequality and multiplication. The unit can be implemented based on existing operators. So overall, I would say that it pretty much represents integers, and there are no simple types. In fact, the only type that the class uses is itself.

The implementation is basically a list of links with some optimization, so moving the list is not required for each 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

Always Lisp, in which 0 can be represented as () (empty list), 1 - (()) , 2 - (() ()) , etc. It was proven back on the same day, but Of course, the Lisp implementation actually uses this, as it is too slow to believe.