Category Archives: Mathematics

Math from scratch, part one

Posted on by
39

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 BigInteger and BigRational[1. Which can be found in the Microsoft Solver Foundation library.] 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 integer[2. Maybe we’ll go further into rationals as well; we’ll see how long this takes!] arithmetic without using any built-in types other than object and bool.[3. As we’ll see, we’ll be forced to use int and string in 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.]

Continue reading →

Why not allow double/decimal implicit conversions?

Posted on by
43

I’ve talked a lot about floating point math over the years in this blog, but a quick refresher is in order for this episode.

A double represents a number of the form +/- (1 + F / 252 ) x 2E-1023, where F is a 52 bit unsigned integer and E is an 11 bit unsigned integer; that makes 63 bits and the remaining bit is the sign, zero for positive, one for negative. You’ll note that there is no way to represent zero in this format, so by convention if F and E are both zero, the value is zero. (And similarly there are other reserved bit patterns for infinities, NaN and denormalized floats which we will not get into today.)

A decimal represents a number in the form +/- V / 10X where V is a 96 bit unsigned integer and X is an integer between 0 and 28.

Both are of course “floating point” because the number of bits of precision in each case is fixed, but the position of the decimal point can effectively vary as the exponent changes.
Continue reading →

Spot the defect: rounding, part two

Posted on by
27

Last time I challenged you to find a value which does not round correctly using the algorithm

Math.Floor(value + 0.5)

The value which does not round correctly is the double 0.49999999999999994, which is the largest double that is smaller than 0.5. With the given algorithm this rounds up to 1.0, even though clearly 0.49999999999999994 is less than one half, and therefore should round down.

What the heck is going on here?

Continue reading →

Spot the defect: rounding

Posted on by
32

The intention of this method is to round a double to the nearest integer. If the double is exactly half way between two integers then it rounds to the larger of the two possibilities:[1. For negative numbers, -1.5 should round to -1.0, since -1.0 is larger than -2.0; I do not mean larger in the sense of absolute magnitude. That would be characterized as “midpoint rounding away from zero”.]

static double MyRound(double d)
{
  return Math.Floor(d + 0.5);
}

Is it correct? Can you find a value for which it does not give the mathematically correct value?[2. HINT: The value I’m thinking of is small.]

UPDATE: The answer is in the comments, so if you don’t want spoilers, don’t read the comments.

Next time on FAIC: The answer, of course.

Producing permutations, part seven

Posted on by
6

Last time on FAIC I generated a “random” permutation of a deck of cards and gave you the first five cards, and challenged you to determine what the next five cards were. David Poeschl (of the Roslyn team!) was the first to get a possible order and, with the additional hint that the sixth card was the three of hearts, Joel Rondeau found the correct solution, which is below. Both used brute-force algorithms.

Continue reading →

Producing permutations, part six

Posted on by
25

Last time in this series I presented an algorithm for generating a random number, and the time before I presented an algorithm that turns such a number into a permutation, so we can put them together to make an algorithm that returns a random permutation:

static Permutation RandomPermutation(int size, Random random)
{
  return Permutation.NthPermutation(size, RandomFactoradic(size, random));
}

Is this actually a correct algorithm for generating a random permutation? Give it some thought.

Continue reading →

Producing permutations, part four

Posted on by
8

Last time on FAIC I implemented a short algorithm that produces a sequence containing every permutation of a given size, such that the sequence is a Hamiltonian tour of the vertices of the n-dimensional permutohedron. That is, the shape you get when you make each vertex have the coordinates of a permutation, and an edge connects two permutations that differ only by a swap of adjacent items.

Since we have an algorithm that produces the same order every time, we can number each ordering; it is convenient to do so starting with zero and going to n!-1. What I’d like is an algorithm which given size, the number of items in the permutation, and index, an integer between zero and size!-1, gives back the indexth permutation of length size, without having to calculate all of them.

Continue reading →