# Matthew Smith

web developer and designer

matt@matthewsmith.io

# Roman Numerals with Sawtooth and Step Functions

by on September 28, 2017

Let’s take a look at how to generate Roman numerals from Arabic Numerals using a bit of math.

Ultimately, we want to write a function that takes any positive integer less than 4000 and returns the corresponding Roman numeral.

However, because I want to focus on the approach, we’ll only be looking at single-digit positive integers. Operating on single-digit positive integers is where the most interesting part of the algorithm lies. But the algorithm can easily be extended to include multi-digit positive integers. If you are interested in my final algorithm which works with positive integers up to 3999, take a look at my CodePen.

Integers over 3999 cannot be written in Roman numerals without using vinculum notation.

In this article, I use the term Roman symbol to refer to any one of these symbols: `I, V, X, L, C, D, M`. I use the term Roman numeral to refer to a collection of one or more Roman symbols.

## The Guts / Overview

At the heart of this algorithm are two functions, a sawtooth wave function and a step function. Each of these two functions takes an integer (the single-digit digit positive integer to be converted to a Roman numeral) and returns an integer. These two return integers give us important information about which Roman symbols to use, which order to write them in, and how many times to repeat a Roman symbol.

## Breaking it Down

a. Every single-digit positive integer is written in Roman numerals as the concatenation of no more than two unique Roman symbols.

This is important. Some single-digit positive integers use more than two Roman symbols. For example, 8 is written as `VIII`. But the important bit here is that 7 uses only two unique Roman symbols.

b. Every single-digit integer Z has two integer components A and B, such that A + B = Z.

A and B are not unique, there are many values of A and B that could satisfy our assertion. Our goal is to find the specific values of A and B that add up to Z and also provide us with some useful information for converting to Roman numerals.

For our purposes, Roman numerals always use additive notation. What I mean by that is illustrated by this example: To find the value of `VI`, we add the values of `V` and `I`.

What about `IV`? Shouldn’t we subtract the value of `I` from the value of `V` because they are in reverse order? No. For our purposes, when a smaller symbol comes before a larger symbol, it indicates that that the sign of the smaller symbol is flipped, making it negative. Then we add the symbols like usual.

We’re going to extract A and B from each single-digit positive integer and use them to find the corresponding Roman numeral. In order for A and B to be useful, they must help us answer these three questions:

1. Which Roman symbol we should use?
2. How many times we should repeat that Roman symbol?
3. In which order should we write the Roman symbols? (e.g. 4 is written as `IV` but 6 is written as `VI`)

### A Table of Two Components

After a late night spent scribbling on bits of paper, I came up with this table:

Z 1 2 3 4 5 6 7 8 9
A 1 2 3 -1 0 1 2 3 -1
B 0 0 0 5 5 5 5 5 10
Roman Numeral I II III IV V VI VII VIII IX

And it answers all of my questions!

1. Which Roman symbol we should use? If the value in Row A is not 0, use at least one `I`. If it’s 0, do not use an `I`. If the value in Row B is 5, use a `V`. If it’s 10, use an `X`. If it’s 0, do not use anything.

2. How many times we should repeat that Roman symbol? The absolute value of row A tells us directly how many times we should repeat `I`. The Roman symbols indicated by row B are never repeated.

3. In which order should we write the Roman symbols? If the value in row A is -1, write the Roman symbol indicated by A first, then write the Roman symbol indicated by B. Otherwise, reverse the order.

See how the table tells us everything we need to know to generate Roman numerals from the any single digit integer? Cool, huh?

### Seeing the Patterns

Now let’s lengthen the table so we can see the patterns better. But remember, we only care about single-digit positive integers right now.

Z -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
A -1 0 1 2 3 -1 0 1 2 3 -1 0 1 2 3 -1 0 1 2 3 -1 0
B 0 0 0 0 0 5 5 5 5 5 10 10 10 10 10 15 15 15 15 15 20 20

Looking at the patterns of values of A and B, we can see that A is generated by a sawtooth wave function and B is generated by a step function. These functions can obviously be written in JavaScript or whatever language you prefer.

## Let’s Look at Some Code!

Now that we have the ideas down, let’s write the code that generates our Roman numerals.

Here’s a basic overview of algorithm:

1. Use a sawtooth wave function and a step function to generate integer components A and B from the input integer.
2. Create a two-element array containing components A and B in the necessary order.
3. Map the two-element components array to a new array of Roman symbols based on the values of A and B.
4. Concatenate each element of the new array and return the Roman numeral string.

Let’s look at the code for each step:

1. Use a sawtooth wave function and a step function to generate integer components:

``````function componentA(z) {
// Sawtooth wave
return z - 5 * Math.floor((z + 1) / 5);
}

function componentB(z) {
// Step function
return 5 * Math.floor((z - 4) / 5) + 5;
}
``````

2. Create a two-element array containing components A and B in the necessary order:

``````function getComponents(z) {
const a = componentA(z);
const b = componentB(z);

if (a < 0) return [Math.abs(a), b];
else return [b, a];
}

// examples:
getComponents(3);  // [0, 3]
getComponents(4);  // [1, 5]
getComponents(5);  // [5, 0]
getComponents(6);  // [5, 1]
``````

3. Map the two-element components array to a new array of Roman symbols based on the values of A and B:

``````function componentsToRoman(componentsArray) {

return componentsArray.map(function(c) {
if (c === 0) return '';
else if (c === 5) return 'V';
else if (c === 10) return 'X';
else return 'I'.repeat(c); // repeat() requires polyfill for IE
});
}

// example:
componentsToRoman([1, 5]);  // ['I', 'V']
``````

4. Concatenate each element of the new array and return the Roman numeral string:

``````componentsToRoman(componentsArray).join('');

// example:
componentsToRoman([1, 5]).join('');  // 'IV'
``````

We can pass in `getComponents()` as the argument of `componentsToRoman()` to get a Roman numeral in one fell swoop:

``````function toRomanNumeral(int) {
return componentsToRoman(getComponents(int)).join('');
}

// example:
toRomanNumeral(4); // 'IV'
``````

### Wrapping Up / The Challenge

The code we have so far only works with single-digit positive integers. Can you extend this algorithm to work with positive integers up to 3999? Hint: Split the multi-digit number and operate on each digit individually. Keep track of the position of each digit, applying higher Roman numerals for higher-positioned digits. Finally, concatenate the result of each single-digit operation. If you get stuck, take a look at my solution.