Bug/Gross InEfficiency in HeathField's fgetline program

[Malcolm McLean]

As I understand it, inexact results in monetary calculations are
*never* acceptable.

These sorts of rules go out of the window when you have hyperinflation. If
the dollar becomes nearly worthless - which <OT> is what will happen if the
Fed doesn't sharpen up its attitude to liquidity </OT> the amounts cease to
have any real meaning anyway. Your users will just be glad that the system
is still handling transactions.

In a typical modern implementation, both double and long long are 64
bits -- but long long doesn't waste bits on an exponent, and can
therefore represent a much wider range of integer values exactly.
Many implementations that don't support long long nevertheless support
a 64-bit integer type by another name.

I see you edging towards the camapign for 64 bit ints.

 

[Richard Heathfield]

Tor Rustad said:

Tor Rustad said:

Richard Heathfield wrote:
Tor Rustad said:
Richard Heathfield wrote:
Tor Rustad said:

<snip>
Furthermore, many of the calculations needed for double entry
bookeeping, can be done exactly by banks.
[...] I'm struggling to imagine any real-world
double-entry-relevant calculation that /cannot/ be done exactly.
Even if the numbers involved are colossal, they can still be
processed exactly. You might need a bignum lib to do it, but you
*can* do it.
What if the currency of the transaction, is different from the
currency
of the account?

So, you talked about *rounding*.

FYI, calculations using rounding, are not done *exactly*.

Fine, but we're actually talking about different things. I'm talking about
"calculations needed for double entry bookkeeping". You are talking about
"calculations needed for currency conversion". These are two different
ideas.

 

[Keith Thompson]

These sorts of rules go out of the window when you have
hyperinflation. If the dollar becomes nearly worthless - which <OT> is
what will happen if the Fed doesn't sharpen up its attitude to
liquidity </OT> the amounts cease to have any real meaning
anyway. Your users will just be glad that the system is still handling
transactions.

Hyperinflation is unlikely to cause amounts of money to exceed 2**64-1
(about 18 quintillion). Even if it did, the response would almost
certainly be to issue a new devalued currency (one new dollar equal to
one trillion old dollars, for example).

I see you edging towards the camapign for 64 bit ints.

Absolutely not. If you think I am, you need to re-read what I've
written (and remember that "int" and "integer" are not synonymous).

 

[Malcolm McLean]

Hyperinflation is unlikely to cause amounts of money to exceed 2**64-1
(about 18 quintillion). Even if it did, the response would almost
certainly be to issue a new devalued currency (one new dollar equal to
one trillion old dollars, for example).

The Eurpean Central bank pumped in 400 billions of Euros of liquidity last
August. There are about 650 billion Euros of currency in circulation. They
are hoping that most of that 400 billion will come back in before anyone
demands it in cash, however assuming that the full amount is taken up, they
will need to pump in about 600 billion to have the same effect next time.
Then it will be 1 trillion. Printing money is O(N^2). Pull that trick more
than a few times and you'll get up to 18 quintillion remarkably quickly.

 

[Tor Rustad]

Tor Rustad said:

Tor Rustad said:
Richard Heathfield wrote:
Tor Rustad said:
Richard Heathfield wrote:
Tor Rustad said:

<snip>
Furthermore, many of the calculations needed for double entry
bookeeping, can be done exactly by banks.
[...] I'm struggling to imagine any real-world
double-entry-relevant calculation that /cannot/ be done exactly.
Even if the numbers involved are colossal, they can still be
processed exactly. You might need a bignum lib to do it, but you
*can* do it.
What if the currency of the transaction, is different from the
currency
of the account?

So, you talked about *rounding*.

FYI, calculations using rounding, are not done *exactly*.

Fine, but we're actually talking about different things. I'm talking about
"calculations needed for double entry bookkeeping". You are talking about
"calculations needed for currency conversion". These are two different
ideas.

Methinks, you initially only considered single currency.

 

[Flash Gordon]

Keith Thompson wrote, On 03/11/07 18:00:
The only degradation an accountant would consider graceful would be an
error message along the lines of, "I am most terribly sorry but your
finances are beyond my humble capacity to compute."

- it will no longer

In other words incorrect and leading to the company submitting them as
accounts or using them for any of a number of other purposes being find
large (to the company) amounts of money.

but if there are 6 trillion dollars to

As I understand it, inexact results in monetary calculations are
*never* acceptable.

Correct. If the tax returns are found to be incorrect that can lead to
large fines. If you submit accounts that are incorrect you can get
fined. If you sell the SW that is provably at fault in such cases then
the company could pursue you for damages.

Using a floating-point type might give you an
acceptable range over which exact values can be represented,

Yes, and people have actually used double for precisely that reason.

but if
you go outside that range you *silently* get inexact results.

In a typical modern implementation, both double and long long are 64
bits -- but long long doesn't waste bits on an exponent, and can
therefore represent a much wider range of integer values exactly.
Many implementations that don't support long long nevertheless support
a 64-bit integer type by another name.

Agreed. Having a 64 bit integer type available when you need it is very
useful. Having fixed point arithmetic (especially fixed decimal point
rather than binary point) would also be very useful, more useful for me
that a lot of what went in to C99 ;-).

 

[Richard Heathfield]

Tor Rustad said:

Methinks, you initially only considered single currency.

Yes, that's right, I did. And the introduction of a discussion of multiple
currencies blurred the issue in my mind for a little while. Taking a step
back and thinking about it, I realised it represented a completely
separate issue.

I still stand by my statement that you can do double-entry book-keeping
*exactly*.

 

[Malcolm McLean]

Correct. If the tax returns are found to be incorrect that can lead to
large fines. If you submit accounts that are incorrect you can get fined.
If you sell the SW that is provably at fault in such cases then the
company could pursue you for damages.

The British Inland Revenue doesn't care about odd pennies. It might be
different in other jurisdictions.
Accountants do, but for internal quality control purposes.

 

[Flash Gordon]

Malcolm McLean wrote, On 03/11/07 23:44:

The British Inland Revenue doesn't care about odd pennies. It might be
different in other jurisdictions.

My SW sends data direct to HMRC and they *do* care about pennies, just
not in the way you might expect. On certain returns you are *required*
to specify pounds and pence and the pence are *required* to be .00, and
they specify the rounding (which is down) that you are *required* to
use. Getting the pounds wrong (and you only have to be one penny out to
do that sometimes) is not permitted.

Also, pennies add up to a lot of money.

Accountants do, but for internal quality control purposes.

They care for more than that since the pennies add up.

Also, this was with reference to using floating point numbers in
financial SW and what happens when you get beyond the range that can be
accurately represented, that can lead to errors far larger than pennies.

 

[Chris Torek]

Keith Thompson wrote, On 03/11/07 18:00:
Well, it depends on the purpose of the calculations ... for instance
if I am doing a rough estimate of future values of various funds
flows, I do not need exact results, because I am putting in estimates
for rates of return and only expect a rough estimate as output.

However, in other areas, well:

Correct. If the tax returns are found to be incorrect that can lead to
large fines. If you submit accounts that are incorrect you can get
fined. If you sell the SW that is provably at fault in such cases then
the company could pursue you for damages.

Someone rather more well off than I am used a certain Borland
product to calculate his US taxes, some years ago. He actually
owed somewhere around five million dollars, if I remember right;
but the tax software claimed he owed a negative number.

He called their support people and directed their attention to
their guarantee of correctness, which said that, in the case of
any error on their part, they would pay the difference between what
their software computed, and what was actually owed. Fun times
ensued.

(The culprit turned out to be internal use of 32-bit integer types.
Once the correct number was computed, he had another adventure:
it turns out that one cannot write ordinary checks [or "cheques",
for those in the UK and Canada] for more than about one million
dollars at a time. In his case, it sufficed to simply send five
of them.)

... Having a 64 bit integer type available when you need it is very
useful. Having fixed point arithmetic (especially fixed decimal point
rather than binary point) would also be very useful, more useful for me
that a lot of what went in to C99 ;-).

One can always use the 64-bit integral type along with "manual"
fixed-point scaling, so that, e.g., 215256249812543 represents
$2,152,562,498,125.43 (a little over two trillion dollars, or about
what Iraq will most likely cost US taxpayers). One must still take
care to avoid rounding errors with internal calculations, though;
I note that a number of COBOL compilers allow up to 63 decimal
digits in intermediate results, to avoid problems here.

 

[Flash Gordon]

Chris Torek wrote, On 04/11/07 10:07:

Well, it depends on the purpose of the calculations ... for instance
if I am doing a rough estimate of future values of various funds
flows, I do not need exact results, because I am putting in estimates
for rates of return and only expect a rough estimate as output.

Yes, I can see that. The same would actually apply to some of the
reports we produce which are purely for budgetary purposes. However, so
much is for purposes where accuracy is a legal requirement that we just
do everything accurately.

However, in other areas, well:



Someone rather more well off than I am used a certain Borland
product to calculate his US taxes, some years ago. He actually
owed somewhere around five million dollars, if I remember right;
but the tax software claimed he owed a negative number.

Humans often beet computers at spotting the obviously wrong results

He called their support people and directed their attention to
their guarantee of correctness, which said that, in the case of
any error on their part, they would pay the difference between what
their software computed, and what was actually owed. Fun times
ensued.

Yes, I can imagine.

(The culprit turned out to be internal use of 32-bit integer types.
Once the correct number was computed, he had another adventure:
it turns out that one cannot write ordinary checks [or "cheques",
for those in the UK and Canada] for more than about one million
dollars at a time. In his case, it sufficed to simply send five
of them.)

Seems a daft restriction to me.

One can always use the 64-bit integral type along with "manual"
fixed-point scaling, so that, e.g., 215256249812543 represents
$2,152,562,498,125.43 (a little over two trillion dollars, or about
what Iraq will most likely cost US taxpayers).

This is, indeed, what we do. It would just simplify the SW a lot if we
did not have to do it.

One must still take
care to avoid rounding errors with internal calculations, though;
I note that a number of COBOL compilers allow up to 63 decimal
digits in intermediate results, to avoid problems here.

Old languages still have some advantages

 

[David Thompson]

"Richard Heathfield" <[email protected]> a écrit dans le message de news:

strncpy can be banned with no downside.

Or only a very tiny one. Which I for one would be happy to accept.

Pointers are a fundamental feature of the language.

That's true.

The class of problems that can be solved without them has
a topological measure of zero.

I'm not absolutely certain what you meant here. From my brief and
long-ago exposure to topology I am under the impression that it deals
(or did) with binary/Boolean connectedness, not things that would
reasonably be called measures. I did pass briefly by measures in some
other branches of mathematics, in some of which measure zero was,
counterintuitively, actually quite large.

But from context I think you meant something like 'tiny' or
'negligible'. If so, that's not strictly true. You can implement any
finite set of finite arrays by things more or less like:

/* double x [N]; being simulated */
double getx (size_t i) {
if( i == 0 ) return x0;
else if( i == 1 ) return x1;
else if( i == 2 ) return x2;
/* else's not actually needed but included for symmetry */
... }
void putx (size_t i, double v) {
if( i == 0 ) x0 = v;
else if( i == 1 ) x1 = v;
... }

and you can either implement 'reference' parameters to functions in a
similar way, with a smaller set of larger aggregates, or by having the
caller(s) copy in and out, as in classic BASIC(s).

These aren't GOOD solutions; in fact they're atrocious. But they are
solutions, and thus formally put those problems in the 'solved' class.
(Leaving aside that formally, in the C abstract machine, function
calls, even of specific functions, use a function pointer value. But
the discussion as I understood it was about data pointers. Plus in
practice calls to specific functions are almost(?) always implemented
as direct calls, with no pointer. Sometimes a stub or jacket, but
those can't 'point' to more than one routine and so can't really
semantically be considered pointers.)

- formerly david.thompson1 || achar(64) || worldnet.att.net

 

[Malcolm McLean]

But from context I think you meant something like 'tiny' or
'negligible'. If so, that's not strictly true. You can implement any
finite set of finite arrays by things more or less like:

/* double x [N]; being simulated */
double getx (size_t i) {
if( i == 0 ) return x0;
else if( i == 1 ) return x1;
else if( i == 2 ) return x2;
/* else's not actually needed but included for symmetry */
... }

As long as you've got an input and and output statement, you can in fact
implement any program without pointers. That's a fundamental theorem.

 

[Flash Gordon]

Malcolm McLean wrote, On 05/11/07 00:10:

But from context I think you meant something like 'tiny' or
'negligible'. If so, that's not strictly true. You can implement any
finite set of finite arrays by things more or less like:

/* double x [N]; being simulated */
double getx (size_t i) {
if( i == 0 ) return x0;
else if( i == 1 ) return x1;
else if( i == 2 ) return x2;
/* else's not actually needed but included for symmetry */
... }

As long as you've got an input and and output statement,

Which in C use pointers, so you can only use them by using pointers.
After all, stdin, stdout and stderr are pointers and when you call a
function you are using a pointer to a function.

you can in fact
implement any program without pointers.

In ALL languages? Even one where the only way to do input or output
involves using a pointer?

That's a fundamental theorem.

It is easy to prove that it is incorrect for at least one language.

 

[Richard Bos]

Malcolm McLean wrote, On 05/11/07 00:10:


Which in C use pointers, so you can only use them by using pointers.
After all, stdin, stdout and stderr are pointers and when you call a
function you are using a pointer to a function.


In ALL languages? Even one where the only way to do input or output
involves using a pointer?


It is easy to prove that it is incorrect for at least one language.

It's Malcolm's usual muddle. The fundamental theorem, which has not even
been proved (though there is a great deal of circumstantial evidence for
it, and none against) is that any _calculation_ can be done on a Turing
machine. To leap from any calculation to any program is a bit of a long
one, though. Generally, programs have more requirements than that they
perform a single calculation.

Richard

 

[Flash Gordon]

Richard Bos wrote, On 05/11/07 11:15:

It's Malcolm's usual muddle. The fundamental theorem, which has not even
been proved (though there is a great deal of circumstantial evidence for
it, and none against) is that any _calculation_ can be done on a Turing
machine.

That theorem I know, I just did not make the connection from what
Malcolm said. However, has anyone proved that C without pointers is
Turing complete? If not, then that needs to be done before Malcolm can
use that theorem.

To leap from any calculation to any program is a bit of a long
one, though. Generally, programs have more requirements than that they
perform a single calculation.

Indeed.

 

[Richard Heathfield]

Richard Bos said:

The fundamental theorem, which has not even
been proved (though there is a great deal of circumstantial evidence for
it, and none against)

Oh my dear chap, you're beginning to make a bit of a habit of being wrong,
aren't you? If it's a theorem, it *has* been proved. If it has not been
proved, it is not a theorem. (Fermat's Last Theorem was for centuries a
misnomer, because it hasn't been proved. Now it's a misnomer because the
proof was supplied by Wiles, not Fermat.)

is that any _calculation_ can be done on a Turing
machine.

Wrong again! It's that any computable problem can be computed on a Turing
machine. Some problems are not computable. For example, the Halting
Problem (which we might express as "write a program that calculates
whether an arbitrary program (supplied at runtime) will eventually halt")
cannot be computed.

 

[Chris Dollin]

Richard Bos said:



Oh my dear chap, you're beginning to make a bit of a habit of being wrong,
aren't you? If it's a theorem, it *has* been proved. If it has not been
proved, it is not a theorem.

Richard is referring (if I am not mistaken) to the Church-Turing /thesis/.

So you're right: it's not a theorem. (Off-hand, I recall it as too informal
to realistically expect a /proof/ of it.)

I don't think your position that unproved statements cannot be theorems
is sound, however, even if one discounts the fact that names that look
like descriptions need not be accurate labels.

 

[Richard]

What a load of rubbish.

Fermat's last theorem wasn't "proven" until 1994.

 

[Richard Heathfield]

Chris Dollin said:

Richard is referring (if I am not mistaken) to the Church-Turing
/thesis/.
Indeed.

So you're right:

Natch.

it's not a theorem. (Off-hand, I recall it as too
informal to realistically expect a /proof/ of it.)

I don't think your position that unproved statements cannot be theorems
is sound, however, even if one discounts the fact that names that look
like descriptions need not be accurate labels.

This, however, is interesting. If I'm wrong, two useful things happen:

1) I get egg all over my face for incorrectly tweaking RB's nose;
2) I learn something.

Nevertheless, alas, I am not yet convinced that I am wrong. Not being a
mathematician, I have little recourse but to look at the mathematical
equivalent of Wikipedia and hope that it's a bit more accurate. Here is
what it has to say about theorems:

"A theorem is a statement that can be demonstrated to be true by accepted
mathematical operations and arguments. In general, a theorem is an
embodiment of some general principle that makes it part of a larger
theory. The process of showing a theorem to be correct is called a proof."

The case for the defence rests, m'lud.