Computers are of course called "computers" because they're good at math; there are lots of ways to do math in C#. We've got signed and unsigned integers and binary and decimal floating point types built into the language. And it is easy to use types in libraries such as
From a practical perspective, for the vast majority of programmers who are not developing those libraries, this is a solved problem; you can use these tools without really caring very much how they work. Sure, there are lots of pitfalls with binary floats that we've talked about many times in this blog over the years, but these are pretty well understood.
So it's a little bit quixotic of me to start this series, in which I'm going to set myself the challenge of implementing arbitrary-size integer2 arithmetic without using any built-in types other than
My solution is not going to be pragmatic. It's going to use immense amounts of memory, it is going to be orders of magnitude slower than
Before we get to the integers though we're going to start with the naturals. The naturals are the numbers 0, 1, 2, 3, ... and so on; they're the "counting numbers". We can loosely4 define the natural numbers recursively:
I seem to recall that Hofstadter uses
We could choose any of these, or come up with yet another way to represent numbers. For the purposes of this series I'm going to stick with the final one: a natural number is represented by a series of bits.
Next time on FAIC: the natural numbers zero and one.
BigInteger and BigRational1 to represent arbitrary-sized integers and arbitrary-precision rationals.From a practical perspective, for the vast majority of programmers who are not developing those libraries, this is a solved problem; you can use these tools without really caring very much how they work. Sure, there are lots of pitfalls with binary floats that we've talked about many times in this blog over the years, but these are pretty well understood.
So it's a little bit quixotic of me to start this series, in which I'm going to set myself the challenge of implementing arbitrary-size integer2 arithmetic without using any built-in types other than
object and bool.3My solution is not going to be pragmatic. It's going to use immense amounts of memory, it is going to be orders of magnitude slower than
BigInteger, and almost all my algorithms are going to be recursive. Since C# is not a tail-recursive language, this means that they'll blow up with stack overflow exceptions when given numbers of only a few hundred bits. But hopefully we'll learn something about both mathematics and recursive data structures along the way.Before we get to the integers though we're going to start with the naturals. The naturals are the numbers 0, 1, 2, 3, ... and so on; they're the "counting numbers". We can loosely4 define the natural numbers recursively:
- 0 is a natural number.
- The successor of a natural number is a natural number.
I seem to recall that Hofstadter uses
0, S0, SS0, SSS0, and so on, to represent the naturals. A standard way to represent the naturals in set theory is to say that a natural number is represented by the set of all natural numbers smaller than it. So zero, having no natural numbers smaller than it, is the empty set, {}. One has only zero smaller than it, so it is {{}}. Two has zero and one smaller than it, so it is {{},{{}}}. Three is {{}, {{}}, {{},{{}}}}. And so on. The Church numerals use elements of the lambda calculus to represent natural numbers. We of course typically use a complicated decimal convention whereby a string of digits compactly represents a number as a series of multiplications and additions. And computers use a similar but simpler convention in which a string of bits represents a number.We could choose any of these, or come up with yet another way to represent numbers. For the purposes of this series I'm going to stick with the final one: a natural number is represented by a series of bits.
Next time on FAIC: the natural numbers zero and one.
- Which can be found in the Microsoft Solver Foundation library.
- Maybe we'll go further into rationals as well; we'll see how long this takes!
- As we'll see, we'll be forced to use
intandstringin one or two places, but they will all be away from the main line of the code. I will also be using the standard exception classes to indicate error conditions such as dividing by zero. - A proper definition would also include restrictions like "zero is not the successor of any number" and "unequal numbers have unequal successors" and so on, but we don't need to take a formal axiomatic approach for the purposes of this series.
Sign up here with your email
ConversionConversion EmoticonEmoticon