last day (15 days later) » 

4:05 PM
-2
Q: Why do we use 8 bits to encode 0-9 decimal digits instead of 4 bits which would be more than enough?

willy wonkaWhy do computers usually use 8 bits to encode each of 0-9 decimal digits instead of 4 bits which would be more than enough? Allow me to better explicate. What if we used a code table like this to encode numbers: 0 0000 1 0001 2 0010 3 0011 4 0100 5 0101 6 0110 7 0111 8 1000 9 ...

 
@mkrieger1, no, it doesn't really. In the sense that we could have an encoding table for numbers and a separated encoding table for string symbols
@mkrieger1 I see, but it is not the aim of my question that I edited/updated to better explicate the point.
@KenWhite: why encoding in 4 bits is more convoluted than using 8? For numbers: do you see any difference in encoding them in 4 bits from the current 8 bit encoding in standard binary. apart the leading zeroes at the begging of 8 bit encoding that in 4 bit aren't present? - The need of processors able to process 4 bits numbers instead of 8 bits is another point.
@KenWhite for the single digit sign you are right the current 8 bit encoding requires a single bit, but at the same time the data type is not able to handle very long numbers. For example the long double can handle numbers from 3.4E-4932 to 1.1E+4932 if I am not mistaken, but my "!convoluted schema" (of course with some more optimizations, I give you that) could handle numbers of any length, theoretically even numbers with billions of ciphers. in both integer part and decimal part.
 
You're proposing an arbitrary-precision decimal number representation, using packed BCD for the decimal digits. (Not exactly fixed-point or floating-point, seems like separate fractional and integer parts.) Use it if you want, but since it has unbounded width you'll need extended-precision techniques to work with it; a single CPU instruction won't be able to add or subtract them. Computers normally use binary integers and binary floats, because that's more natural and doesn't waste any bit-patterns (e.g. decimal BCD only uses 10 of the 16 bit-patterns of each nibble).
Hypothetical CPUs could be developed with support for packed-BCD integer arithmetic instructions if formats like this were used in real life, instead of more normal extended-precision formats using 32-bit or 64-bit chunks. See this answer for a summary of some extended-precision number formats that get used in practice.
Note that PowerPC CPUs have hardware support for decimal floating point, where the exponent is for base-10 not base-2. en.wikipedia.org/wiki/Decimal_floating_point
 
@PeterCordes so "my" method is not a news and it is not "my" at all: it already exists or existed in the past. Or at least something similar to that did. I didn't know about it. But it seems interesting especially if it is able to solve precision errors as those compared to our times where calculating 0.1+0.2 doesn't return 0.3 as it has to be but returns 0.30000000000000004, that is indeed a pretty ugly result for Math in general... Allow me two more questions, if I may: does the existing BCD method solves these imperfections in calculations? And can handle any number length?
 
Yes, if you care about getting round numbers in base 10, decimal formats are good for that. (In many computing use-cases, that's not important; base 2 is as good as base 10 for numbers that humans aren't going to look at directly.) Combining the ideas of using decimal and arbitrary-precision, yes, you can handle numbers of any length.
 
@PeterCordes, good, than a question arise spontaneously: why precision is not the aim when a computer is designed and built? We trust computers for precision and speed on daily basis but than we discover that for computers 0.1 + 0.2 = 0.30000000000000004: and it is frustrating especially when there is a relative easy possibility to have the right result, especially for a so easy calculation: I mean 0.3 is not the 62.800 billion pi's cipher.... Am I the only one that believes that computers deserve more precision or was I born in the wrong Earth ?
 
4:05 PM
If you want exact decimal arithmetic, especially for "desktop calculator" type use-cases, yes, arbitrary-precision decimal is a good way to go. For example, ubunlog.com/en/apcalc-calculator-from-terminal / isthe.com/chongo/tech/comp/calc/calc-whatis.html, or a symbolic algebra system like Maple or Mathematica.
For numerical computation like physics simulations, binary is just as good if not better. Numbers aren't inherently base 10, so being able to exactly represent 0.1 or not isn't a big deal. Binary floating point generally gives the most precision per space, and is most efficiently implementable (renormalizing is just shifting the binary mantissa and adding/subtracting the exponent.) You're making binary float look bad by choosing numbers that are round in decimal but not representable as binary floats. Binary FP can do 0.75 + 0.75 = 1.5 exactly, as 3/4 has a power-of-2 numerator.
For example, pi and e are irrational, and take infinite precision in any base, so can't be represented exactly as decimal or binary.
as if math was an opinion. - IDK if this is hyperbole, but you do understand that the rounding error comes from converting 0.1 and 0.2 to double in the first place, right? See h-schmidt.net/FloatConverter/IEEE754.html for float; 64-bit double is essentially the same. The actual addition of bit-patterns 0x3dcccccd and 0x3e4ccccd (0.200000002980) also rounds to the nearest representable result. That's a consequence of using fixed-width types, but the initial rounding before addition is due to using constants that aren't representable as mantissa * 2^exp binary FP.
 
@PeterCordes in the case of e and π and so for other numbers that are irrational/transcendental I understand that a certain point the decimal part has to be cut so I will sooner or later lose precision because of rounding, but I don't for 0.1 + 0.2: this is just a kinda of "design error" of the binary floating point system. An error that needs correction. It is simply not acceptable that 0.1+0.2 == 0.3 == false because 0.1 + 0.2 = 0.30000000000000004: such a result simply demonstrates that it is a wrong method the one that is used that privileges easiness over precision.
 
Like I said, if you want exact results for working with decimal fractions, indeed, don't use binary floating point. Or round the result to fewer decimal digits when printing it; that works well enough for many use-cases, so you give up some precision to get correctly-rounded decimal addition. It's not a design error, it's a tradeoff because the use-case you're focusing on isn't important in many scientific-computing use-cases. FP math is exact when possible, but inputs like 2/10 have infinite significant digits in base 2, just like 2/7 in base 2 or 10, and like pi in any base.
 
Too ugly trade off.
 
Why are you so focused on decimal fractions? Binary FP math can add 5/16 + 7/16 = 12/16 exactly. (I'm writing them as rationals to avoid confusion with notation like 0.0101_base2 and 0.0111_base2). If you only ever want to use decimal floating point or arbitrary-precision decimals, go buy a PowerPC and use it's hardware support for that. Or write software that uses an arbitrary-precision decimal number class. If you're doing so few computations that human inputs in the form of simple decimal fractions lead directly to simple outputs, the performance downside won't be a big deal.
Did you mean to write 0.1 + 0.2 == 0.3, not 0.1 == 0.2? Indeed, that happens to be false because the rounding errors in converting 0.1 and 0.2 to double, and in the +, are larger than the rounding error in converting 0.3 to double. (The nearest representable double to 0.3 is 0x1.3333333333333p-2 (0.2999999999999999888977698), but (double)0.1+(double)0.2 rounds to 0x1.3333333333334p-2.) Again, this is because you insist on using values in your source that aren't exactly representable in the type you're using (double), including 0.3. godbolt.org/z/4znYcdd9P
 
@PeterCordes "Why are you so focused on decimal fractions?" Because of: function NukeTheWorldOrNot (a,b) { if(a+b == 0.3) { giveFlowers() } else { allNukesGoBoom() } } NukeTheWorldOrNot (0.1, 0.2) It means that because FP imprecision... well you know... ;-) ... I know it is a borderline case. But you can't never know....
in Javascript I can't specify the data type for a variable
 
4:05 PM
You should basically never be comparing for exact equality in numbers that might have rounding error. That's already a bug for any fixed-size number format. randomascii.wordpress.com/2012/02/25/… goes into a lot of detail about what's actually happening, and how to think about floating point numbers.
in Javascript I can't specify the data type for a variable - Then don't use JavaScript if you don't like its primary choice for numbers. Perhaps use something that compiles to WebAssembly. Or use JavaScript BigInt; v8.dev/features/bigint says it could become the basis of an eventual BigDecimal, which might use a different internal storage format, but would give you exactly the properties you're looking for: arbitrary precision exact decimal math.
Unless every operation is always exact (which would require arbitrary precision, and rule out math functions like log, exp, sqrt, and sin), different ways of getting the same number mathematically will sometimes produce different results computationally, due to rounding errors require by limited precision. Even if you use decimal arithmetic. You simply can't expect == to be true in every case you might naively expect, and false in every case you'd naively expect. (Again, unless you use arbitrary precision, making some numbers potentially take huge amounts of storage for fractions.)
 
@PeterCordes The exact point is that comparing for exact equality cannot be tricky but it must be easy as doing a==b, no more no less: the rest is something that a programmer has to implement to correct the errors of design of what is above (>the floating point "mystery" that introduces rounding errors where rounding errors aren't present because 0.1+0.2=0.3 doesn't have any rounding need even in real life). So what I am saying is that if Floating-point math doesn't work as it has to, to return precise numbers even with short decimals, than must evolve in something that is able to
 
You keep focusing on this one example of 0.1+0.2 == 0.3 which happens to be "simple" in decimal, but isn't in binary. None of those three numbers are exactly representable in binary, e.g. printing out (double)0.3 to 25 decimal places gives you 0.2999999999999999888977698, so you were never comparing with exactly 0.3 in the first place. But 0.3 is totally arbitrary, and chosen to make decimal look good vs. binary. What about 1.0/3.0? How well does your system handle that?
(Also, try to avoid deleting and reposting your comments after the replies. edit them instead. If it's past the 5-minute window, you can try posting a new version of the comment, at which point you'll see whether there were any intervening comments or not. If not, then you can delete the original.)
 
1.0/3.0 is truncated after 16 decimal but the result is a 3 periodic, that goes forever. This means that we have the solution just in front of us: the floating point mystery must evolve to the point in which we can round things correctly and return results correctly till a n number of decimals that the programmer can set for example if I want a precision of 3 decimal digit I must have the possibility to set that limit. And by defoult the limit is 15 or even 20 decimal digit, just for instance. Today seems to be 16. Ok good enough, but a system that introduces errors where there is no error...
...cannot be good enough and must be redesigned to make such errors disapear
 
introduces errors where there is no error - That's one way of looking at it. People that understand floating point would mostly agree that it's the wrong way, or a naive and over-simplified way to put it. Of course there's rounding error if you use numbers that aren't exactly representable as binary floats. Don't do that in the first place if you expect exact results. That's not what binary floating-point is for. Use a decimal number format if you want to work with human-input numbers and do a couple simple operations. JavaScript is Turing complete, you can implement whatever you want
Yes, rounding error is a thing (including in conversion to and from decimal fractions), and yes it would be nice if it wasn't. Some number formats don't have rounding error in that specific case. Use them if that's important. Or learn to deal with binary floating point if you want to use JS's native numeric type. (I'm not saying JS's design is excellent; many people would agree it has warts.)
 
"None of those three numbers are exactly representable in binary" And why is that? What's wrong in the following possibility? 000011010001 == 0.1 000011010010 == 0.2 000011010011 == 0.3
 
4:05 PM
I meant "as binary floats". The reason being that as fractions, the denominator isn't a power of 2. Obviously you can write down the binary bit-pattern for a decimal and/or rational format that can exactly represent them.
Anyway, it's reasonable to say "it would be better if we had a way to do math on computers that's exact for the same cases as for humans using paper and pencil." I don't find it reasonable to say that binary floating point math is broken and needs to be replaced everywhere, and repeatedly complaining about the same example isn't convincing or interesting to read. If you want to have an interesting conversation about the problems of binary floating point, you need to understand it better, including its strengths (like efficient HW implementations, and good info density).
Maybe there's an argument to be made that binary FP is not a good default choice for a real-number format in programming languages aimed at beginners, but OTOH any languages that want their number crunching to run fast on current CPUs need to use binary floats because that's what HW supports. Other groups of people would complain if they try to write some simple code in some language and it runs tens or thousands of times slower than the same thing in C with double.
 
@PeterCordes: "complaining about the same example isn't convincing or interesting to read": 0.1+0.2 is just an emblematic example that well represents the problem of the topic.
 
x + y == z is essentially the same example no matter what the actual values are. Yes, decimal number formats are useful for cases like the one you're describing. They exist, use them.
 
@PeterCordes: "If you want to have an interesting conversation about the problems of binary floating point, you need to understand it better, including its strengths (like efficient HW implementations, and good info density": I can agree with that... partially at least. Nevertheless my mind has difficulties to put aside precision in returned results for efficient HW implementations and info density especially when I deal with such emblematic examples of just 1 decimal....
 
binary floating point isn't a decimal format. The number of decimal digits is not relevant to whether a number can be represented exactly. 0.1 + 0.2 is another way of writing 1/10 + 2/10 (aka 1/10 + 1/5). 10 isn't a power of 2, so as a binary float, the division result needs an infinite number of repeating digits to represent in a binary place-value system. Exactly the same problem as if you wanted to do 1/7 + 2/7 using decimal fractions. (x/2^n can always be represented as a decimal fraction with a finite number of digits because 2 is a factor of 10, but not vice versa)
 
.... but of course I put aside precision when I have to deal with transcendent numbers as pi and e and 1/3 and similar where there are very big number or infinite decimals, at least in base10, because there is not any other choice. But 0.3 is not one of them and one expects to be exact. And one expects to be truncated instead to 16 decimal positions numbers like 1/3 because that is the "logic deal" for base10
@PeterCordes: "as a binary float, the division result needs an infinite number of repeating digits to represent in a binary place-value system" well the solution is just right in front of us: 000011010001 + 000011010010 = 000011010011 that is 0.1 + 0.2 = 0.3: no infinite binary digits for binary representation nor for base10. It seems coherent after all. Now can you do the same operation in normal FP representation so we can make a direct comparison? Because I am not sure on how to do that because I don't know much about FP binary encoding.
 
4:05 PM
h-schmidt.net/FloatConverter/IEEE754.html and en.wikipedia.org/wiki/Double-precision_floating-point_format‌​. No, like I've repeatedly said, binary floating point can't exactly represent 0.1. And yes, using a decimal format of course works for simple decimal fractions. But it doesn't necessarily solve the problem of 1./7. + 2./7. == 3./7. which doesn't have a simple decimal-fraction representation.
Once you introduce a language with your decimal format, someone could come along and say "math is broken, 1./7 + 2./7 != 3./7" (Unless it is by chance, pick some other example.) That will be exactly like you coming along and complaining that 0.1 + 0.2 != 0.3 in binary floating point. Unless you use a rational number format (separate numerator and denominator), you'll have a hard time handling that exactly with a decimal format. Some software does use rational number formats as a way to maintain precision including in the 1./10 + 2./10 == 3./10 case.
 
@PeterCordes also another contradiction or flaw in FP way, is that if I do 0.1+0.2 I get = 0.30000000000000004 as already said but if I do (0.1*10 + 0.2*10) / 10 I get the right result of 0.3 . This means that into the FP universe (0.1*10 + 0.2*10) / 10 != 0.1+0.2 . This means that the distributive property doesn't work... so "math is really an opinion" into FP way? It is kinda of like the FP way redefines the basic math rules... brrr... ugly... wrong universe ;-)
 
Correct, strict FP math is not associative, nor distributive for multipliers that aren't a power of 2 and thus will be inexact. But it's impossible to get exactly 0.3 as a binary floating-point number. 0.3 is not exactly representable. The two nearest double values below and above it are 0.2999999999999999888977698 (bit pattern 0x1.3333333333333p-2) and 0.30000000000000004 (0x1.3333333333334p-2, 1 higher mantissa, aka 1ulp). The 0.2999 one is closer, so 3.0/10.0 rounds to that. (And so does string -> float conversion, which is also a hard problem in general...
Re: strtod string to double, see exploringbinary.com/…. Numbers like 0.1000000000000000009 are hard to handle when converting to binary float. That's another downside to binary float, that converting to/from decimal fractions is slow and the library functions are hard to get right. (Although at this point it's a solved problem, and IIRC some recent progress on algorithms sped things up some.)
Traditionally (e.g. in scientific computing), most code didn't spend most of its time converting numbers to/from decimal strings; just take some input and spend much more time doing numeric simulations. For code that makes heavy use of FP, that's probably still the case.
 
@PeterCordes FP seems to be an ugly and old way to go. Maybe I like more the BigInt approach... I'm hopping for an eventual upcoming BigFloat to replace current FP way as a new standard... hopping it will work as logically expected of course
@PeterCordes so a question arises: will bigints and bigfloats solve the flaws of FP way?
 
BigFloat, no, I assume that's still a binary format. BigDecimal, yes, should be what you're looking for. Of course it might not solve the 1./7. + 2./7. == 3./7. problem.
 
@PeterCordes BigDecimal? ah ok. If it works fine, is good for me.
@PeterCordes Nevertheless, it seems that the intrinsic problem of FP way is that it tries to represent numbers with a per-base10Number based binary representation. It seems better the other approach that uses a per-base10Digit based binary representation as we discussed almost at the begginning: this approach will solve all precision problems like those we are discussing here, a part of course those in which it is necessary to truncate long/infinite decimals, as the examples you mentioned....
@PeterCordes ... But this is obvious: some limits are even in base10 representation, but since there will be coherence will be easier to deal with because people are more used and familiar to. What is important is that it will be possible to use it with no workaround anymore as easy as a+b=c or a*b=c and so on, as normally we would do on paper without having to do convertToSomethingElse(n) before calculations to make possible the calculation itself. These conversions are to be done transparently by the system so without the programmers to be obligated to deal with them explicitly.
 
4:06 PM
@willywonka Binary floating point doesn't have any base10 parts. It's a binary mantissa, and a binary exponent field, basically a shift-count for the mantissa. (And the mantissa is binary so it's shifting by binary digits, multiplying by a power of 2).
It works very well as designed. It's not intended for representing decimal fractions like 0.1, it's designed for representing real numbers, without caring whether or not they're round numbers in decimal.
If you expect something else from it, or use it where it's not appropriate, that's your problem. (Or Javascript's problem, in languages that don't give an easy choice of using a library for a decimal or rational number format, if you want to trade lots of speed for lack of rounding.) Having learned how binary FP works, I see that as normal, not a problem to get solved except for these odd use-cases you keep bringing up involving conversion to/from decimal fractions.
 
@PeterCordes well maybe it is not intended for representing decimal fractions like 0.1 but it used to it too and normal programmers in fact would have to focus on programming and results not on how floating point works to find workaround to its flows.
To deal with on how floating point works or implement a different way is a problem that has to be faced and solved once and for all from those that develop systems and memory and hardware and browsers and firmware and gates and CPU or math processors and similar things.
the problem with **those odd use-cases ** are part of the problem normal programmers have to deal with on daily basis.
and usually normal programmers prefer doing a+b=c than convert(a)+convert(b)=convertBack(c)
it is objectively normal and less tedious the first way
things in programming need to be more immediate in any cases no matter how odd they are
because of such odd cases in FP sometimes normal programmers need to "invent" new ways to deal with them that are ugly to implement and on the long run not convenient
 
4:33 PM
@willywonka Enjoy your quixotic crusade, then. Maybe you can get the ball rolling on more widespread support for a more "forgiving" number format that more often (but not always) works the way humans expect from pencil&paper math. But don't expect direct hardware support for unbounded size (arbitrary precision). At best some instructions that maybe help with something software needs to do in a loop, not as efficient as a fixed-width format like IEEE decimal64 floating point can be.
 
@PeterCordes @PeterCordes about that you could be right... ;-D but it is ok. Nevertheless on the long run something maybe will change because evolution of things never stops.
research is time consuming but sooner or later some genius will find a solution and even binary encoding will be replaced. Someone is already talking about inventing computers that use analogue logic inside... so we never know... ;-)
 

last day (15 days later) »