CAS Community   >   Resources   >  

Life-of-brian-banner1-min
What have the Romans ever done for us?

Teaching the whole CS spec. through one problem - converting decimal to Roman numerals

Richard Pawson

Created by Richard Pawson
last edited Feb 06 2021 by Richard Pawson



This resource is part whimsical, and part serious. The background is that I have long used the example of converting decimal to Roman numerals to illustrate various aspects of programming: the problem is just simple enough to program in lesson-time, and just complex enough to be interesting. Over the years I have built a library of different implementations, illustrating different principles.

Eventually, this became something of an obsession – to try to see how many different aspects of the syllabus I could illustrate, usefully, using this one idea. OK, my sub-title is an exaggeration: it’s not the whole syllabus. But if you read on you might be surprised at the breadth of approaches that can be applied to this single problem. (Also, I don’t really mean that this is a good way to teach those topics; but I think it can be a very good way to reinforce them.)

The serious point of the undertaking is this: typically each new technique in CS is introduced using only a problem that is hand-picked to show the advantage of that technique. IMO this can sometimes lead to a weak understanding of the power of the technique. By deliberately tackling the same problem using many different approaches, I think one can gain more – or at least different – insights.

What follows are 10 illustrations of key ideas in Computer Science (the first few are relevant to GCSE, the later ones to A-level) applied to the problem of converting decimal to Roman numerals. Each of these illustrations can be used in a variety of different ways:

  • (For the simpler ones) As whole-class exercises
  • As a teacher-led demonstration
  • (For the more advanced ones) As ‘stretch’ exercises for the most able pupils
  • As revision reading

Example answers for each of the 10 examples are attached as downloadable files. For the first five, I have included C#, VB and Python versions.

1: Procedural programming: using a series of ‘while loops’

This can be used as soon as ‘while loops’ have been covered. The challenge is to write a function that takes in a decimal integer, in the range 0 – 2099 (think of it as a ‘year’) and returns the Roman numeral equivalent as a string (zero should be returned as an empty string). The most able pupils might be able to take it from there; I suggest that most would benefit from having an algorithm sketched out for them:

  • Start with the highest value ‘symbol’ ( ‘M’ = 1000). Subtract the value of that symbol from the number, and each time you can do this append the symbol to the string result. Then do the same for the next highest value symbol, and so on down until you have reduced the remainder to zero.
  • This will work as described for the so-called ‘additive’ representation (where 4 = ‘IIII’) but we require the more normal ‘subtractive’ representation (where 4 = ‘IV’). At first sight this can be a daunting challenge: the key is to recognise that ‘IV’ can be treated as a single symbol (and ‘IX’ = 9, ‘XL’ = 40 and so on).

Armed with this idea, write the function using a series of consecutive while loops, each one handling a single symbol. (You should end up with 13 of them).

The resulting code is not particularly elegant, but it is straightforward to write and to understand. This also gives you a very good segue to talking about what’s not good about this approach i.e. it violates the ‘DRY’ principle – Don’t Repeat Yourself.

2: Procedural programming: using a subroutine to reduce repetition

The answer to the previous example used 13 successive while loops, all structurally identical but using different values. It would be nice to extract this common logic into one re-usable subroutine.

We can do this by creating a subroutine, where we pass in the symbol and its corresponding value, along with the current decimal value to be converted and the string result being built-up.

The problem is that the subroutine is going to alter two things: the remaining decimal value will (potentially) be reduced, and the result string potentially appended to.

In C# and VB one way to handle this is passing parameters ‘by reference’. Personally, I hate this pattern. Python, and in C# 7 onwards (we’re now on C# 9), offers a more elegant solution: passing the two results back as a tuple, and then assigning the two elements of the tuple back to the corresponding variables (a pattern known as ‘tuple deconstruction’). VB, from version 15 onwards, has supported ‘value tuples’ but does not support deconstruction – so you’d have to do the deconstruction in separate lines of code, which defeats the object of the exercise. So, for C# I have provided two solutions, one(for C# 7 onwards) using tuples, the other (for earlier versions) using passing by reference. For VB, only the ‘passing by reference’ option is provided. For discussion afterwards: How many lines of code have you ended up saving? What other advantage(s) does this design offer over the previous ones?

3: Data structures – using arrays

Pupils will need to understand how to use arrays for this exercise.

This exercise teaches an important point that is not widely understood: procedural instructions and data structures are, to some extent, interchangeable. You can often reduce the number of instructions by using a more powerful data structure, or vice versa.

So, starting from the model answer to the previous example, how could we make effective use of one or more arrays to improve the implementation? (Hint: you can hold all the symbols in a string array, and all the values corresponding to those symbols in another array – with the same number of elements.)

Once the exercise has been completed (or the example answer worked through), discuss: - What are the potential advantages and/or disadvantages of the solution using arrays compared to the previous one?

4: Data structures – using a dictionary

Once dictionaries have been introduced, a simple exercise is to take the model answer from the previous example and convert it from using two arrays to using a single dictionary.

I admit that I would be hard pressed to find a significant advantage of using the dictionary over two arrays – but it is useful practice, and I would argue that the code is slightly more readable, because each symbol is shown next to its value (so there’s less risk of entering them wrongly, perhaps). And you could lead on to a revision discussion, or a test, on the general characteristics of a dictionary. For example: why would you not want to try to do Roman numerals with a single array, where the value was the index into the array? (Because there are huge gaps between the values, so most of the array would be empty, which is very wasteful of memory. Dictionaries, inter alia, allow numeric keys with large gaps, with high efficiency in both memory and performance.)

5: Recursion (in a procedural language)

This example can be used to reinforce the point that although some problems seem naturally to suggest a recursive algorithm, any algorithm involving a loop can be translated into a recursive form.

The challenge here is to re-implement the decimal to Roman numerals function using a recursive approach. Some pupils will see the idea straight away; others might need a strong hint on the algorithm, which can be done with an example:

The Roman numeral representation of ‘2021’ is ‘M’ (the symbol with the largest value that can be deducted from the decimal value) followed immediately by the Roman numeral representation of ‘1021’ (the remaining decimal after the value of that symbol has been deducted).

Once pupils have completed the exercise, or the teacher has worked through a model answer in class, invite the pupils to discuss the advantages/disadvantages that they see in the recursive approach.

Note: My solutions for this example use two arrays, as in Example 3, rather than a dictionary (Example 4). This is in case recursion is taught before dictionaries. They could all easily be converted to use the dictionary approach.

6: Functional Programming

It should be no surprise that the recursive approach used in the previous example is the key to how to tackle the problem using a pure Functional Programming language such as Haskell. But the example can also illustrate other features of such languages including: functional lists, guards, and list decomposition (x: xs).

This is probably too advanced an exercise for any but your most able pupils, but as an example to work through on the board, the model answer included here might be useful.

7: Assembly Language

The Roman numerals conversion problem is actually quite an interesting one to attempt in Assembly Language. It is not especially difficult – and different pupils can be given different levels of hints. It is possible to tackle this in two stages:

  • First, sticking strictly to the AQA Instruction Set, which supports only ‘Immediate’ and ‘Direct’ addressing modes (which is nearly a crime, IMO!). The hint here is just to translate the algorithm used in the model answer from Example 1 into assembly language.

  • Secondly, allowing indexed (or indirect – they’re closely related) addressing. Here you can use an approach very similar to the model answer used in Example 3. Indeed, it is worth bringing out the point that indexed addressing is how arrays are implemented at low level, and is the reason why they are O(1) performant.

My model solution takes the second approach. It will run on Peter Higginson’s ARMlite simulator. (See this resource if ARMlite is new to you).

8. Logic gates & Boolean algebra

How would you build a combinatorial logic circuit (on a logic simulator), using nothing more than AND, OR and NOT gates, to convert a number from decimal to Roman numerals?

Such an exercise can be used not only to reinforce understanding of logic circuits, but also of Boolean algebra. A very important lesson – IMO, one of the most important in Computer Science, but not explicitly part of the curriculum – is the importance of choosing the right representation. We’ve been doing that, implicitly, in some of the earlier exercises, and it will come up again in the final one that follows this. Any choice of representation makes some things easier, and others harder.

For the combinatorial logic challenge, my suggestion is:

  • Represent the input as binary-coded decimal – BCD – not binary. So, a total of 16 input lines, 4 per decimal digit, to cover the range 0-2099
  • Start with a single decimal digit (encoded as 4 bits of binary)
  • For this lowest decimal digit (0-9), represent the output as a set of lines, each one labelled as a symbol in this order: ‘I’, ‘X’, ’V’, ‘I’, ‘I’, ‘I’. Your logic simulator should let you attach a simulated LED/Bulb to each of these lines. Then you read the result as the symbols (in that order) of the illuminated lines only.
  • Perhaps using a spreadsheet, create a table of test data for the input values 0-9 represented as four lines in BCD, and showing the correct illuminations of output lines for each case. Then write a Boolean expression that derives each output line from the 4 input lines, separately.
  • Then extract common terms from the various expressions – there are many. You may also be able to use the rules of Boolean algebra to reduce some of the expressions.
  • Now add the second decimal digit, encoded as BCD, so you will have 8 input lines, coping with the range 0-99. The key insight is to realise that the second digit has identical logic to the first digit – you can just copy and paste the circuit – but with the 6 output lines now labelled: ‘X’, ‘C’, ’L’, ‘X’, ‘X’, ‘X’. The two digits are translated independently – there is no need for any interconnection between digits.
  • You now have all the information you need to make the circuit work with 4 decimal digits – up to 2099.

9. Automata

For initial discussion: would it be possible to use a Finite State Machine (FSM) to convert decimal to Roman numerals? The problem is that FSMs do not generate output – other than an end state. You could, in theory, design an FSM that parsed an input number in the range 0-2099 and ended up in one of 2100 different ‘accept’ states, each labelled with the corresponding Roman numeral equivalent, plus an ‘Invalid Input’ state. But it wouldn’t be considered a proper use of FSMs, or be very interesting to create.

Mealy machines are class of automata that can generate output. This is worth attempting, but the resulting machines are large. I suggest you set the challenge of translating just a single decimal digit.

Build your machine starting from the lowest value up. The reason is that when the machine is presented with the input value ‘7’ say, it can output ‘V’ and then move to the state (previously built) to handle the input value for ‘2’.

Handling multiple input digits involves more work, but more able pupils might welcome the challenge. Final discussion: the hypothetical FSM involved no generalisation at all: to handle conversion of decimal in the range 0-2099 you need 2100 final states (plus intermediate states). The Mealy machine involves some generalisation, but a full implementation would still be massive. There are other classes of automata, not covered in the (AQA spec), some of which would permit greater generalisation i.e. result in smaller, more elegant designs. This leads naturally to the discussion of Turing machines.

10. Turing Machine

This one almost did my head in! I do not recommend attempting it as an exercise, unless you are a really sad case, like me! The design took me many hours, and my first successful attempt involved literally thousands of transition functions. My final version has ‘just’ 317 transition functions. As the saying goes in software development: ‘Simplicity is the ultimate sophistication’.

Rather than study the transition rules directly (though you can if you want), I recommend you download the document containing the whole set, and copy and paste it into this online simulator. Then load an example date (e.g. 1489) onto the tape, and run it, adjusting the execution speed up and down as needed. The important thing is to get a feel for how the machine is tackling the problem – it should be reasonably clear.

I have to say that, personally, I found this exercise challenging – resulting in the most complex Turing Machine I have yet built – but also very instructive.

The key learning for me – yet again – was about representation, in this case the idea (deeply ingrained from having studied Engineering, incidentally) of transforming the input representation into an intermediate representation. I then realised I could do the translation in three main steps:

  1. Translate the decimal representation into what we might call ‘Roman-coded Decimal’ (RCD), so ‘1489’ becomes I-IV-VIII-IX where the dash symbol is just to demarcate between the digits (the implementation uses a vertical bar, but that messes up formatting here)
  2. Transform the symbols within each group, according to the position of the group (i.e. the power of 10). So I-IV-VIII-IX becomes M-CD-LXXX-IX
  3. Remove the separating bars and close-up the digits. So, M-CD-LXXX-IX becomes MCDLXXXIX

Conclusion

There’s a lot of files here and some are quite old. I’ve tested quite a few of them afresh today, but I’ve run out of time now. If you have problems running any of them, just ping me and I’ll fix them.

Finally, in homage to (another type of) Python, I’ll leave you with the question:

Apart from while-loops, subroutines, arrays, dictionaries, recursion, functional programming, assembly language, combinatorial logic, automata, and Turing machines … what have the Romans ever done for us? ;-)

Downloaded 1853 times.

Download

This resource has attached files: to access these files, please tick the box below to assent to the license terms
License: The resources on CAS website are under Creative Commons Attribution-Share Alike 3.0 licence unless otherwise specified by the resource creators.

You must confirm that you have read and agree the licence's ToS before you can download the attachments of this resource.

I have read the licence agreement of this resource and agree to abide by its terms and conditions.

Feedback and Comments


Available when logged in (join via the front page, for free):
  • View 4 comments on this resource.
  • View resource history, links to related resources.
  • Leave feedback for the author(s), or help by editing the resource.
Categories:


© 2021 BCS, The Chartered Institute for IT Registered charity: No. 292786
Using the websiteDisclaimer of liabilityCookies policyPrivacy notice