Skip to contentSkip to author details

Mathematics

A 4-post collection

Solving the Stable Marriage problem on an FPGA (Part 2)

Written by Michael Earls
 Mathematics  FPGA  electronics  programming

In part 1, I introduced the Stable Marriage problem and proposed implementing it on an FPGA.

In this post, I will define the approach I am taking to define the preferences in binary form.

Series entries:

Note: Blog title image used without permission (pending) from numberphile.com

Since we're only dealing with eight people (four women and four men), I decided to use a 2-bit number to define the Id number of the person within their gender.

With a 2-bit number, that gives us the following Id's to work with (per gender):

  • Person #1 - 00
  • Person #2 - 01
  • Person #3 - 10
  • Person #4 - 11

To define the preferences for each person, we can take advantage of the fact that we're only using 2-bits per id and only have four preferences. That means we can use a single byte to define the preferences, with the most significant 2 bits being the first choice.

Here is a table to illustrate some sample preferences:

Proposal Table (Decimal)

Females
Id 1st 2nd 3rd 4th
1 2 1 4 3
2 2 4 3 1
3 2 1 4 3
4 4 3 2 1
Males
Id 1st 2nd 3rd 4th
1 4 3 2 1
2 3 1 2 4
3 4 3 1 2
4 2 4 3 1

So, let's take a look at our proposal cycles using this table:

First cycle

Here are the proposals:

  • Woman 1: Man 2
  • Woman 2: Man 2
  • Woman 3: Man 2
  • Woman 4: Man 4

So, Man 2 now has 3 proposals (Woman 1, Woman 2, and Woman 3). If we look at his preferences (3, 1, 2, 4), we see that he prefers Woman 3 over Women 1 and 2, so he declines them and accepts a tentative proposal from Woman 3 (since this is the first match and they both are top of each other's list, they won't be matched with another person, but that is a fact that we can deduce as humans that we can't expect the machine to know).

Woman 4 is tentatively engaged to Man 4.

Women 1 and 2 are left out because they were declined, so they'll propose to their second choice on the second cycle.

At the end of the cycle we have the following state for the Women:

  • Woman 1: unmatched
  • Woman 2: unmatched
  • Woman 3: tentatively engaged to Man 2
  • Woman 4: tentatively engaged to Man 4

Second cycle

Here are the choices

  • Woman 1: Man 1
  • Woman 2: Man 4
  • Woman 3: N/A (tentatively engaged)
  • Woman 4: N/A (tentatively engaged)

Woman 1 proposes to her 2nd choice, Man 1. Man 1 has not been proposed to yet, so he'll accept.

Woman 2 proposes to Man 4, but he is tentatively engaged to Woman 4. However, since Woman 2 is his first choice, he declines Woman 4 and "trades up" to accept the new proposal from Woman 2.

This leaves Woman 4 alone to propose in the third cycle.

At the end of the cycle we have the following state for the Women:

  • Woman 1: tentatively engaged to Man 1
  • Woman 2: tentatively engaged to Man 4
  • Woman 3: tentatively engaged to Man 2
  • Woman 4: unmatched

Third cycle

Here are the choices

  • Woman 1: N/A (tentatively engaged)
  • Woman 2: N/A (tentatively engaged)
  • Woman 3: N/A (tentatively engaged)
  • Woman 4: Man 2

So, Woman 4 proposes to Man 2, but he prefers his current fiance, so he declines her.

At the end of the cycle we have the following state for the Women:

  • Woman 1: tentatively engaged to Man 1
  • Woman 2: tentatively engaged to Man 4
  • Woman 3: tentatively engaged to Man 2
  • Woman 4: (still) unmatched

Fourth cycle

Here are the choices

  • Woman 1: N/A (tentatively engaged)
  • Woman 2: N/A (tentatively engaged)
  • Woman 3: N/A (tentatively engaged)
  • Woman 4: Man 1

Woman 4 proposes to Man 1, but he is tentatively engaged to Woman 1. However, Woman 4 is is top choice, so he declines Woman 1's proposal and "trades up" to accept Woman 4's proposal.

This leaves Woman 1 alone again, forcing her to propose in the next cycle.

At the end of the cycle we have the following state for the Women:

  • Woman 1: unmatched
  • Woman 2: tentatively engaged to Man 4
  • Woman 3: tentatively engaged to Man 2
  • Woman 4: tentatively engaged to Man 1

Fifth cycle

Here are the choices

  • Woman 1: Man 4
  • Woman 2: N/A (tentatively engaged)
  • Woman 3: N/A (tentatively engaged)
  • Woman 4: N/A (tentatively engaged)

Woman 1 proposes to Man 4, but he is already engaged to his top preference, so he declines her proposal. This leaves her alone again for the next cycle.

At the end of the cycle we have the following state for the Women:

  • Woman 1: (still) unmatched
  • Woman 2: tentatively engaged to Man 4
  • Woman 3: tentatively engaged to Man 2
  • Woman 4: tentatively engaged to Man 1

Sixth cycle

Here are the choices

  • Woman 1: Man 3
  • Woman 2: N/A (tentatively engaged)
  • Woman 3: N/A (tentatively engaged)
  • Woman 4: N/A (tentatively engaged)

Woman 1 proposes to Man 3, who is currently free, so he accepts her proposal.

At the end of the cycle we have the following state for the Women:

  • Woman 1: tentatively engaged to Man 3
  • Woman 2: tentatively engaged to Man 4
  • Woman 3: tentatively engaged to Man 2
  • Woman 4: tentatively engaged to Man 1

We now have no more unmatched Women, so our cycles are complete and we have stable marriages.

Here are the final results:

  • Woman 1: engaged to Man 3
  • Woman 2: engaged to Man 4
  • Woman 3: engaged to Man 2
  • Woman 4: engaged to Man 1

Here is the proposal table in binary (with 2-bit Id's)

Females
Id 1st 2nd 3rd 4th
00 01 00 11 10
01 01 11 10 00
10 01 00 11 10
11 11 10 01 00
Males
Id 1st 2nd 3rd 4th
00 11 10 01 00
01 10 00 01 11
10 11 10 00 01
11 01 11 10 00

So to represent the preferences of the Women, we simply create a byte containing their preferences.

Here they are for each woman:

  • Woman 1 (00) - 01001110
  • Woman 2 (01) - 01111000
  • Woman 3 (10) - 01001110
  • Woman 4 (11) - 11100100

Note: It's important to notice that I'm referring to them in 1-based decimal (Woman 1, 2, 3, 4), but 0-based binary (Woman 00, Woman 01, Woman 10, Woman 11).

So, to represent these preferences we simply need four sets of 4-bit numbers representing the matching for the women. So, our final results would look like this in binary:

0010 0111 1001 1100

I'm not considering how to scale this out, yet, so I'm making some assumptions on the feasibility of using 2-bit id's rather than full bytes. In the end, a full byte will give us more people, but I wanted to keep this simple. I hope by starting this way I don't adversely effect the overall solution.

Now that I've established the preferences and a way to represent them in binary, I need to figure out the best way to store them and run the cycles on the FPGA.

Next up, defining our finite state machines (FSMs).

Solving the Stable Marriage problem on an FPGA (Part 1)

Written by Michael Earls
 Mathematics  FPGA  programming

At my last client, there was an issue that came up that required matching between two groups. It had to be a fair matching based on preferences of both sides. I first started by writing my own algorithm, but I quickly realized that someone has to have come up with something to do this already. I was right. Not only had someone(s) figured the problem out, they received a Nobel Prize for their work (good thing I didn't try to tackle it on my own).

Note: Blog title image used without permission (pending) from numberphile.com

Series entries:

The algorithm is named after the two mathematicians who discovered it: the Gale–Shapley algorithm, or commonly called the Stable Marriage Problem (or stable matching problem - SMP). I'll let you read about it on Wikipedia as I don't just want to repeat what's already there. Basically, it's also used in the National Resident Matching Program to help match medical students to residency programs, so it has real-world applications beyond the classroom.

Here is a great video describing the algorithm in layman's terms:

And for some deeper math, here is the follow-up to that video:

I became obsessed with this algorithm while working with the client because they had some unique ways of determining preferences beyond just saying "I like guy 2". There had to be more to it. "I like guy 2 because...".

My work obsession happened to coincide with my home obsession of learning how to utilize and develop on FPGAs. Again, I'll let you read the details, but the best way to describe an FPGA (compared to a microcontroller like the Arduino or Raspberry Pi) is as follows (I read this somewhere on the Internet and it stuck in my head):

  • You tell a microcontroller what to do.
  • You tell an FPGA what to be

There's a nuance there that has enormous implications on the differences between the two. FPGAs are much faster than microcontrollers because all of the logic runs in parallel, whereas a microcontroller has to run a program in a tight loop and constantly check and update the status of its IO pins. Every time you add a new task to a microcontroller's program, you slow it down.

Here is a video from Microsoft's Channel 9 discussing research they are doing on using FPGAs in the data center (Bing specifically) to increase performance and save energy:

Since the SMB algorithm can be so processor-intensive, I thought it might be cool to implement it on FPGA hardware to see if I can pull it off.

To keep things simpler for me, my initial approach is only going to deal with 8 total people: 4 women, and 4 suitors. I will take the "women propose" approach as discussed in the video above.

Next: Establishing the preferences...

How I accidentally learned something unexpected from a simple binary counter

Written by Michael Earls
 electronics  Mathematics  programming  binary

In my previous post, I talked about how I implemented a binary counter with my Mojo FPGA board.

I am working on a follow-up post on implementing a reverse binary counter with a switch that lets you change between the incrementing ( UP ) counter and the decrementing ( DOWN ) counter.

I accidentally discovered a property of 8 bit numbers. It's referred to as the "Ones' complement".

When you add a number n between 0 and 255 to an 8-bit binary representation of 0, the same number n subtracted from 255 will be the binary inverse (bit complement) of the first number.

To demonstrate, let's say we start with an 8-bit number at 0:

00000000

Now, we add 2:

00000010

OK, let's look what happens when we have 255:

11111111

Now, let's subtract 2:

11111101

So, comparing them, one above the other, we can see that they are inverse:

00000010  
11111101

This is true for all numbers between 0 and 255 (the only assertion I can personally make through observation).

So, in my original implementation of the reverse binary counter, I was using two counters to keep up with the numbers; one that started at 0 and counted up, and one that started at 255 and counted down.

As I switched between the two to test my design, I noticed the inversion almost immediately. This might be a neat trick when you want to flash LED's, too.

I think a more efficient implementation to replace the DOWN counter is to apply a simple inverter to each bit.

ones' complement inverter for 8-bit number ones' complement inverter for 8-bit number

This is what happens when you learn in reverse. Rather than simply being taught this in a ten minute aside from a lecture, I had to accidentally discover it. I'm learning electronics engineering from a hobbyists perspective, so I'm avoiding the theory and the complex math that makes it actual engineering. I'm sure I'll learn a lot more in the coming years.

This hobby never stops giving...

What lies beyond the limits of Mathematics?

Written by Michael Earls
 featured  macrocosm  Mathematics  microcosm  Universe

I’ve been thinking about the universe lately and I’ve started wondering if the limitations of our understanding of the universe lies in the fact that our language of mathematics has limitations. Seriously, most of our observations (microcosms and macrocosms) are based on deep mathematics. At the end of that language of numbers and theorems lies something greater than our collective intelligence.

How can we describe our universe with mathematics alone? Even our calculations of the distances to stars and other celestial bodies is based on color shifting and radio waves which must be processed. I’m not saying that the nearest galaxy is only a few light days ahead, I’m just suggesting that our limit of understanding isn’t necessarily caused by stupidity. It’s merely a limitation of our understanding of the universe as it relates to the language of mathematics.

What if there was another language we could use? I’m not referring to religion, I’m suggesting that there might yet be an undiscovered language we can use to apply to the unknown universal truths. Something that doesn’t even require an “intelligent design versus evolution” war. Maybe I’m just referring to the “all inclusive theory of everything”. :)

What if this language could teach us that light isn’t the fastest known thing in the universe? What if it could reveal to us that time and light are connected in such a way that time would adjust to an increase in the speed of light so as to keep the balance there? Oh well, I’m spouting BS now.

Just something I’ve been pondering lately.

Note: Featured image taken from http://www.wallshq.com/nature/microcosm-wp-1920×1200-by-trystianity