The Naked Scientists

The Naked Scientists Forum

Author Topic: How efficient is binary?  (Read 11737 times)

Jason Fong

  • Guest
How efficient is binary?
« on: 10/09/2009 08:30:02 »
Jason Fong asked the Naked Scientists:
   
Hi Chris,

As we all know the standard qwerty keyboard layout is rather inefficient, error prone and slow. After all in school we learn that it was designed to slow down "typewritists".

After stumbling into the dvorak keyboard layout whilst trying to increase my characters per minute typed, I suddenly began to question the efficiency of codes such as binary.

Is binary inherently the most efficient way of representing any set data using two states? Or is it just efficient in conveying a set number of characters?

Or should I be asking about the efficiency code which is written in binary?

Also would the complexity of computer code increase linearly or exponentially as we hopefully in the future mature into quantum computing?

Perhaps binary is only efficient for linear calculations, I read that quantum computing will allow multi threaded algorithms, such as the ones used to calculate large primes, to run much faster/efficiently.

What do you think?


 

lyner

  • Guest
How efficient is binary?
« Reply #1 on: 10/09/2009 17:15:46 »
It all depends upon why you mean by "efficient".
Do you mean the length of code needed to represent a certain amount of information?
Do you mean how quickly a computer can perform a given basic operation?
Do you mean how quickly can you write a program to do something.
If the last is what you mean then all I can say is
10 Print "Hello World"
(Younger readers may need to talk to their grandmothers for an explanation of that)
which proves that binary is not too efficient for at least one purpose.
 

Offline syhprum

  • Neilep Level Member
  • ******
  • Posts: 3816
  • Thanked: 19 times
    • View Profile
How efficient is binary?
« Reply #2 on: 11/09/2009 04:25:06 »
Unfortunatly my grandmother (born 1885) is not available to consult, please explain.
Is it a statment in 'Basic' ?
« Last Edit: 11/09/2009 04:28:01 by syhprum »
 

Offline LeeE

  • Neilep Level Member
  • ******
  • Posts: 3382
    • View Profile
    • Spatial
How efficient is binary?
« Reply #3 on: 11/09/2009 15:39:01 »
Yes, it depends upon what you mean by 'efficient'.

In any numbering system there's a trade-off between the number of symbols that you use and how many of those symbols are needed to express a value.  With the decimal system we have ten symbols, so we can represent ten different values with just a single symbol whereas with binary we have only two symbols, so we can only represent two values with a single symbol i.e. 0 & 1.

As I pointed out in another recent thread (after initially getting it wrong - Oops  ;)) you can count up to 1023 using your fingers and thumbs if you do it in binary, rather than just 10 if you use decimal.
 

Offline graham.d

  • Neilep Level Member
  • ******
  • Posts: 2208
    • View Profile
How efficient is binary?
« Reply #4 on: 11/09/2009 16:17:39 »
I have seen efficiency described by the number of positions of a matrix. For example, to describe 1 million - 1 (=10^6 - 1) in the decimal system there would be a 6 x 10 matrix. That is 6 positions (units, tens, hundreds etc) by 10 states (0,1,2,3,4,5,6,7,8,9). Binary is a smaller matrix. To avoid fractions a slightly larger number 2^20 - 1 (=1,048,576) is represented by a 20 x 2 matrix. But a number base of 3 is the most efficient with 13 x 3 matrix giving 3^13 - 1 (= 1,594,323).

I believe this can be proved with more mathematical rigor than this example, and, as is the nature with mathematical abstractions, it is actually possible to show the most efficient number base is "e" (2.718281828..). Though it is hard to see what this means as a number base. I remember learning about this some time ago. It's a shame that ternary logic never caught on :-)
 

Offline syhprum

  • Neilep Level Member
  • ******
  • Posts: 3816
  • Thanked: 19 times
    • View Profile
How efficient is binary?
« Reply #5 on: 11/09/2009 16:47:17 »
I think ENIAC was the only large computer to use base 10, this was done to reduce the number of vacuum tubes needed to store data all later computers seem to have used base 2 as better ways of storing data were devised.
Vacuum tube circuits were devised to work in base 3 but as far as I know know no large computer ever used them.
« Last Edit: 11/09/2009 16:50:09 by syhprum »
 

lyner

  • Guest
How efficient is binary?
« Reply #6 on: 11/09/2009 17:44:04 »
Morse code is an example of a fairly efficient code for English text. Unlike ASCII, with fixed length symbols, it uses short symbols for common letters and longer symbols for uncommon letters. It is an example of what is called Redundancy Codes. Fiddly to code and decode but very efficient in the use of bits.

LeeE
I'm desperately trying to find some fallacy in your thing about fingers and counting. There's something suspiscious about it but I can't think what. I.e. it may be true but not relevant to the notion of efficiency,
 

Offline Geezer

  • Neilep Level Member
  • ******
  • Posts: 8328
  • "Vive la résistance!"
    • View Profile
How efficient is binary?
« Reply #7 on: 11/09/2009 19:38:51 »
LeeE must be quite correct, certainly in terms of fingers (assuming each finger only has two possible states of course) because there can be no more than 1024 unique patterns of ten fingers. All possible combinations are used, from 0000000000 to 1111111111

Other counting methods (using fingers or anything else where only two states are allowed) fail to make use of all possible combinations.

For this reason, as long as a "bit" can only have two states, binary representation will always be the most efficient in terms of bits. And bits don't come for free in hardware terms, so you would like to use as few as possible.

BTW, here's a link to a recent thread on the same subject.

http://www.thenakedscientists.com/forum/index.php?topic=24968.0
 

lyner

  • Guest
How efficient is binary?
« Reply #8 on: 11/09/2009 21:43:49 »
When using fingers to count, I'm not sure it's the binary state of fingers that counts as much as the position of the raised finger. Or is that just another way of looking at it?
 

Offline Geezer

  • Neilep Level Member
  • ******
  • Posts: 8328
  • "Vive la résistance!"
    • View Profile
How efficient is binary?
« Reply #9 on: 11/09/2009 22:15:36 »
Traditionally we only raise one finger at a time to count (although Churchill did make it popular to raise two - something to do with Agincourt I think). However, that's a very inefficient method of counting in terms of fingers. By assigning the values 1, 2, 4, 8, 16 etc. to particular fingers we can encode any number between 0000000000 and 1111111111 if you like to count in binary or 0 and 1023 if you prefer decimal notation.

As someone once pointed out, this is all rather basic "book work" to those who know anything about digital systems.

 

lyner

  • Guest
How efficient is binary?
« Reply #10 on: 12/09/2009 10:30:16 »
I think you have to look at the two hands as, effectively, ten different symbols in a decimal system.
In which case, you would need about three such symbols to transmit 10E3 different states which is roughly the same number of states that can be sent with ten binary digits. (This is a fairly common computer thing - as in kB often meaning 1024Bytes.)

I must say, I hadn't imagined, in my remotest dreams that "raised finger" could be taken in that way but, on re-reading, I see that it could have been.

« Last Edit: 12/09/2009 10:32:08 by sophiecentaur »
 

Offline DoctorBeaver

  • Naked Science Forum GOD!
  • *******
  • Posts: 12656
  • Thanked: 3 times
  • A stitch in time would have confused Einstein.
    • View Profile
How efficient is binary?
« Reply #11 on: 12/09/2009 22:36:05 »
I like the ancient Babylonian method of counting on one's fingers. Forgetting the thumb, there are 3 segments to each finger. That means you can count to twelve on 1 hand. When you reach 12 you mark 1 on your other hand. Starting with the tip of the left index finger you check all 3 segments on that finger, then move to the middle finger & so on.

Thumbs were used to touch the relevant finger segments so touching the 2nd segment of the middle finger, left hand and 3rd segment index finger of the right hand you are indicating 3*12+5=41. The max number you can count to is 144 (assuming you have 4 fingers on each hand).

12 is a more efficient base than 10 as 12 is divisible by 2, 3, 4 & 6. 10 is only divisible by 2 & 5. Common fractions are readliy calculable in base 12 too. You have use decimal places for any fractions other than 1/2 or 1/5. Base 12 allows 1/4, 3/4, 2/3 etc. I sometimes wish the Babylonian system had come to the fore rather than the base 10 system we now use.
 

Offline Geezer

  • Neilep Level Member
  • ******
  • Posts: 8328
  • "Vive la résistance!"
    • View Profile
How efficient is binary?
« Reply #12 on: 13/09/2009 05:41:00 »
I like the ancient Babylonian method of counting on one's fingers. Forgetting the thumb, there are 3 segments to each finger. That means you can count to twelve on 1 hand. When you reach 12 you mark 1 on your other hand. Starting with the tip of the left index finger you check all 3 segments on that finger, then move to the middle finger & so on.

Thumbs were used to touch the relevant finger segments so touching the 2nd segment of the middle finger, left hand and 3rd segment index finger of the right hand you are indicating 3*12+5=41. The max number you can count to is 144 (assuming you have 4 fingers on each hand).

12 is a more efficient base than 10 as 12 is divisible by 2, 3, 4 & 6. 10 is only divisible by 2 & 5. Common fractions are readliy calculable in base 12 too. You have use decimal places for any fractions other than 1/2 or 1/5. Base 12 allows 1/4, 3/4, 2/3 etc. I sometimes wish the Babylonian system had come to the fore rather than the base 10 system we now use.

Ah ha! I think that might explain why Ancient Babylonians, Inc. had to announce yet another delay in shipments of their radical new base 12 architecture microprocessor. However, I just heard from their product manager and he is extremely confident they will actually release a Beta version of the chip during Q1, FY2010, only 3217 years behind schedule.
« Last Edit: 13/09/2009 06:29:13 by Geezer »
 

Offline Geezer

  • Neilep Level Member
  • ******
  • Posts: 8328
  • "Vive la résistance!"
    • View Profile
How efficient is binary?
« Reply #13 on: 13/09/2009 07:16:17 »
I think you have to look at the two hands as, effectively, ten different symbols in a decimal system.
In which case, you would need about three such symbols to transmit 10E3 different states which is roughly the same number of states that can be sent with ten binary digits. (This is a fairly common computer thing - as in kB often meaning 1024Bytes.)

I must say, I hadn't imagined, in my remotest dreams that "raised finger" could be taken in that way but, on re-reading, I see that it could have been.

Sophiecentaur - Let's assume, for a moment, that you are sufficiently naive to have missed the implications of your "raised finger" observation, but what on earth are you babbling on about regarding binary systems? Are you suggesting that all the scientists and engineers in the computer industry are a bunch of twits who don't know what they are talking about?

Are you proposing a better system? If you have one, I'm confident you will receive a Nobel Prize if you reveal it, and I will happily support you if that is the case.

Sadly, I think you are just waffling because you can't stand the idea that others might know more about a subject than you ever will, but I'll be delighted if you can persuade me that my perceptions are misguided.
 

Offline Geezer

  • Neilep Level Member
  • ******
  • Posts: 8328
  • "Vive la résistance!"
    • View Profile
How efficient is binary?
« Reply #14 on: 13/09/2009 09:14:17 »
SC - Recently, I happened upon a post from an undergrad who was obviously struggling with his course work and came to this site to seek help. Perhaps he was not applying himself sufficiently, but perhaps he was a brilliant technologist who could not relate to the teaching method at his school. I have no idea which it was.

However, your lack of knowledge of his situation did not deter you from pointing out that, if he wanted to get a degree, he better get into a library and figure it out for himself. I think you made some insightful comment along the lines of "That's why they call it a degree."

I'm having a little difficulty finding the particular post, but I'm sure you will remember it and be able to point us to the link.

Many thanks.

Geez
 

Offline Make it Lady

  • Neilep Level Member
  • ******
  • Posts: 4050
  • Hands-on fun for everyone!
    • View Profile
How efficient is binary?
« Reply #15 on: 13/09/2009 15:42:23 »
Is no one going to answer Jason's question in a sane ans sensible manor. I think he has probably gone running off to the medicine cupboard for some aspirin after reading this load of tripe. Jason, I wish I could help you. Perhaps I'll ask my 15 year old son as he might have a more mature reply.
 

Offline Geezer

  • Neilep Level Member
  • ******
  • Posts: 8328
  • "Vive la résistance!"
    • View Profile
How efficient is binary?
« Reply #16 on: 13/09/2009 20:44:15 »
But Miss, he started it!
No I didn't. You did!
Didn't!
Did!
Swot - Ouch!
Waaa! He hit me Miss.

OK Miss, fair point. We are not being very considerate to our guest.

Jason is asking several questions. Perhaps we should try to identify them:

1. Are there more efficient human interfaces for data and text entry?
2. Are there more efficient means of representing values (in a computer) than binary numbers?
3. Would it be more efficient to represent computer code using something other than binary representation?
4. Will the amount of code required with quantum computing be much greater than the amount of code required with today's linear programming technique?
5. Will quantum computing allow us to calculate some things much more quickly?

(I hope the above captures the essence of Jason's question.)

Here's an attempt to answer them.

1. As Jason already pointed out, there are more efficient keyboard layouts than QWERTY. It's possible to do a lot of things to speed up user input. For example, it's possible to use stenographer type keyboards which are more like playing chords on a piano. Unfortunately, QUERTY is so firmly entrenched that's is unlikely to be replaced any time soon.

2. I'm not sure if I got the question right exactly, but assuming I did, and assuming Jason is referring to computers that employ binary (i.e. two state) logic, then binary representation, storage and manipulation of numeric data is the most efficient method, certainly in terms of computer hardware utilization because there are no unused states. It might seem like a pain to do everything in binary, but that's a human perspective because we (typically) count using bits that have ten states rather than two. Although it is possible to build computers that count using other bases, because the computer's logic is still all binary, it only adds complexity without improving performance. I don't think Jason was proposing anything other than two state hardware. If he was, then the answer would be very different.

3. The code that the computer executes is a mixture of op-codes and data. The op-codes are really just patterns that the processor recognises and acts upon. The associated data can be almost anything in the context of the op-codes. Again, because the logic is two state, the objective is to use all the available bits as efficiently as possible. If for example, we only permitted binary-coded-decimal (BCD)representation "inside" the computer, we would not be making full use of all the available bits, so, for a given set of requirements, the BCD machine would have wider words and more memory than its plain binary counterpart.

4. I'm rather clueless about that one. I suspect the code does not expand because multiple instances of the code are executing simultaneously, but that's only a guess.

5. I hope so, otherwise we should not waste our time developing such a thing  :D
 

Offline graham.d

  • Neilep Level Member
  • ******
  • Posts: 2208
    • View Profile
How efficient is binary?
« Reply #17 on: 14/09/2009 12:44:44 »
Make it Lady, I did give a sensible, and I believe mathematically correct, answer but it was obviously considered too boring to bother with.
 

Offline Geezer

  • Neilep Level Member
  • ******
  • Posts: 8328
  • "Vive la résistance!"
    • View Profile
How efficient is binary?
« Reply #18 on: 14/09/2009 19:22:38 »
Make it Lady, I did give a sensible, and I believe mathematically correct, answer but it was obviously considered too boring to bother with.
Certainly not boring, but possibly too erudite for a Geezer!
Would your scheme require three state logic, or could it be implemented with two state logic?
« Last Edit: 15/09/2009 07:26:06 by Geezer »
 

Offline LeeE

  • Neilep Level Member
  • ******
  • Posts: 3382
    • View Profile
    • Spatial
How efficient is binary?
« Reply #19 on: 14/09/2009 19:36:54 »
You'd need three-state logic for trinary, four-state logic to work in base four etc.
 

Offline Geezer

  • Neilep Level Member
  • ******
  • Posts: 8328
  • "Vive la résistance!"
    • View Profile
How efficient is binary?
« Reply #20 on: 14/09/2009 20:03:34 »
You'd need three-state logic for trinary, four-state logic to work in base four etc.

Agreed - unless you used two bits for three states, which would be very inefficient. I suppose two bits for four states would be OK, but I'm not sure why it would be any better than binary.

Jason's question was;
"Is binary inherently the most efficient way of representing any set data using two states?"

I think by "binary" he is referring to the binary representation of numbers (presumably including positive and negative values) and "two states" refers to two state (i.e., binary!) logic. So, if we are limited to two states (per bit) then yes, I would say that binary representation is as good as it gets.
 

Offline graham.d

  • Neilep Level Member
  • ******
  • Posts: 2208
    • View Profile
How efficient is binary?
« Reply #21 on: 15/09/2009 15:20:50 »
Actually three states is more efficient as a number system, but two states is easier to implement in logic because logic is based on something being true or false - a natural two state system.
 

Offline Geezer

  • Neilep Level Member
  • ******
  • Posts: 8328
  • "Vive la résistance!"
    • View Profile
How efficient is binary?
« Reply #22 on: 15/09/2009 16:40:01 »
Actually three states is more efficient as a number system, but two states is easier to implement in logic because logic is based on something being true or false - a natural two state system.

I'll take your word for that :)

Wonder what a trinary J-K flip-flop would look like?
 

Offline LeeE

  • Neilep Level Member
  • ******
  • Posts: 3382
    • View Profile
    • Spatial
How efficient is binary?
« Reply #23 on: 15/09/2009 18:13:12 »
Umm... "a trinary J-K flip-flop..."

Do you want to think that one through again?  ;D

You can't really use several bits i.e. two bits to work in trinary because it's not just a question of how you store the data but also how you operate on that data.  Even though you could use two bits to represent trinary or base four, the underlying operations will still be binary because the logic is still two-state.  In trinary you need to not only work with tits, rather than bits, but also with three-state logic, hence my comment re a trinary flip-flop.  For example, if we use -1, 0 & +1 for our trinary states, what would be the opposite of each state?
 

Offline Geezer

  • Neilep Level Member
  • ******
  • Posts: 8328
  • "Vive la résistance!"
    • View Profile
How efficient is binary?
« Reply #24 on: 15/09/2009 19:28:01 »
Umm... "a trinary J-K flip-flop..."

Do you want to think that one through again?  ;D

You can't really use several bits i.e. two bits to work in trinary because it's not just a question of how you store the data but also how you operate on that data.  Even though you could use two bits to represent trinary or base four, the underlying operations will still be binary because the logic is still two-state.  In trinary you need to not only work with tits, rather than bits, but also with three-state logic, hence my comment re a trinary flip-flop.  For example, if we use -1, 0 & +1 for our trinary states, what would be the opposite of each state?
I was in the shower why I realized the folly of my question! It wouldn't be a flip-flop. It would have to be a trip-flop  :D
It ought to be possible to define a set of logic elements that would allow the construction of a trinary computer, but my brain is so "hard-wired" for binary, that I'm having a hard time imagining what they would possibly be. For example, what would be the equivalent of a simple binary inverter? It makes no sense to me in trinary terms. As you point out, there is no such thing as "opposite" (I think!)_
« Last Edit: 15/09/2009 19:31:57 by Geezer »
 

The Naked Scientists Forum

How efficient is binary?
« Reply #24 on: 15/09/2009 19:28:01 »

 

SMF 2.0.10 | SMF © 2015, Simple Machines
SMFAds for Free Forums