TL;DR Dijkstra basically got it right.
The primary means for computing with Roman numerals were the abacus and the reckoning board. The use of small pebbles in this manner of computation is the origin of our word calculus.
Roger Cooke, "The History of Mathematics. A Brief Course 2nd. ed.", Wiley 2005, p. 144, gives a brief but useful overview how and when the switch took place to our current decimal system using Arabic numerals employing pen-and-paper methods of computation:
For computations these cumbersome numerals were supplanted centuries ago by the Hindu-Arabic place-value decimal system. Before that time, computation had been carried out using common fractions, although for geometric and astronomical computations, the sexagesimal system inherited from the Middle East was also used. It was through contact with the Muslim culture that Europeans became familiar with the decimal place-value system, and such mathematicians as Gerbert of Aurillac encouraged the use of the new numbers in connection with the abacus. In the thirteenth century Leonardo of Pisa also helped to introduce this system of calculation into Europe, and in 1478 an arithmetic was published in Treviso, Italy, explaining the use of Hindu-Arabic numerals [...] In the sixteenth century many scholars, including Robert Recorde (1510-1558) in Britain and Adam Ries (1492-1559) in Germany, advocated the use of the Hindu-Arabic system and established it as a universal standard.
Leonardo of Pisa (c. 1170 – 1240), called Fibonacci, popularized the use of Arabic numerals in his book Liber Abaci published in 1202. It already contained early variants of our modern long-hand methods for performing basic arithmetic as well as extracting square roots. However, a wide-spread switch to these new methods of doing arithmetic did not take place until roughly the first half of the 16th century.
There is a famous allegorical woodcut from a work by Gregor Reisch from 1503 that shows a competition between Pythagoras, computing in the traditional method with an abacus, and Boethius, computing with pen and paper using Arabic numerals. From their respective facial expressions it is clear that the latter won. We also note that the goddess Arithmetica in the background smiles favorably upon Boethius. This is a clear expression that the superiority of paper-and-pen computations with Arabic numerals had been recognized.
The mathematician Adam Ries published several popular textbooks in German. It is interesting to note that his first book Rechnung auff der linihen (1518) explains the use of the abacus, while his second book Rechenung auff der linihen vnd federn (1522) explains the use of both abacus and pen-and-paper computation, indicating a shift toward the latter manner of computation.
Google provides a full scan of the book "Die Coss Christoffs Rudolffs, Mit schönen Exempeln der Cosz. Durch Michael Stifel Gebessert vnd sehr gemehrt" of 1571. This is a book on algebra written originally by Christoph Rudolff (1499-1545) that was improved and expanded by Stifel. Beyond basic arithmetic it covers the extraction of square roots and cube roots. The methods demonstrated are basically identical with the long-hand methods in use today.