There is an old joke that was used in the television series “Home Improvement”. It deals with a guy, lets call him Tim, who is looking at a new tool with a version number of 600.
His wife asks, “Don’t you have one of these already?”
Tim says, “No, I have a version 500.”
She asks, “What’s the difference?”
Tim says, “The 600 is 100 better than the 500.”
The reason this joke comes to mind is that I just read an article at New Scientist entitled Ditching binary will make quantum computers more powerful. Mathew Neeley, a Physics Graduate student at UCSB, has been quoted as stating that a given computation can be done with less “quidits” (a five state quantum storage unit) than “qubits” (a binary quantum storage unit). The article, written by Paul Marks, then goes on to state that more powerful computers can be created if we move away from the binary representation in computing to a higher base number system (he said things in a more layman’s way, but that is what he meant). What articles like this fail to mention is that although memory (RAM, Solid State Hard Drives, etc.) would benefit from one memory unit having more than one state, the actual computations (adding, subtracting, multiplying, and dividing) would suffer significant slowdown by moving to a higher based number system.
Most of the tasks a CPU does are comprised of five basic functions: move memory values from one point to another; add values; multiply values; subtract values; and divide values. The binary number system gives us a significant advantage in adding, multiplying, subtracting, and dividing because we can do several shortcuts that we can not do in higher based number systems. The best example I can think of is subtracting one piece of data from another.
While subtracting you need to keep track of possible borrows from positions higher than the current position, this can get recursive up to the high order position. Contrast that to adding where you only need to keep track of a single carry to the next position. When implementing the operation in hardware simpler designs make for faster operations, so most computer arithmetic logic units implement subtracting by adding.
Subtracting By Adding
Mathematicians have taught us the great idea of the Method of complements to subtract by adding. In brief, you take the number you are subtracting and calculate the diminished radix compliment. Add one to diminished radix compliment to get the radix complement. Add the radix compliment to the number you are subtracting from and ignore the carry.
Example base-10:
873
- 219
=====
Calculate the 9′s complement of 218. Which is basically the number do you need to add to 219 to get 999. This number is 780. Add one to this number to get the 10′s compliment. This number is 781. Add the 10′s compliment to 873 and ignore the carry.
873
+ 781
=====
1654
Ignore the carried 1 and you get 654, the correct answer for subtracting.
But wait, I actually had to subtract 218 from 999 in order to get 780, so your method is adding unnecessary overhead to the original subtraction problem.
Here is the beauty of using binary. In order to calculate the diminished radix compliment (1′s compliment) all you have to to is flip the bits. If it is 1 make it a 0, if it is 0 make it a 1. This is a simple logic NOT operation. Then we add 1 to it, then add ignoring the carry.
Here is a binary example:
01100100 (equals decimal 100)
- 00010110 (equals decimal 22)
==========
Calculate the 1′s compliment = 11101001. Add 1 = 11101010.
01100100
+ 11101010
==========
101001110
Ignore the carried 1 and you get 01001110 (equals 78 decimal)
Conclusion
Unless mathematicians can come up with simpler algorithms to do the basic building blocks of computing in a number system greater than binary that can match the speed of binary computing, then binary computing is not going away.
However, the quidit storage unit may have applicability to extremely large memory systems where the largest delay is the transferring of the data to the processor. Jonathan Home at NIST is quoted in the article as saying quidits will help pave the way for large scale quantum computing because it solves the “information transport” problem.
Still this would necessitate a conversion to binary in order for the processor to use those nifty mathematical tricks in order to keep up with the memory retrieval.
I applaud Jonathan Home of NIST for keeping a perspective on quantum computers.
Posted in Math, programming, Software
Tags: computers, LinkedIn, Math, memory, programming, quantum computing