Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Is there an alternative to bits as the smallest unit of data? Something that won't be only 0 or 1, but actually hold many possible states in between? Wouldn't it be more natural to store floats like that?

share|improve this question

We're looking for long answers that provide some explanation and context. Don't just give a one-line answer; explain why your answer is right, ideally with citations. Answers that don't include explanations may be removed.

7  
You'd need an infinity of states to be able to store arbitrary floats, so this wouldn't be practicable. –  ChrisF Jan 31 '12 at 16:11
2  
@ChrisF: Can you represent an infinity of floats with a limited amount of bits? –  user unknown Jan 31 '12 at 16:59
11  
@userunknown - no you can't. Which is why floating point arithmetic is error prone. What I was trying to say was that having more states wouldn't actually solve anything. –  ChrisF Jan 31 '12 at 17:05
6  
This may be of interest: thedailywtf.com/Articles/What_Is_Truth_0x3f_.aspx –  Chris Cudmore Jan 31 '12 at 19:45
5  
It is impossible to uniquely represent an infinite number of different floats. You would need to store an infinite amount of information to uniquely identify a single infinifloat, which can't be done in a finite amount of space because physics. Information storage in excess of a certain amount in a given volume requires a density such that the contents would be gravitationally crushed to MAX_DENSITY in finite time, even if they can travel at MAX_SPEED (better known as 'the speed of light'): a black hole. See en.wikipedia.org/wiki/Bekenstein_bound for the CompSci implications. –  fennec Feb 1 '12 at 3:13
show 3 more comments

12 Answers 12

Of course it is possible, both theoretically and practically.

Theoretically, there are two classes of alternatives: digital number systems with a base other than 2 (in fact, the decimal system as we know it is one such system); and non-digital number systems. Mathematically speaking, we're talking about discrete vs. continuous domains.

In practice, both options have been explored. Some of the early digital computers (e.g. ENIAC) employed decimal encodings rather than the now ubiquitous binary encoding; other bases, e.g. ternary, should be just as feasible (or infeasible). The esoteric programming language Malbolge is based on a theoretical ternary computer; while mostly satirical, there is no technical reason why it shouldn't work. Continuous-domain storage and processing was historically done on analog computers, where you could encode quantities as frequencies and / or amplitudes of oscillating signals, and you would then perform computations by applying all sorts of modulations to these signals. Today, quantum computing makes the theory behind continuous storage cells interesting again.

Either way, the bit as a theoretical smallest unit of information still stands, as any alternative can encode more information than a single yes/no, and nobody has yet come up with a smaller theoretical unit (and I don't expect it to happen anytime soon).

share|improve this answer
14  
@Dokkat: Continuous-domain storage, such as an analog tape, is great in theory, but in practice, it suffers from irrecoverable noise and degradation, which is one of the reasons why we're using digital computers in the first place. –  tdammers Jan 31 '12 at 15:54
16  
In information theory it's quite possible to convey less than 1 bit of information. The basic idea is that one bit of data only holds one bit of information if both states are equally likely. According to that definition, in the Sahara desert the answer "no" to the question "did it rain today?" carries less than 1 bit of information because that's almost always the answer. –  Michael Borgwardt Jan 31 '12 at 16:10
8  
@Dokkat used to be common for modelling complex analog quantities, the 'digital' computer was a control system for the analogue computer. In practice it's difficult to build an analog circuit with the resolution of a double –  Martin Beckett Jan 31 '12 at 17:03
4  
Some of the early digital computers employed decimal encodings rather than the now ubiquitous binary encoding - Actually, decimal encodings are still in use today; it's called BCD. The BIOS in most computers use it (for decimal-based dates), as well as most cheapo-calculators, because it requires less circuitry (ie. it's cheaper) to do everything in BCD than it is to do it in binary and have a binary-to-decimal converter. –  BlueRaja - Danny Pflughoeft Jan 31 '12 at 18:44
3  
As @tdammers says, it is hard to match even single-precision floats using analog signals. 32-bit floats effectively have 24 bits of precision; analog circuits with comparable noise are expensive, power-hungry, slow, and very very sensitive to their environment. –  comingstorm Jan 31 '12 at 21:23
show 7 more comments

Those are called qubits, and are used in quantum computers. You'll find more information about them on the wikipedia entry. Research is being done to make such computers that are stable and economically feasible.

share|improve this answer
1  
this makes my head hurt reading that... –  Ryathal Jan 31 '12 at 15:41
    
I'm not sure exactly how a qubit works (I'm reading it so I'll update later), but I know qubits are impractical with current technology, while that concept isn't. For instance, one could physically represent the 'floating' bit by the amount of water filling a glass, and measure it using a balance. –  Dokkat Jan 31 '12 at 15:43
10  
Nitpicking: A qubit doesn't hold states in between 0 and 1. It's still 0 or 1, but it can have multiple states simultaneously. (Just like Schrodinger's cat which isn't "half dead", but dead and alive simultaneously) –  nikie Jan 31 '12 at 18:04
7  
@Ryathal That's actually a good sign: "Anyone who is not shocked by quantum theory has not understood it." -- Niels Bohr –  Dan Neely Jan 31 '12 at 19:58
1  
For some reason I always picture qubits as pale blue or pink Tribbles. –  Wayne Werner Feb 1 '12 at 0:25
show 5 more comments

You're basically describing an analog signal, which are used in sensors, but rarely for internal computations. The problem is noise degrades the quality, you need very precise calibration of a reference point that is difficult to communicate, and transmission is a problem because it loses strength the farther it travels.

If you're interested in exploring analog computing, most undergrad "intro to electronics" classes have you build things like op-amp integrators. They're easy enough to build even without formal instruction.

You can also store multiple digital states on the same node. For example, instead of 0-2.5 volts being a zero and 2.5-5.0 volts being a one, you can add a third state in between. It adds a lot of complexity, though, and significantly increases your susceptibility to noise.

share|improve this answer
    
A analog computing used to be quite common, but ultimately digital can be more precise. Using a few more bits in memory to represent a value is downright trivial compared to trying to hammer noise down several dB lower (3 bits ~ 20 dB), and at some point (varies based on speed) physically impossible. –  Nick T Jan 31 '12 at 23:01
    
I like the emphasis here on analog computing and the examples. Coming from a strictly digital comp sci background I did not always see what analog computing was. Though googling for that will give many examples. I think I recall seeing that a prism "computes" the fourier transform, because it splits incoming light into its constituent frequencies. It does this quite fast, with 0 energy (in the sense of requirements to compute the FT). Of course to do something with the result would likely require digitization. –  Paul Apr 21 at 13:10
add comment

A matter of accuracy

One reason we use bits is that it helps us store and retrieve information accurately.

The real world is analog, therefore all the information computers pass or store is ultimately analog. For example, a current of a specific voltage on a wire, or magnetic charge of a specific strength on a disk, or a pit of a specific depth on a laser disc.

The question is: how accurately can you measure that analog information? Imagine that a current on a wire could be interpreted as any decimal number, as follows:

  • 1 to 10 volts: 0
  • 10 to 20 volts: 1
  • 20 to 30 volts: 2

Etc. This system would let us pass a lot of data in a few pulses of current, right? But there's a problem: we have to be very sure what the voltage is. If temperature or magnets or cosmic rays or whatever cause some fluctuation, we may read the wrong number. And the more finely we intend to measure, the greater that risk is. Imagine if a 1-millivolt difference was significant!

Instead, we typically use a digital interpretation. Everything over some threshold is true, and everything under is false. So we can ask questions like "Is there any current at all?" instead of "Exactly how much current is there?"

Each individual bit can be measured with confidence, because we only have to be "in the right ballpark". And by using lots of bits, we can still get a lot of information.

share|improve this answer
    
To be fair, digital circuits have to define measurable values that are definitely true or false, and in-between states that are "undefined". In 3.3/5V logic it might be < 0.8V is false, > 2.5V is true. Noise is certainly still an issue if it takes the signal out of those ranges. For instance, trying to pull down a signal to low using an NPN transistor will only get you down to 0.55 to 0.7V depending on certain factors. Not a lot to play with. You just make it harder when you define more defined ranges. –  Scott Whitlock Jan 31 '12 at 17:50
1  
@ScottWhitlock those are just specifications; unless the pin is designed to accept HiZ or the like, it will be interpreting the input as a 1 or 0, and that point can vary based on temperature, manufacturing batch, supply voltage, etc. That undefined region isn't a feature (you seem to suggest you could exploit it for fuzzy logic). –  Nick T Jan 31 '12 at 23:06
1  
@NickT: the undefined region marks that there is a major distortion (one that is so major that normal error correction might not recover it) and a possible retransmit is necessary. –  Lie Ryan Feb 1 '12 at 0:05
1  
@LieRyan, you're considering a much higher level than what such specs deal with (physical layer). The undefined region just means the behavior (how the bit is read) is undefined and not guaranteed. It could still work just fine. –  Nick T Feb 1 '12 at 0:46
add comment

There are also ternary computers instead of binary ones. http://en.wikipedia.org/wiki/Ternary_computer

A ternary computer (also called trinary computer) is a computer that uses ternary logic (three possible values) instead of the more common binary logic (two possible values) in its calculations...

share|improve this answer
2  
The balanced ternary system is one of the most beautiful number systems. –  ypercube Jan 31 '12 at 19:46
add comment

It might well be more natural to us but there are specific reasons why binary was chosen for digital circuitry and thereby for programming languages. If you have two states you only need to distinguish between two volt settings say 0V and 5V. For each additional increase to the radix (base) you'd need to further divide that range thus getting values that are indistinct from one another. You could increase the voltage range but that has this nasty habit of melting circuitry.

If you want to change the hardware type from digital circuitry your options are more varied. Decimals used to be used in mechanical computers since gears have much more heat tolerance and are much more distinct than electron charges. Quantum computers as stated elsewhere have other ways of dealing with things. Optical computers might also be able to do things we've not dealt with before and magnetic computers are a possibility as well.

share|improve this answer
add comment

I think you could nowadays built items that could hold any amount of states or even work with analog data. Though building a whole system and getting all the logical components running to get a full featured and programmable architecture would be a lot of work and a financial risk for any company to undertake this task.

I think ENIAC was the last architecture to use ten-position ring counters to store digits. Though I could be wrong about this and I'm not sure, how much this influenced the other parts of the machine.

share|improve this answer
add comment

Storage can be thought as transmission to the future, all of the transmission problems with continuous(analogue) media will apply.

Storing those states could be trivial (a three way switch or some sort of grid) and physically storing these states is one issue that many answers cover, much better than I could.

My primary concern is how this stored state is encoded and it seem that there's a high posibility that this task is a fools errand, since bits are sufficient for representation of practical continuous data, depending the accuracy you need, keep adding more bits.

Truly continuous data is impossible to store in this way, but equations to calculate them e.g.

1/3

can be stored.

share|improve this answer
add comment

A clue and an inkling are smaller pieces of information than a bit. Several clues are usually required to establish the definite value of a bit. Inklings are worse: no matter how many you add up, you still can't know the value of the resulting bit for certain.

More seriously, there are multi-valued logics where the fundamental unit can have one of n states, where n > 2. You could consider these units to carry less information than a bit in the sense of the preceding paragraph, but from an information theory point of view you'd have to say they carry more. For example, you'd need two bits to represent the same amount of information that a single value in a four-valued logic could carry.

share|improve this answer
add comment

The optimal numerical base is e, but since the simplest way to represent a number in digital electronic is with two states (high voltage=1, low voltage=0), the binary number representation was chosen.

share|improve this answer
    
Talking about e without also mentioning the nat? For shame. –  Ben Voigt Jan 31 '12 at 23:31
1  
@BenVoigt huh? What is nat? :) google told me some weird things, which do not fit well into the subject. –  BЈовић Feb 1 '12 at 8:58
    
@BenVoigt Maybe you were referring to Nat (information)? A nat ... is a logarithmic unit of information or entropy, based on natural logarithms and powers of e, rather than the powers of 2 and base 2 logarithms which define the bit. –  Michael Kjörling Feb 1 '12 at 12:24
    
@MichaelKjörling: That's it exactly. –  Ben Voigt Feb 1 '12 at 14:46
add comment

I can't a find a definitive English reference, but as far as I remember from Information Theory Class the bit is fundamental unit of information. A bit of information is the information you receive after tossing a fair coin (50% probability for each side). Everything else can be reduced to this.

Even if you use a device that has multiple states, it can always be reduced to bits.

share|improve this answer
add comment

If you define natural by being close to how mother nature works, the most natural way of information encoding are DNA-like combinations of adenine, cytosine, guanine, and thymine.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.