42

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?

gnat
  • 21,442
  • 29
  • 112
  • 288
Dokkat
  • 557
  • 4
  • 6
  • 8
    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
  • Is there some specific problem you're trying to solve? – Patrick Hughes Jan 31 '12 at 18:58
  • 6
    This may be of interest: http://thedailywtf.com/Articles/What_Is_Truth_0x3f_.aspx – Chris Cudmore Jan 31 '12 at 19:45
  • 1
    Mind you, computers using base-4 or base-16 are pretty much equivalent as computers with base-2. I mean, 1 base-4 digit is pretty much the same as 2 bits. – luiscubal Jan 31 '12 at 21:39
  • 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 http://en.wikipedia.org/wiki/Bekenstein_bound for the CompSci implications. –  Feb 01 '12 at 03:13
  • What type of data are you trying to represent and store? What are you trying to measure? You have many different data types available to you in any language that can be used for any combination of purposes. The limitation in terms of application is really just your imagination. Is there a way this question can be reworded to make it clearer what the OP is really asking here? The heading and description seem a little at odds, and I'm wondering how to reword to salvage the question. – S.Robins Feb 03 '12 at 10:21

12 Answers12

59

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).

tdammers
  • 52,406
  • 14
  • 106
  • 154
  • 1
    Great answer. I'm specifially interested in what you described as continuous-domain storage, I'll certainly take a look on that. It is not smallest but is not it more suitable to represent floating points, as they are currently 'emulated'? – Dokkat Jan 31 '12 at 15:52
  • 17
    @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
  • 2
    Would it be useful if a computer used either digital and analog, one to store data (ints, strings) and other to store floats and such? – Dokkat Jan 31 '12 at 16:06
  • 20
    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
  • 9
    @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
  • 5
    `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](http://en.wikipedia.org/wiki/Binary-coded_decimal). 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
  • ENIAC was still a binary computer internally, the programmers just used BCD for certain user input data, which is a lazy way of mapping decimal digits to nibbles and vice versa, leaving 6 of the 16 values the nibble can hold wasted. Most people don't use BCD these days because of that waste. – psusi Jan 31 '12 at 19:22
  • @Michael - I'm not an information theory expert, but I would think that definition of a bit (i.e. having an implicit probability) is only applies in domains where an implicit probability is understood to be present. – 9b5b Jan 31 '12 at 19:47
  • 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
  • 1
    @Jon Schoning: The probability can also be derived from context. In the weather example, the result for 1 year can be trivially encoded via a bitmap (0=no rain on that day, 1=rain) of 356 bits. Almost all of those will be 0 for Sahara, and because of that you can convey the same amount of information in far fewer bits of data by listing the days on which it rained. Which is of course a form of compression, and the concept can be mechanically applied (as entropy encoding) quite independently of the domain. And thusly, information theory gave us ZIP compression. – Michael Borgwardt Jan 31 '12 at 21:30
  • 3
    And, if single-precision is difficult, it is *technically impossible* to build an analog circuit with noise equivalent to a `double` (at 53 bits of effective resolution, it's seriously a wacky-town proposition). That said, I do like the idea of using analog where it makes sense -- and, there are hybrid analog/digital FPGA's available, so it is now technically practical to literally program in analog... – comingstorm Jan 31 '12 at 21:40
  • 2
    @psusi: According to wikipedia, "ENIAC used ten-position ring counters to store digits". That's not BCD, and certainly not binary: it's actually a decimal digital computer. – tdammers Feb 01 '12 at 16:19
  • Small notes: Malbolge is *not* turing complete, although that's due to a memory limitation, not due to being ternary. Malbolge-T (backwards compatible) and Malbolge Unshackled (not backwards compatible) are attempts at turing complete revisions. [Setun](https://en.wikipedia.org/wiki/Setun) is an example of a hardware ternary computer. – 8bittree Aug 09 '16 at 20:37
26

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.

Karl Bielefeldt
  • 146,727
  • 38
  • 279
  • 479
  • 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 '14 at 13:10
  • @NickT Norbert Wiener, the author of cybernetics and early player in it / control theory field recalled in his book that ultimately it was the lower cost of binary circuits compared to analog equivalent that caused labs, researchers and industry opt for binary – Christophe Aug 09 '16 at 21:02
19

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.

J. Maes
  • 437
  • 2
  • 6
  • 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
  • @Dokkat, even the very best laboratory scales only provide about 6 digits of precision. Commodity computing digital hardware gives us get 14-28 decimal digits. – Charles E. Grant Jan 31 '12 at 17:59
  • 11
    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
  • @nikie - agree. although qubits are more versatile than bits, but describing them as the definitive answer 'for something that won't be only 0 or 1, but actually hold many possible states (i.e. meaning 'values' in the context of the OP's question) is a bit of a stretch. – 9b5b Jan 31 '12 at 19:41
  • @nikie That’s the misunderstanding. Schrödinger at least was convinced that the cat is actually *not* in multiple states at the same time, he used this metaphor to illustrate how ridiculous Copenhagen interpretation of quantum physics was. – Konrad Rudolph Jan 31 '12 at 19:51
  • 7
    @Ryathal That's actually a good sign: "Anyone who is not shocked by quantum theory has not understood it." -- Niels Bohr – Dan Is Fiddling By Firelight Jan 31 '12 at 19:58
  • @KonradRudolph: Of course you're right. But Schrodinger's cat is well known, and it illustrates the superposition of states in a quantum computer very well, don't you think? – nikie Jan 31 '12 at 20:09
  • @nikie Yes. I might have been a bit overeager with my urge to correct you. It’s just that so many people completely misunderstand this and form a wrong understanding of (the history of) quantum mechanics. – Konrad Rudolph Jan 31 '12 at 21:13
  • 1
    For some reason I always picture qubits as pale blue or pink Tribbles. – Wayne Werner Feb 01 '12 at 00:25
  • Your understanding of qbits is way too simple: The possible quantum states of a qbit with two states are 2D vectors `(a, b)`, where both `a` and `b` are *complex* values. So we are talking 4D here. This is then reduced by requiring the norm of the vectors to be 1, giving a 3D surface within 4D space. And, at the end of the day, you have to measure your qbit, cause otherwise you won't get any answers from it. Which is when it looses all that fancy quantum state and returns to either a 1 state or a 0 state... – cmaster - reinstate monica Jul 28 '18 at 17:52
16

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.

Nathan Long
  • 3,667
  • 3
  • 24
  • 28
  • 1
    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
  • 2
    @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 01 '12 at 00:05
  • 2
    @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 01 '12 at 00:46
11

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...

gnat
  • 21,442
  • 29
  • 112
  • 288
Sign
  • 2,643
  • 19
  • 22
  • 3
    The [balanced ternary system](http://en.wikipedia.org/wiki/Balanced_ternary) is one of the most beautiful number systems. – ypercubeᵀᴹ Jan 31 '12 at 19:46
3

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.

2

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.

thorsten müller
  • 12,058
  • 4
  • 49
  • 54
2

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.

StuperUser
  • 6,133
  • 1
  • 28
  • 56
2

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.

Caleb
  • 38,959
  • 8
  • 94
  • 152
1

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.

BЈовић
  • 13,981
  • 8
  • 61
  • 81
  • 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 01 '12 at 08:58
  • @BenVoigt Maybe you were referring to [Nat (information)](http://en.wikipedia.org/wiki/Nat_%28information%29)? *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.* – user Feb 01 '12 at 12:24
  • @MichaelKjörling: That's it exactly. – Ben Voigt Feb 01 '12 at 14:46
0

There is a smaller possible unit of data. I do not know an official name for it, let's call it an un.

Bit is a smart combo-word for "Binary digIT", meaning it has two possible states. So there must be a kind of digit with only a single possible state.

Let's see what that means. It means you would have only zeros to work with.

How would you count? In any x-base system, you increase the value until you run out of digits and then add a digit to form a number. If you have only one digit, you would run out of digits immediately so:

Zero = 0 One = 00 Two = 000 et cetera

This is definately more natural: more is more! It maps perfectly to any discrete number of things. How many potatoes? 00000 That is four potatoes. Wait a minute... that is off-by-one. If you don't like that you could redefine the value of 0 to one. Then it is really natural: no zeros is none, one zero is one, two zeros is two, et cetera.

This is impractical for a solid state machine though. Digits would have to be physically placed and removed and it doesn't scale well.

Martin Maat
  • 18,218
  • 3
  • 30
  • 57
  • 1
    This doesn't really qualify as being a unit of data, though, since you have basically just encoded 0 as "not present" and 1 as 0. They are still bits. – DeadMG Aug 09 '16 at 20:46
  • It is not binary, it is unary. The point is that the data element has only one state, not two. Presence or absence is not a state, the state of the element is always the same hence it is a unary digit. I am basically describing the tally mark system. – Martin Maat Aug 09 '16 at 21:52
-1

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.

StefG
  • 113
  • 1