Wasn't expecting this... C floating point arithmetic

[paulca]

We're "slow finance" and we use our own math library because we have all the time in the world

It's actually a typed constraint solver engine which uses rational, precise decimal types only and any loss of precision has to be manually accounted for i.e. conversion to and from double precision values. It generates C# code which is fast and has no assumptions in it or precision loss or human errors (assuming the input was correct)

edit: based on SICP 3.3.5: https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-22.html#%_sec_3.3.5

Getting slightly off the track here, but I ran into an "Engineer versus Accountant" issue recently.

Calculating VAT.  I was trying to explain that if I calculate VAT per item on on invoice to high precision, the total VAT charged may "look" different to the VAT amount on the total bill.

Of course most accountants don't even realise that their spreadsheets and/or sage have strategies delibrately coded to do whatever the taxation system requires.

It took quite a lot of effort to finally get the answer that VAT (in the UK) is on a literal basis.  The tax office are not concerned that you rolled out 0.1p on an invoice due to rounding, they are concerned that if you charge the customer £1.39 VAT that you put that £1.39 VAT on your tax return.

But explaining the engineering problem to accountants was harder than expected.

[bd139]

Yes accounting rules are different and accountants are dicks.

That's one reason we use the constraint engine as it allows us to provide the precision rules to it unlike the native type system. One of the common problems I saw when I was working in ecommerce for a number of years was tax invoice values. When you sum 1000 order lines ex VAT then apply VAT with a 2 decimal places pricing then you get an issue that the per-line item VAT doesn't add up to the net sum always. When that happens on 10,000 orders, HMRC will own you just because they are arseholes. Also 9999 clients won't even blink an eye and just enter the invoice, but one will kick up a stink and shitpost all over twitter about how your product can't add. This is made even worse when incremental floating point rot creeps in. Incidentally no one gives a crap about this really.

That is until someone wants to be paid commission and they want it right to that tenth of a penny because it might round up into their pocket. They'll spend a week chasing half a penny.

Incidentally I charged them a lot to fix it, which was an expensive few pennies lost

[IanB]

When you sum 1000 order lines ex VAT then apply VAT with a 2 decimal places pricing then you get an issue that the per-line item VAT doesn't add up to the net sum always.

Isn't there a special kind of rounding that can be used for each of the 1000 line item VAT entries so that the sum does add up to the total?

[paulca]

When you sum 1000 order lines ex VAT then apply VAT with a 2 decimal places pricing then you get an issue that the per-line item VAT doesn't add up to the net sum always.

Isn't there a special kind of rounding that can be used for each of the 1000 line item VAT entries so that the sum does add up to the total?

This is what I was told, in the end. 

For each line item, calculate and round the VAT to the nearest penny, using natural rounding, aka >=0.5 round up.

Then for the order VAT total, total those values up.

It does however exist a possibility where the total on the order does not equal exactly 20% of the net pre-vat total.

HM Renevue and customs could pull you on this, but if you can demonstrate why it's calculated that way and you are accounting VAT only on exactly what you charged the customer they should be fine.

If however you are charging the customer by line item * VAT Rate and then putting the order total * VAT Rate onto your tax documents they may then charge you the differential and bitch at you a lot... because they are dicks.

Of course there are different ways, the important part is that what you show the customer on the bill is what you actually charged them and it is what you actually record for tax purposes.

[T3sl4co1l]

Of course it "looks "contrived" to the academic who would say, "Well just multiple it by 100", but if a is being read in from a user, a bank account or a sensor and just happens to be returning numbers the computer doesn't like, it goes off.  Adding up all the VAT or transaction fees for instance.

...

So I still stand by, computer suck at maths, make simple errors, can't represent real world numbers very well and without trying to avoid such mistakes or identify them when they do happen your code can end up fairly badly out in it's calculations.

Guess I'll be repeating this once again:
There are no bad models, only incomplete models.

Or more specifically: there are no bad computers, only incomplete programs.

Again: you literally told the computer that you want to introduce rounding errors, by choosing floats.

If you had wanted exact values, you would've chosen integers, rationals, bignums, whatever.

Further, complaining that, by coincidence or providence, you still sometimes get the correct answer, despite having no guarantee of correct answers, is silly.

"Pray tell, Mr. Babbage, if one should enter the wrong number, will it still produce the correct answer?"

Indeed, reading such code, it seems clear that it was your intent to introduce these errors.  You cannot possibly complain about errors that you, yourself, have personally desired!  That's what it looks like from the outside.

Accounting, as an example, still cannot be free of rounding, because interest accrues decimal places very quickly.  Far faster than, say, the number of decimal positions even a large government's balance sheet might have (maybe 15 digits?).  Nevermind continuous compounding, which uses a transcendental function: essentially zero inputs will have exact (rounding-free) outputs.

Anyway, this is a manifestly solved problem: many countries are phasing out their smallest denominations (Canada for example having done so), and transactions are simply rounded (up or down) to the nearest now-smallest denomination (nickels).  Rounding, it's the law!

Tim

[paulca]

Guess I'll be repeating this once again:
There are no bad models, only incomplete models.

Or more specifically: there are no bad computers, only incomplete programs.

Again: you literally told the computer that you want to introduce rounding errors, by choosing floats.

We are arguing about semantics of the term "error" and "mistake".

If I build an abacus that has 11 beads, but if you use the 11th bead one of your beads falls off.  I tell you this, but you insist on using the 11th bead.  Is the abacus in error or the user?

I think that depends on the perspective.

This is where I  often come into conflict with other engineers.  I am a practicalist.  I want to get the job done to the highest quality per effort available.  I do not like pissing around with diminishing returns.  I do not like boiling away resources on pedantry over a 1% gain.  I do not like smart arses who insist on writing complicated code because they need tissues or gym socks to mop up after them.

So in my view the abacus is broken and one needs to be careful using it because of this.

In the pendants view however, such as a hardware engineer's view it is fine, it's an artiefact of how they designed it.  The end user couldn't give a shit how they designed it or why, they would prefer it worked as intuitively intended to get their job done.

[NorthGuy]

The end user couldn't give a shit how they designed it or why, they would prefer it worked as intuitively intended to get their job done.

This is exactly what the job of the engineer is - to isolate the end user of all the peculiarities and idiosyncrasies.

For some reason, engineers often don't do it. For example, when you enter a credit card number, many of the forms will not let you enter spaces or dashes - and this after 20+ years in the making.

However, the engineer itself must be able to deal with technical stuff, and if something is not right, the engineer will be better off figuring out the root cause instead of laying the blame around.

Infinite precision cannot be achieved by finite numbers. Floating point format is one of the methods to deal with that. If you don't understand how it works, you can read the standard, you can look at binary presentation and figure out all the peculiarities. If, after you understand the mechanism, you don't like it, come up with your own method, if you can.

[T3sl4co1l]

Sorry to disappoint, but... your preference is simply impossible?  It seems rather... impractical, self-contradictory you might say?

If you don't like what a CPU cranks out, then fine, go... uh, sheesh... go curl up in the fetal position and cry?

Idunno man, you don't have a choice.  If it's not an option to:
1. Heroically correct those, "design quirks" shall we say (because that would take too much effort),
2. Choose a CPU with fewer quirks (but which has negligible market share, so would take too much cost or effort),
3. Create your own CPU without any quirks (because that would take way too much cost and effort),
Then what can you do?

Please let me know if I'm terribly misunderstanding things here!

I've always taken the view that, writing a program is solving a puzzle; building a bridge from the bricks and beams you're given; salvaging electronics and repurposing the components for a new function; etc.  Whatever the case, the challenge is to make do with the building blocks you have, to realize the desired solution.

I've always used this view, and it's always been reinforced by experience.  It's hard to think of any situation where it is not true.  Even the people making the CPUs, have to put up with the constraints imposed by their silicon process.  (Though, probably more importantly, they must put up with many less-than-ideal constraints, like compromising an otherwise magnificent x64 processor with stupid legacy 8086 instructions and semantics!)

Practicalism (by your paragraph of definition) fits nicely within this, as you simply do what you can, with what you have available, including time and money as well as material and technical resources.  There's no complaining about inconsistent hardware -- it's just what you have to work with.  There's no need to be frustrated by anything, there is only incomplete knowledge (incomplete documentation might be represented as a chance of failing to meet the constraints, rather than a material quantity), and the tedium of implementing something, whether it be the direct route, or via workarounds.

An argument from law, also goes here: ignorance of the law is not a defense.  If the law of the CPU is that so-and-so instruction produces this-and-that result plus quirks, then it's your own fault that you didn't know about it.  Mind, that remains true, even if nothing ever says what those quirks are.  (Intel has no idea how many binary input sequences produce wrong results -- CPUs are far too complex to test exhaustively.  Most FPU operations are in error by some amount, based on a statistical evaluation.  The chance of an unlucky input producing an output that violates the specification it was supposed to implement (like IEEE-754), is small, but is not zero.*)

*I don't know, maybe FPUs are actually provably-correct these days.  In that case, use something unprovable, like race conditions, or cache coherency or something.

There are many legal standards, that are not spelled out in any single law.  Many are an ad-hoc patchwork of case history, and a few laws, with an outcome deeper than the sum of its parts.  A lawyer must know these structures, just as an EE must know, say, that ceramic capacitors don't meet ratings under bias; or... that an SE must know that PHP is a clusterfuck.

Tim

[MasterT]

My OS periodically notifies me that "CPU microcodes were updated". Seems, we don't have hard-wired CPU /FPU /ALU anymore, but software-defined. This makes me think, that security issue concern may not be just floating point math related, but wider, you can not trust someone, who write those microcodes that integer math is not bugged. And reading assembler listing would not help much, since all low level instructions  like mov-mults-summ etc. may produce something that you would not expect. 

[SiliconWizard]

@T3sl4co1l: Fully agree.

Floating point numbers and operations on them are approximations. They are NOT mathematically correct in a strict sense. So this concept of "mathematical correctness" can be set aside.

FP has its uses when dealt with carefully. But if you want exactness (without having to spend a lot of time determining how to use FP to get exact results in your particular case), use integers. As we already said, there are numerous ways of using integers.

As an example, I would never use FP numbers for financial purposes. A 64-bit integer can represent in an exact manner over 184467440 billions of a money down to the cent, which is an awful lot more than the GWP. It probably fits most uses.

[bd139]

Yep. For ref, our internal representation of financial values is stored as follows as a study case:

struct FD {
    ulong Value;
    byte Precision;
    Currency Currency;
}

This represents the absolute value in the DP position so £1850.99 would be:

Value = 185099
Precision = 2
Currency = Currency.GBP

To add those together, you have three steps:

1. Assert the currency is the same.
2. Shift the lowest precision value up in precision to the highest level by multiplying it by 10^(precisionmax - precision min). Checking for overflows of course.
3. Add the numbers together

So much complexity for simple operations when you need precision.

[Nerull]

My OS periodically notifies me that "CPU microcodes were updated". Seems, we don't have hard-wired CPU /FPU /ALU anymore, but software-defined. This makes me think, that security issue concern may not be just floating point math related, but wider, you can not trust someone, who write those microcodes that integer math is not bugged. And reading assembler listing would not help much, since all low level instructions  like mov-mults-summ etc. may produce something that you would not expect.

How is that any different than hardware? The Pentium had a busted FPU in 1993, buggy CPUs aren't a new problem.

[sokoloff]

This is where I  often come into conflict with other engineers.  I am a practicalist.  I want to get the job done to the highest quality per effort available.

I'm not sure that C++ is the best language to accomplish the last sentence's stated goals. (And I say this as a very long time C++ programmer who has a lot of love for the "portable assembly language" that C and C++ represent.)

[bd139]

Yes that’s for Common Lisp 

Going to hide back in my hole now

[free_electron]

How about this :

time for a new number format : Algebraic
The numbers are stored as arrays of bytes
any operation performed is not calculated but stored in the number array
when cast to a lower type the 'number' (the equation) is then first algebraically solved , and then the 'calculated' result returned to a lower type .
you can ask for the full equation by asking for the 'true' number
you can ask for the algebraically reduced number using 'frac'

def x algebraic
def y algebraic
x = 1                'x now contains [1]
x = x /3            ' x now contains [1/3]
y = x *3            ' y now contains [(1/3)*3]
x = sqr(x)         ' x now contains [S(1/3)]
x = x^2            ' x now contains [(S(1/3))^2]
x = x *3            ' x now contains [((S(1/3))^2)*3]
y = y * x           ' y now contains [((1/3)*3)*((S(1/3))^2)*3]
print x              3  ' resolves to smallest format that can store in this case an integer
print x.tofloat    3.0
print y.tofloat    9.0
print x.true       ((S(1/3))^2)*3  ' this returns the actual stored sequence

when you ask for the 'value' the array is parsed algebraically to it smallest format an then it is calculated. if the result is a 'endless number' it can be returned as a fraction
For example:
x = 1/3
x = x *2
print x.float ' prints 0.666666666666
print x.true  ' prints (1/3)*2
print x.frac  ' prints 2/3       this reduced the equation without calculating any 'precision unsafe' operations like SQR and div it and shows the outcome
x = x.frac         ' reduces the algebraic equation to its simplest form and stores that.
print x.true  2/3

The format would support ln, log, sin, cos, tan, j (imaginary) and other commonly found things like e and pi.

What are the coders waiting for ?

[paulca]

Sorry to disappoint, but... your preference is simply impossible?  It seems rather... impractical, self-contradictory you might say?

If you don't like what a CPU cranks out, then fine, go... uh, sheesh... go curl up in the fetal position and cry?

No, not really.  By accepting the short comings of floating point and learning to treat them cautiously I know where to pay especial attention... because computers suck at maths.

This is all I'm saying.

[IanB]

...because computers suck at maths.

This is all I'm saying.

You have no evidence that computers suck at maths any more than humans with pen and paper suck at maths.

So really you are saying nothing at all. This whole thread is a waste of energy.

[T3sl4co1l]

Hey Ian, could you indulge me in a hypothetical for a moment?

Pray tell, what is the square root of two?  Please write out twenty decimal places.

Tim

[paulca]

Pray tell, what is the square root of two?  Please write out twenty decimal places.

It's an interesting example and a university assignment I had to do in assembler.  Thankfully to the closest integer, the square root of any number.

The traditional way computers do it is much like a school boy would.  Try, compare, adjust, try, compare.  Though with much smarter searching logic.

[IanB]

Hey Ian, could you indulge me in a hypothetical for a moment?

Pray tell, what is the square root of two?  Please write out twenty decimal places.

Tim

Isn't that my point? Clearly it's much easier for a computer to do that than a human. So to say "computers suck at maths" when they are evidently much better at it than humans is a rather pointless statement.

[paulca]

Hey Ian, could you indulge me in a hypothetical for a moment?

Pray tell, what is the square root of two?  Please write out twenty decimal places.

Tim

Isn't that my point? Clearly it's much easier for a computer to do that than a human. So to say "computers suck at maths" when they are evidently much better at it than humans is a rather pointless statement.

Okay.  Lay up now.  It's getting old.  Lets say that computers make approximations in maths which may cause your program to error out and to be aware of that.

Out of interest... I gave up at 6 decimal places, but:

Code: [Select]

1.5 * 1.5
2.2
1.4 * 1.4
1.9
1.45 * 1.45
2.10
1.42 * 1.42
2.01
1.415 * 1.415
2.002
1.412 * 1.412
1.993
1.413 * 1.413
1.996
1.414 * 1.414
1.999
1.4145 * 1.4145
2.0008
1.4142 * 1.4142
1.9999
1.4143 * 1.4143
2.0002
1.41425 * 1.41425
2.00010
1.41422 * 1.41422
2.00001
1.41421 * 1.41421
1.99998
1.414215 * 1.414215
2.000004
1.414212 * 1.414212
1.999995
1.414214 * 1.414214
2.000001
1.414213 * 1.414213
1.999998                                                                                                         
1.4142135 * 1.4142135                                                                                           
1.9999998                                                                                                       
1.4142138 * 1.4142138
2.0000006                                                                                                       
1.4142137 * 1.4142137
2.0000003                                                                                                       
1.4142136 * 1.4142136
2.0000001
1.4142135 * 1.4142135
1.9999998
1.41421355 * 1.41421355
1.99999996
1.41421356 * 1.41421356
1.99999999
1.41421357 * 1.41421357
2.00000002
1.414213565 * 1.414213565
2.000000007
1.414213562 * 1.414213562
1.999999998
1.414213563 * 1.414213563
2.000000001
1.4142135625 * 1.4142135625
2.0000000003

Is, as I understand it how computers calculate roots.  Obviously there are optimisations and hardware dedicated to this process available, but it's all just trial and error.

To take things a little off the rails.  Here is a question for the egg head grey beards...

How does a CPU divide by 3?

[691175002]

Like everyone else, I also took numerical computation in university and did all the operations by hand.  I also retained nothing other than a broad sense of caution when dealing with floating point numbers.

I suspect 1/3 is simply a combination that works by chance.  If you test your sample code with other values (such as 1/11) it fails as expected.

Code: [Select]

Python 3.5.2 |Anaconda 2.5.0 (64-bit)| (default, Jul  5 2016, 11:41:13) [MSC v.1
900 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> import numpy as np
>>> a = np.float16(1) / np.float16(3)
>>> a*np.float16(3)
1.0

>>> a = np.float16(1) / np.float16(11)
>>> a * np.float16(11)
0.99951
>>>

How does a CPU divide by 3?

IIRC It multiplies by 1/3 so that it can reuse the hardware.

[paulca]

Like everyone else, I also took numerical computation in university and did all the operations by hand.  I also retained nothing other than a broad sense of caution when dealing with floating point numbers.

Exactly.  I hold several University degrees in computing and technology.  This caution is all you need from day to day.

But we are in the presence of academics and pedants who believe that every single instruction you execute on a computer needs understanding to the bit depth on a floating point unit and failure to understand this detail is a cardinal sin which means you are not a real programmer.

This might be fine for a few hundred instructions in an MCU, but a few billion in a distributed real system with 100s of programmers, it's no longer practical.  So you need to trust and set boundaries within which to stay so you do not encounter "The dragons."

While they fettle about with that level of detail I will get actual work done, produce actual products, make actual money and get paid a shed ton of money doing so.

That said, if I had to pick a perfect software team, I would have 1 IanB, the grumpy technical pedantic engineer, 1 me, the practicalitst technical engineer, 1 business sympathetic technical engineer.  3 cookie cutter senior engineers to do the bulk of the work and 3 juniors to do the dirty work and mould into seniors.  So while the pedant approach is something I hate, it is useful to have, it can just sometimes be difficult to weigh their whinging against actual risk versus effort.

[paulca]

Isn't that my point? Clearly it's much easier for a computer to do that than a human. So to say "computers suck at maths" when they are evidently much better at it than humans is a rather pointless statement.

"Easier", "Better", "Pointless" are subjectives.

The computer is FASTER than a human, buy many orders of magnitude, but it is not, by far, better.  A computer will execute billions of mistakes faster than a human can make one.

So a lot of the maths they do is based on this fact.  The will happily make a million trial and error calculations to get an exact value a human could narrow in on in a few iterations.

EDIT:  A lot of software engineering, is about realising this.  Sorting routines, matching and filtering routines can seem horribly difficult to devise for a junior engineer, the senior realises some of the things "you" find hard are just repetitive and tedious, two things a computer has no trouble doing.  So the solution is often to just use the sheer speed of the computations to solve things brute force.

It depends on those subjective qualifiers if you consider this better.

You will note that computers rarely do maths, they simply do computation (it's kind of in the name and where it came from).  But that's a whole other kettle of fish.

[T3sl4co1l]

Pray tell, what is the square root of two?  Please write out twenty decimal places.

Out of interest... I gave up at 6 decimal places, but:

Code: [Select]

...
1.4142135625 * 1.4142135625
2.0000000003

Is, as I understand it how computers calculate roots.

You idiot!  It's not correct!  The square root of two is not, and can never be, 1.4142135623730950488!  What a stupid computer!

(Do you see how strange this looks?)

Tim