Mar 30

## Fast binary conversion – Part II

[Fast binary conversion – part I]

In this post we continue talking about fast binary conversion, this time focusing on signed numbers, in particular two’s complement (2C) numbers .  We introduced binary in a previous post (Sinistar), and two’s complement was only briefly tackled:

” In 2C’s representation, the most significant bit (the one most to the left) is the sign bit. Positive numbers would have this bit to zero and negative numbers to one. The value of the number can be obtained like this: $valor = -b_{N-1}\cdot 2^{N-1} + {\sum_{i=0}^{N-2} b_i\cdot 2^i} = -b_{N-1}2^{N-1}+b_{N-2}2^{N-2}+\ldots +b_{1}2^{1}+b_{0}2^{0}$.

So, number 3 would be represented with 8 bits as 00000011 and number -3 as 11111101. Do the maths to check that it fits. An interesting property of 2C numbers is that we can add them no matter their sign: the results will be positive of negative directly, and it will be correct (given that the result can be represented with the available bits). … you can easily check that if we add 3 and -3 in 2C the result is zero (00000011+11111101 = 100000000, dicarding the ninth bit). Thus, substracting one unit to a number is the same as adding -1, than in 2C binary turns out to be the number 11111111 … “

So let’s see if we can find ways to read 2C binary numbers quickcly.

### Positive numbers

Positive number are those with a zero in the most significant bit (MSB) zero. So the negative most significant weight is multiplied by zero leading to a positive number. For instance, the 2C binary number 011 is 3, since $011_2=(-2^2)\times 0 + 2^1\times 1 + 2^0\times 1 = 3_{10}$. Therefore if the MSB is zero, numbers are positive and we can apply the rules from part I.

So from now on we will stick to negative numbers.

### All ones

An N-bit numbers with N ones are always equal to $-1_{10}$. The reasoning is straightforward:

$111 \cdots 111_{2}=1000 \cdots 000_2+011 \cdots 111_2=(-2^{N-1})+(2^{N-1}-1)=-1_{10}$

Here we have applied the consecutive ones rules to the second term of the addition. So:

$1_2=-1_{10}$

$11_2=-1_{10}$

$111_2=-1_{10}$

$1111111111_2=-1_{10}$

Etc.

### More ones than zeros (for negative numbers) and 2C numbers in general

A number with more ones than zeros can be seen as a number with all ones with some ones substracted. For instance:

$111101_2=111111_2-000010_2=-1_{10}-2_{10}=-3_{10}$ $1111010111_2=1111111111_2-0000101000_2 = -1_{10}-40_{10} = -41_{10}$

From the example, it is simple to infer that a way to read a negative 2C number is to invert the number (flip zeros and ones), add one, and then apply a negative sign. So a negative number $B$ can be converted to decimal performing the operation $-(\bar{B}+1)=-\bar{B}-1$. For instance, number $111101_2=-000010_2-1 = -2-1=-3$. So now, it is up to you to see a negative 2C number as a -1 lacking some ones in the positions where there are zeros, or as the result of $-1$ multiplied by value of the inverted binary number. minus one.

### More zeros than ones (for negative numbers)

If there are more zeros than one you might as well simply add the weigths of the correspoding ones:

$10000001_2= -2^7+1=-126$ $1000101_2= -2^6+4+1=-61$ $1000000000_2= -2^9=-512$

### Zeros to the right

As with unsigned numbers (and positive 2C numbers), the effect of having zeros to the right is equivalent to a multiplication of a power of two. For negative number we have:

$10100_2=101_2\cdot 2^2=-3\cdot4=-12$

$1111111111000_2=1111111111_2\cdot 2^3=-1\cdot 8=-8_{10}$

$11110101110000_2=1111010111_2\cdot 2^4 = -41_{10}\cdot 16 = -656_{10}$

$100010100_2=1000101_2\cdot2^2= (-2^6+4+1)\cdot 4=-61\cdot 4 = 244_{10}$

Etc.

### Putting all together

Let’s try to find the best way to perform fast conversion to several 2C  numbers.

$010100000101=1024+256+5=1285$

$10100000101=-6\cdot128+5=-768+5=-763$

$011110000=15\cdot16=240$

$11110000=-1\cdot16=-16$

$011110111000=(255-8)\cdot8=247\cdot8=1976$

$11110111000=-9\cdot8=-72$

Etc.

With this post and in part I I think that we have learnt a few useful tricks that can be handy if a calculator is not available.  It remains open if we will be proficient at communicating with moisture vaporators. Please let me know.

Feb 24

## Fast binary conversion – Part I

Binary is the basis of digital systems and it is important to be fluent when it comes to obtain the decimal value of a binary number. In this post we will start dealing with fast binary to decimal conversion for numbers up to 16 bits. This will be handy if you work in the domain of embedded systems and digital design.

In a previous post, we introduced the basics of binary number systems. I will reuse some paragraphs here:

” The binary system is a base-2 positional numeral system. A base-B positional numeral system represents numbers with digits that can have values from 0 to $B-1$ (from 0 to 1 for binary; from 0 to 9 for decimal, etc.), and they are written one after the other. A digit is in a position i which in turn determines its weight. Assuming that the digit located to the right of the number has position 0 and that the digit located to the left of the number has position $N-1$ (because there are N digits), the weight of each digit is $B^i$. Given that an N-digit number with values $b_i$ ($b_i\in [0\ldots B-1]$ and $i\in [0\ldots N-1]$), its value can be computed as:
$value = \sum_{i=0}^{N-1} b_i\cdot 2^i = b_{N-1}2^{N-1}+b_{N-2}2^{N-2}+\ldots +b_{1}2^{1}+b_{0}2^{0}$.
For instance, the binary number $10011_2$ has a decimal value of $1\cdot2^4+0\cdot2^3+0\cdot2^2+1\cdot2^1+1\cdot2^0=16+2+1=19_{10}$. “

Learning by heart a few powers of two is useful in many ways. Firstly, it is necessary to do any mental conversion from binary to decimal. So do your homework and learn the powers of two from $2^0$ to $2^{16}$; that is: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768 and 65536. Once you know these powers of two, it is easy to find out the minimum number of bits that we need to represent an integer number. For instance, if we know the upper closest power of two of a number $x$, this will lead us to the number of bits required to represent that number. Let’s say that we want to convert to binary number 240. The upper closest power of two is 256, which is $2^8$, which tells us that 8 bits are required. Note, that if the number is exactly a power of two (i.e. x=256) then the number of bits has to be increased by 1. And knowing this powers of two will be also essential in performing fast binary to decimal conversions.

### Consecutive ones

Let’s talk now about something quite trivial. If we add 1 to number 999, we obtain 1000. So $999=1000-1$, that is $999=10^3-1$, so, the exponent of the power of ten matches the number of consecutive nines. We can generalized this so that a number in base $B$ composed of a sequence of $N$ consecutive digits is equal to $(B^N-1)_B$, and particularizing for binary ($B=2$) a sequence of $N$ consecutive ones is equal to $(2^N-1)_{10}$. So now, assuming that we master the powers of two, we can easily calculate the decimal value of numbers such as:

• $11111_2=2^5-1=32-1=31$
• $1111111111_2=2^{10}-1=1024-1=1023$
• Etc.

### Zeros on the right

Adding a zero to the right of a number is equivalent to multiplying the number by the base. For instance, $560_{10}=56\times10$$110_2=11_2\times 2$, etc. Thus, adding $N$ zeros to the right of a binary number is equivalent to multiplying the number by $2^N$ . This could be useful sometimes:

$10100_2=101_2\cdot 2^2=5\cdot4=20$ (also, $16+4=20$)

$1111111111000_2=1111111111_2\cdot 2^3=(2^{10}-1)\cdot 8=1023\cdot8=8184$

Etc.

### More ones than zeros

If a binary number has just a few zeros you might as well consider the number as a sequence of consecutive ones that has a few ones missing. Thus, number $111111110111_2$ can be seen as $111111111111_2-1000_2=(2^{12}-1)-2^3=4095_{10}-8_{10}=4087_{10}$. Let’s see some examples:

$10111101_2=(2^8-1)-2^7-2^1=255-66=189$

$111111111100_2=(2^{12}-1)-3=4092$ (or, $1023\cdot4=4092$)

### Putting all together

Let’s try to find the best way to perform fast conversion to several numbers. I am assuming here that you master powers of two and that you easily recognize short binary numbers.

$10100000101=1024+256+5=1285$

$10100000101=5\cdot 2^8 + 5=5\cdot 257 = 1285$

$11110000=15\cdot16=240$

$11110111000=(255-8)\cdot8=247\cdot8=1976$

$11110111000=2047-64-7=2040-71=1976$

$1000000000001=4096+1=4097$

$1000000001110=4096+(7\cdot2)=4096+14=4110$

$111101000=8\cdot(63-2)=8\cdot61=488$

Etc.

Well, it is not rocket science, but surely it is useful. You will find many occassions when these tricks cannot be applied and you have to add all the weigths corresponding to the ones to obtain the decimal values. Also, you can use a calculator 🙂 .

In this post we have covered unsigned numbers. The next post we’ll be about fast conversion of signed binary numbers: two’s complement numbers. Stay tune and soon you will master the binary language of moisture vaporators (Star Wars rules!) . See you soon!

Feb 01

## Torres Quevedo and the first computer

(originally published in spanish in November 2018)

I am in the middle of intensive reading up on the inventions of Leonardo Torres Quevedo, and, even though is a bit early, I would like to share my findings, especially those related with the world of computing. Additionally, I am Spanish and I talk all the time about pioneers of Electronics and Computing born or that lived in U.S.A., Japan, etc., and I think that it is not a bad idea to look for the national heroes now and then. Not pretending to underestimate anyone, I believe that there is a clear americanization of the history of computing, so instead of letting the information to find you, one has to make a special effort to look for it.

I start this research due to my interest in a line of computation that the general public assummes wrongly: computer (digital systems) commit mathematical errors when performing calculations. The main problem is that the number of digits that a computer uses to store a number is finite, thus, not all numeric values can be represented correctly, and this leads to operations’ results with errors, which are propagated if these are used in other operations. It is at this point where I connect with Torres Quevedo, since I read somewhere that he was a pioneer proposing one of the arithmetic formats most used in modern computers at the beginning of the XX century.  “But that is another story and shall be told another time”, not so long.

This time I focus on something big: Torres Quevedo, a Spanish engineer, implemented the first computer in history.

Searching the IEEE and ACM databases yielded only a few articles: [Randell82][Yuste2005][Yuste2008]… I found a few Spanish books tackling this issue, some of them discontinued and others just passing through this issue or with incomplete information about it.  Randell deals with Torres Quevedo’s invention in his book “Origins of Digital Computers” (Springer, 1982),  but I did not have the oportunity to read it. There is a book about Torres Quevedo’s legacy by Alfonso Hernando González which is available online (check below). I have used the article by Randell [Randell82] as a starting point to traverse this path, along with the works of Hernando [Hernando1991] and the articles of Yuste et al [Yuste2005, Yuste2008].

Let’s start:

Leonardo Torres Quevedo was born on the 28 of December of 1852 in Santa Cruz (Cantabria, Spain). He studied Civil Engineering (Ingeniería de Caminos, Canales y Puertos) and his profesional carreer was full of achivements. He worked on different disciplines such as Aeronautics, Automatics, Telecommunications and Mechanics.  His inventions cover from analog computing machines, along with remote radio controlled systems, to the design and fabrication of semi-rigid planes that were used in the First World War. His “Spanish Aero Car” is still fully functional in Niagara’s Falls. He also was quite productive designing computing devices and automata.

The eminent Spanish wise man Leonardo Torres Quevedo (wikipedia)

His famous Chess Player, considered the first chess automaton,  was able to carry out the king and rooke endgame, playing – and winning—against a human opponent. It is possible to check its design in the publication Le Nature de 1914 [Vigneron1914].

The Chess Player (el ajedrecista) by Leonardo Torres Quevedo (wikipedia)

He was keen on exploring the possibilities offered by electromechanic systems and to test the limits of machines. In his work Essays on Automatics (Ensayos sobre automática) [Torres1914] he elaborate on the work of Babbage, who was the first to propose the construction of machines able not only to perform mathematical operations, but also to execute a program.  The Analytical Engine was conceived to be entirely mechanical, was able to store data (as the registers in a CPU do), had arithmetic operators such as adders, multipliers and dividers (equivalent to the Arithmetic-Logic Unit (ALU) of a CPU) and its programs accounted for loops and decision making (conditional branches). Ada Lovelace stands out as the first programmer since she, inspired by Babagge work, wrote the first programs that could be run on a machine, even though neither her nor Babagge would seen the analytical engine built.  Eventually the machine was never built and Torres Quevedo used its design as a seed to carry out a functional electromechanical  implementation. In his eassy, he faced the design of machine able to perform the operation ax(y-z)2 given input values for the variables. The machine had the same blocks of Babagge’s machine, but adapted to the electromechanic technology of early 20th century: arithmetic block (i.e. ALU), temporal storing block (i.e. registers) and read-only program (i.e. ROM) that allowed conditional branches.

Automaton to compute ax(y-z)^2 (“Ensayos sobre automática” 1914)

After this intelectual effort, he built several prototypes and it is in 1920 when he presented in Paris the Arithmometer. This invention enabled writing the operation to be computed through a typewriter and the machine executed a program acording to the chosen operation. Inside, there was an only-read program that would control the arithmetic operators, the temporal memory, etc. In conclusion, a computer that was able to execute a program stored in a drum. In order to change the program it was necesary to build a new drum and insert it into the machine  [Hernando1991]. Quite close to punched card technology.

We must highlight that Torres Quevedo did not consider the use of massive storing memories (i.e. RAM), but only the storing of temporal values or final operations results – resembling the registers of a CPU. It is likely that the complexity of storing and addressing huge amounts of data was out of reach for the technology of the times.

In [Hernando1991] it is pointed out that the publication Essays on automatics (Ensayos sobre automática) is “one of the fundamental texts in the history of Informatics”. Hernando also prompts that Torres Quevedo brings out the importance of digital machines that allow controlling systems, while reacting to the environment conditions as well as to the very computed data. Clearly a visionary comment. Moreover, he proposes the creation of a specific study branch called Automatics. Had this been developed it would have been possible to research on several aspects of Electronics and Computer Science several decades before it actually happened. In addition, the inventor stresses that automata not only must focus on performing automatic mathematical calculations but they should also address any kind of problem, again foreseeing ideas that were developed several decades after by Turing, Von Neumann, etc. Hernando carried out this PhD Thesis on the work of Torres Quevedo and published on his blog a free copy of his book from 2000 about the same subject.

However, it seems that the impact of Torres Quevedo’s theories and inventions related to computing has been negligible, not affecting the course of Informatics due to the lack of difussion [Hernando1991]. Had his theories been spread, the history of Computing would have followed a different path, and the computer would have been created long before. The achivements of Leonardo Torres Quevedo are previous to those of Turing (who was born in 1912) and several decades previous to the computers of the 40s that set the foundations of modern Computing.

With this post, I simply tried to disseminate the relationship between Torres Quevedo and the history of Informatics, without being specific about the inner details of his inventions. I hope I have time to be able to analyze the designs of this awsome scientific and inventor so I can post about it in the future.

The Babbage Engine, Computer History Museum (accessed on 30/11/2018)

Biografía de Leonardo Torres Quevedo, ITEFI-CSIC (accessed on 30/11/2018)

Proceedings of the Symposium “Simposio Leonardo Torres Quevedo: su vida, su tiempo, su obra”, 1987, 1991 y 1995 (accessed on 30/11/2018)

Alfonso Hernando González’s blog (accessed on 30/11/2018)

References

[Randell1982] “From Analytical Engine to Electronic Digital Computer: The Contributions of Ledgate, Torres, and Bush”, Brian Randell, Annals of the History of Computing, IEEE, 1982

[Vigneron1914] «Les automates», H. vigneron Le Nature, 1914 (The Chessplayer)

[Torres1914] “Ensayos sobre Automática. Su definición. Extensión teórica”, L. Torres Quevedo, Revista de la Real Academia de las Ciencias, 1914 [PDF]

[Hernando1991] “Torres Quevedo como precursor de la informática moderna”, A. Hernando González, Proceedings of the Symposium “Simposio Leonardo Torres Quevedo: su vida, su tiempo, su obra”, 1991 [PDF]

[Yuste2005] “Scanning Our Past from Madrid: Leonardo Torres Quevedo”, A.P. Yuste, M.S. Palma, Proceedings IEEE, 2005

[Yuste2008] “Early Developments of Wireless Remote Control: The Telekino of Torres-Quevedo”, A.P. Yuste, Proceedings

Nov 06

## Sinistar: the arcade of the eternal youth

There is nothing like finding an arguably fun example to support any of the arid concepts populating the fields of digital electronics, computing and signal processing. Some time ago, I came across a fantastic video published by the IEEE Spectrum Magazine (Five Infamous Arcade-Game Glitches), devoted to programming mistakes (i.e. glitches) in arcade videogames: Asteroids (Atari), Donkey Kong (Nintendo), Sinistar (Williams Electronics), Ms. Pacman (Midway) and Centipede (Atari) .

Sinistar’s glitch got my attention, and it seemed handy to explain two’s complement arithmetic, which is essential in the digital systems domain. In this game, it was possible to go from having 1 life to enjoy 255 lives. And all due to a programming absent-mindedness and to the behavior of binary arithmetic. By the way, let me clarify that what goes next is quite simple, but fun.

First I will briefly explain some concepts about binary. If you think that this is too basic you can go straight to the heart of the issue clicking here.

Oct 08

## Total recall: “6502: igniting the digital revolution” (2017)

The 6502 was pure magic out of transistors. The creators of this microchip are truly digital heroes that achieved the unthinkable: creating a low-cost microprocessor in 1975 that shaped the electronic industry. This device was used in legendary machines, such as Atari VCS 2600, Apple II, Commodore 64, Nintendo Famicon, etc. An animated GIF is worth one thousand words:

(sometimes this GIF does not animate, try this)

In 2017 I gave two talks on this topic. First, in April 2017, I had the opportunity to pay homage to this wonderful tiny microprocessor by means of a presentation at the retrocomputing event RetroMadrid. Later, I extended a little bit the talk and gave it again as part of a research divulgation event organized by the government of Madrid (Semana de la Ciencia 2017, November 2017).  I deeply enjoyed the process of connecting the numerous dots that outline a fascinating and unique story. Also, I received lots of feedback from the audience that I very much appreciate. By the way, the end of the second talk is alternative… in many senses.

The contents of the talk cover:

• Brief (and quite informal) review on digital circuits and integrated circuits
• Chuck Peddle and Motorola: let’s compete with Intel!
• Chuck Peddle and MOS Technology: Let’s build a low-cost microprocessor!
• The 650x team
• Design of the 650x chipset
• Selling the micro
• Motorola strikes back
• 6502 and Commodore
• 6502 and… Commodores, Atari, Apple, ARM, Nintendo, etc., etc.
• The 6502 today
• Books, microchips and kits
• FPGAs
• Visual6502
• 6502 and neuroscience
• The public goes wild

I must highlight that my talks were based on books and documents that later on I realized that some of them were not completely objective, so the story had some uncertainties that must be further investigated. I wish I have the time some day to do so. Since then, I try to be very careful with the sources I used and I always try to elaborate my own version of the story, clearly stating what is fact and what is an opinion (mine of somebody else’s). [I talked a little bit about that in my talk about the invention of the microprocessor]

Summarizing, no matter if you are sentimentally attached to Zilog, Motorola, Texas Instruments, etc., the story of the 6502 must be told, because this microprocessor is a key element to understand the creation of the PC and the birth of the videogame industry.

Some highlights

• The microelectronic process was manual. They had to draw the different layers of the microchip by hand. This also happens with the Intel 4004.
• A guy called Steve Wozniak bought a few chips from the first batch of 6502 to build the Apple I. This microprocessor made possible to build affordable computers.
• Two of the three first best-seller personal computers that motivated IBM to enter the personal computer business had 6502 as brains: Apple II (6502), Commodore PET (6502) and Tandy TRS-80 (Z80).
• The creation of the 6502 and the fact that a small company (Western Design Center) could design and produce microchip served as an inspiration to Acorn engineers to develop their own microprocessors and a few years later ARM was born.

Resources

6502.org: The 6502 microprocessor resource
The Visual 6502 project: Wanna see the transistor activity while executing assembly code? This is the place
Apple][ history website: The reference place to learn about the Apple ][
Commodore: a company on the edge: Amazing book about the first steps of Commodore Bussiness Machines into computing. The inception of the 6502 chip is beautifully described.

Talks (in Spanish)

• El microprocesador 6502 y su impacto en la revolución digital (Spanish),  RetroMadrid 2017, [slides]
• Historia del microprocesador 6502: semilla del PC y de la industria de los videojuegos (Spanish), Semana de la Ciencia 2017 [slides (with alternative ending 🙂 )]

Sep 05

## (RetroMadrid2018) 4- and 8-bit pioneers: the creation of the microprocessor [the talk I couldn’t give]

(Also available in Spanish. Use the language switch)
Please find a video (in Spanish) of a talk I planned to give in RetroMadrid 2018 (a Spanish event for retrocumputing), but that eventually I got sick and I could not attend. The talk covers the following points:

• Review of my previous talk (history of 6502) in RetroMadrid 2017.
• Origin of Intel 4004.
• Highlight: The role of Japan in the creation of the first comercial microprocessor on 1 single chip.
• Highlight: Two genius Dos genios en acción: Masatoshi Shima y Federico Faggin.
• Was the Intel 4004 the first microprocessor? We will revisit the definition the definition of microprocessor and cover some microprocessor contemporary to 4004.
• Highlight: I think that there were other microprocessor prior to Intel 4004 (my personal opinion).
• Texas Instruments: a 45 years old secret.
• Relationship of Intel with: Zilog, Motorola, MOS Technology, ARM, etc.
• Yes, I like Star Wars 🙂

If you are in a hurry:

Some references: