Oberon Community Platform Forum
December 07, 2019, 07:41:22 AM *
Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length
News:
 
   Home   Help Search Login Register  
Pages: [1]
  Print  
Author Topic: Arithmetic aberrations in Java and Oberon  (Read 14050 times)
manumart1
Newbie
*
Posts: 7


« on: January 09, 2010, 12:23:18 PM »

Code:
MODULE TestArithmeticInOberon;
IMPORT StdLog, Math;

(*
The purpose of this module is to test the floating-point and integer arithmetic implementation under Oberon.
I have made these tests because I found some disturbing problems under Java, and I wondered if Oberon would have solved them.
The answer is no; similar problems arise in Oberon.
*)

(* NOTE: I have used the BlackBox IDE and Windows XP to run the Test, and I would be very happy if someone read this and make the necessary changes to the Oberon language in order to solve what I think are problems.

But I am pesimistic: I am sure that the clever people who designed and implemented such wide variety of languages (C, C++, Java, Oberon, ...) are already aware of these problems, and if they have not solved them yet, it must be because they are really hard or irresoluble problems.

I confess my ignorance about the intricacies of floating-point and integer arithmetic. So, PLEASE, do not take too seriously what I say in this text. It is only the fruit of the state, the limited state, of my knowledge about these themes.

All over this text, I have had the impression that perhaps I was pointing to an innocent --the language-- and that the real guilty is the mathematical co-processor. In fact, perhaps there is no guilty at all, and all these problems are only the unavoidable consequences of the limited precision of the representation of real numbers inside the machine. (As an aside, I wonder: the big supercomputers used for scientific computation, How do they perform about mathematical operations?)

On the other side, I feel deceived, I consider a shame that a secure high-level language --offering clean, elegant and comfortable concepts like Information Hiding, Modularization, Interfaces, Abstract Data Types, Inheritance, Polymorphism, etc, etc, that puts a lot of distance between the raw, bare machine and the person who is writing a program-- forces you sometimes to be aware of the nastiness living underground, in registers of the CPU or in cells of memory. Suddently, the dirt underneath sprinkles you. When you are wearing an evening dress, you do not expect your underpants to be seen.

For example, it surprises me a lot that if I have an INTEGER variable holding a positive value, and if I only sum positive quantities to it, then when the maximum allowable value has been passed over, that variable gets a negative value assigned to it, and the program continues happily without abending its execution. I would rather expect a runtime error, similar to the error you get when you assign the value "zero divided by zero" to a REAL variable, or when you divide (DIV) by zero and assign the result to an INTEGER variable. Another example: it also surprises me that the condition "(0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1) = 1.0" evaluates to false; or that "(a + b) + c = a + (b + c)" is not always true.

Surprises, surprises, ... the spanish philosopher Jose Ortega y Gasset used to say "To be astonished, to be surprised because of something, is to begin to understand it".

The purpose of this text have shifted as I was writing it. I begun it as a critique of what I thought were pitfalls of some programming languages, but now I think that the main purpose is to help other people to take awareness of the following truth: "Do not think that because you are using a powerfull, comfortable and secure high-level language, you have got away from the bits. The bare and cold machine always imposes its rules".
*)


PROCEDURE TestingRealSums*;
(*
Oberon --and many (all?) other languages-- has some annoying problems computing real sums
============================================================================
Oberon behaves wrong --like Java-- at this subject.
But I think Oberon performs somehow better than Java:
Oberon:
Statements IF's okey: #1, #3
Variables okey: a, b, c, x, z
Java:
Statements IF's okey: #1, #2
Variables okey: a, b, x, y

The value of the variable c in the test, gets right under Oberon, but not under Java.
On the other side, the value "1.0 - (10 * a)" (being 0.1 the value of a) is evaluated correctly to zero under Java, but not in Oberon.

Take the decimal number 0.1 and sum it 10 times. You should get 1.0 as result, do not you?

This test shows that the result is correct only when you use auxiliary variables to hold intermediate results.
For example, instead of
N := 1.0 - (0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1);
you should use:
a := 0.1;
aux := a + a + a + a + a + a + a + a + a + a;
N := 1.0 - aux;
Only then you arrive at N with the correct value of 0.0.
But be aware that this test is only an example. I guess that there could exist the opposite example, i.e. one expression okey with literals and wrong with auxiliary variables.

This is disturbing. The fact that the program goes to the ELSE branch of the IF-s statements is nothing more than an arithmetic aberration.

This problem has its origin in the fact that the simple and finite decimal number 0.1 has a binary representation as an infinite sequence of bits: 0.0001100110011001100..., but you can only store a finite number of bits in the computer.
*)
VAR a, b, c, d, x, y, z, u, v, w: REAL;
BEGIN
StdLog.Ln;
StdLog.String("***** TestingRealSums *****"); StdLog.Ln;
StdLog.Ln;

a := 0.1;
b := 10 * a;
c := a + a + a + a + a + a + a + a + a + a;
d := 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1;

x := 1.0 - b;
y := 1.0 - (10 * a);

z := 1.0 - c;
u := 1.0 - (a + a + a + a + a + a + a + a + a + a);

v := 1.0 - d;
w := 1.0 - (0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1);

StdLog.String("a = "); StdLog.Real(a); StdLog.Ln;
StdLog.Ln;

StdLog.String("b = "); StdLog.Real(b); StdLog.Ln;
StdLog.String("10 * a = "); StdLog.Real(10 * a ); StdLog.Ln;
StdLog.Ln;

StdLog.String("c = "); StdLog.Real(c); StdLog.Ln;
StdLog.String("a + a + a + a + a + a + a + a + a + a = "); StdLog.Real(a + a + a + a + a + a + a + a + a + a); StdLog.Ln;
StdLog.Ln;

StdLog.String("d = "); StdLog.Real(d); StdLog.Ln;
StdLog.String("0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 = "); StdLog.Real(0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1); StdLog.Ln;
StdLog.Ln;

StdLog.String("x = "); StdLog.Real(x); StdLog.Ln;
StdLog.String("y = "); StdLog.Real(y); StdLog.Ln;
StdLog.Ln;
StdLog.String("z = "); StdLog.Real(z); StdLog.Ln;
StdLog.String("u = "); StdLog.Real(u); StdLog.Ln;
StdLog.Ln;
StdLog.String("v = "); StdLog.Real(v); StdLog.Ln;
StdLog.String("w = "); StdLog.Real(w); StdLog.Ln;
StdLog.Ln;

IF b = 1.0 THEN
StdLog.String("[IF #1] Oberon is fine. It has computed the sum rightly."); StdLog.Ln
ELSE
StdLog.String("[IF #1] ERROR: Oberon is wrong. It has computed the sum badly !!"); StdLog.Ln
END;

IF (10 * a) = 1.0 THEN
StdLog.String("[IF #2] Oberon is fine. It has computed the sum rightly."); StdLog.Ln
ELSE
StdLog.String("[IF #2] ERROR: Oberon is wrong. It has computed the sum badly !!"); StdLog.Ln
END;

IF c = 1.0 THEN
StdLog.String("[IF #3] Oberon is fine. It has computed the sum rightly."); StdLog.Ln
ELSE
StdLog.String("[IF #3] ERROR: Oberon is wrong. It has computed the sum badly !!"); StdLog.Ln
END;

IF (a + a + a + a + a + a + a + a + a + a) = 1.0 THEN
StdLog.String("[IF #4] Oberon is fine. It has computed the sum rightly."); StdLog.Ln
ELSE
StdLog.String("[IF #4] ERROR: Oberon is wrong. It has computed the sum badly !!"); StdLog.Ln
END;

IF d = 1.0 THEN
StdLog.String("[IF #5] Oberon is fine. It has computed the sum rightly."); StdLog.Ln
ELSE
StdLog.String("[IF #5] ERROR: Oberon is wrong. It has computed the sum badly !!"); StdLog.Ln
END;

IF (0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1) = 1.0 THEN
StdLog.String("[IF #6] Oberon is fine. It has computed the sum rightly."); StdLog.Ln
ELSE
StdLog.String("[IF #6] ERROR: Oberon is wrong. It has computed the sum badly !!"); StdLog.Ln
END;

StdLog.Ln
END TestingRealSums;


PROCEDURE TestingAssociativity*;
(*
Oberon --and many (all?) other languages-- does not always follow the associativity property of addition
===================================================================================
Oberon behaves wrong --like Java-- at this subject.

To find the values for the variables a, b and c which broke the associativity property of addition, I fixed the values of a (0.1) and b (0.3) and then I continuosly probed the values "k + 0.1" (k= 1, 2, 3, ...) for c. The first value breaking the associativity property was 2048.1, and then all the following up to 4096.1 also broke the property.

I have to say that these values --0.1, 0.3, 2048.1-- do not broke the associativity property under Java, but using the same schema I found initially much more values breaking the associativity property: 1.1, 4.1, 5.1, 6.1, 7.1, 16.1, 17.1, ..., 2045.1, 2046.1, 2047.1, 4096.1, 4097.1, ... Between 1.1 and 4096.1 there were 1366 hit values for c under Java. Very strangely, in Oberon all the values between 2048.01 and 4095.1 were hit values; note that none of these were hits for Java. In Oberon, after the hit value 4095.1 we have to wait until 8192.1 to find the next hit value.

Lamentably, I think there is no solution for this problem. We have to be docile and accomodate to these results.
*)
VAR
a, b, c: REAL;
k: INTEGER;
BEGIN
StdLog.Ln;
StdLog.String("***** TestingAssociativity *****"); StdLog.Ln;
StdLog.Ln;

(*
a := 0.1;
b := 0.3;
c := 0.1;
FOR k := 1 TO 10000 DO
c := k + 0.1;
IF (a + b) + c = a + (b + c) THEN
ELSE
StdLog.String("ERROR: Oberon is wrong. The associativity property of addition has been violated !!");
StdLog.Real(c); StdLog.Ln
END
END;
RETURN;
*)

IF (0.1 + 0.3) + 2048.1 = 0.1 + (0.3 + 2048.1) THEN
StdLog.String("[IF #1] Oberon is fine. The associativity property of addition has been followed."); StdLog.Ln
ELSE
StdLog.String("[IF #1] ERROR: Oberon is wrong. The associativity property of addition has been violated !!"); StdLog.Ln;
END;

a := 0.1;
b := 0.3;
c := 2048.1;
IF (a + b) + c = a + (b + c) THEN
StdLog.String("[IF #2] Oberon is fine. The associativity property of addition has been follow."); StdLog.Ln
ELSE
StdLog.String("[IF #2] ERROR: Oberon is wrong. The associativity property of addition has been violated !!"); StdLog.Ln;
END;

StdLog.Ln
END TestingAssociativity;


PROCEDURE TestingDivideByZero*;
(*
Oberon behaves okey when you try to divide by zero.
============================================
Dividing by zero always throws a runtime exception in Java, and the execution is interrupted.
But Oberon instead assigns the special value "infinite" to the result, if you are working with REAL variables, or abends the program if the variable is INTEGER. I am far from being an expert, but I think Oberon is following very well the guidelines from the IEEE-754 standard for floating-point binary arithmetic.
*)
VAR
a, b: REAL;
n, k: INTEGER;
BEGIN
StdLog.Ln;
StdLog.String("***** TestingDivideByZero *****"); StdLog.Ln;
StdLog.Ln;

a := 0.0;
StdLog.String("I am going to divide by zero, using REAL variables ..."); StdLog.Ln;
b := 8.0 / a;
StdLog.String("... I have just divided by zero, using REAL variables. This is the result. b = "); StdLog.Real(b); StdLog.Ln;

b := b + 787878;
StdLog.String("b + 787878 = "); StdLog.Real(b); StdLog.Ln;

n := 0;
StdLog.String("I am going to divide by zero, using INTEGER variables ..."); StdLog.Ln;
k := 3 DIV n;
StdLog.String("... I have just divided by zero, using INTEGER variables. This is the result. k = "); StdLog.Int(k); StdLog.Ln;

k := k + MAX(INTEGER);
StdLog.String("k = "); StdLog.Int(k); StdLog.Ln;

StdLog.Ln
END TestingDivideByZero;


PROCEDURE TestingOverflow*;
(*
Oberon does not detect the overflow.
===============================
Oberon behaves wrong --like Java-- at this subject.

If I take an INTEGER variable with holds the maximum admisible value for its type, and I try to increment that variable by one, it is clear that the result does not fit. So I would expect to get an error alerting of that problem, and the execution to be abruptly interrupted. But instead, the variable got a negative number assigned to it (in fact, the value is the minimum possible), and the program does not mind about it. This is an annoying surprise for me. There have to exist hidden reasons out of my reach for this strange behavior. I do not know. When you are incrementing the variable, it behaves like a circle: when the maximum value has been reached, it goes to the minimum value and begin to start. Perhaps this is okey for some applications.

From my point of view this is a grave error, because the abstraction "INTEGER" offered by the language has been broken silently at runtime, and the program continues executing; perhaps crashing later somewhere else. Or, if the program does not crash later because of this, the results offered would be incorrect and nobody would ever know about it. Certainly, this is not what I expect from a secure high-level language.
To say that it is the responsibility of the programmer to insure that the result of a computation will not produce a value beyond the data type, is like to say that it is his responsibility to insure that working with an array he will never use an index position out of its bounds. The language C does not make array bound checking, and it has been worthly critized because of this.

I know that Oberon (BlakBox) has a module named "Integers" to perform operations with integers of arbitrary size, but this does not solve the problem afecting the primitive type INTEGER.

Another way to provoke an overflow is working with INTEGER and SHORTINT (or BYTE) variables at the same time. In Java you can down-cast a value "int" to "short" or "byte", but you can arrive at stranges surprises if the result does not fit: the value assigned to the smaller variable can be negative (besides the large value did not), and without any arithmetic relation to the initial large value. The same occurs in Oberon. Instead of this, I wonder if it would not be better to abend the program at runtime. Or perhaps this behavior is intentionally so, suited for system or low-level programming. I do not know.
*)
VAR
n: INTEGER;
k: INTEGER;
s: SHORTINT;
BEGIN
StdLog.Ln;
StdLog.String("***** TestingOverflow *****"); StdLog.Ln;
StdLog.Ln;

n := MAX(INTEGER); (* 2147483647 is the maximum value admited in an variable of type INTEGER *)
StdLog.String("n = "); StdLog.Int(n); StdLog.Ln;

INC(n); (* This ought to raise an OVERFLOW ERROR, but Oberon DOES NOT detect it !! Instead, Oberon assigns the negative value -2147483648 to n. *)

StdLog.String("n + 1 = "); StdLog.Int(n); StdLog.Ln;

INC(n);
StdLog.String("n + 2 = "); StdLog.Int(n); StdLog.Ln;

StdLog.Ln;

k := 123456789;
s := SHORT(k);
StdLog.String("I have assigned the INTEGER value "); StdLog.Int(k); StdLog.String(" to a variable of type SHORTINT, and this is the result: "); StdLog.Int(s);

StdLog.Ln
END TestingOverflow;


PROCEDURE TestKahanDarcy_1*;
(*
Oberon does not pass this test.
=========================
Oberon behaves wrong --like Java-- at this subject.
I suppose this is a minor problem. Perhaps only perfect arithmetic would pass this test. Is perfect floating-point arithmetic possible?
*)
(*
Test #1 of William Kahan and Joseph D. Darcy to know if the machine --the programming language-- computes accuracely the numeric operations. (Note: William Kahan is the person who designed the IEEE-754 standard for floating-point binary arthimetic)

View page 38 at "How Java's Floating-Point Hurts Everyone Everywhere" (http://www.cs.berkeley.edu/~wkahan/JAVAhurt.pdf)

Let be the sequence "x0, x1, x2, x3, ..." where
x[0] = 4
x[1] = 4.25
x[n] = f(x[n-1], x[n-2]) for n >= 2
f[y,z] = 108 - (815 - (1500/z)) / y

In perfect arithmetic, that sequence ought to tend to 5 when n grows.
If the sequence tends to 100 (instead of 5) then the CPU --the language-- is not perfect computing numeric operations.
That sequence is very sensible: if we take a slightly diferent starting point than (x0, x1) = (4, 4.25) --say (4, 4.27)-- then it is okey than x[n] tends to 100 instead of 5.
*)
CONST
X0 = 4.0;
X1 = 4.25;
NUM_MAX_ITERATIONS = 50;
VAR
xA, xB, xC: REAL;
k: INTEGER;

PROCEDURE F (y,z: REAL): REAL;
BEGIN
RETURN 108 - (815 - (1500/z)) / y
END F;

BEGIN (* TestKahanDarcy_1 *)
StdLog.Ln;
StdLog.String("***** TestKahanDarcy_1 *****"); StdLog.Ln;
StdLog.Ln;

xA := X0;
xB := X1;
xC := 0;
StdLog.Real(X0); StdLog.String("   ");
StdLog.Real(X1); StdLog.String("   ");
FOR k := 2 TO NUM_MAX_ITERATIONS DO
xC := F(xB, xA);
xA := xB;
xB := xC;
StdLog.Real(xB); StdLog.String("   ");
IF k MOD 10 = 0 THEN StdLog.Ln END
END;

StdLog.Ln
END TestKahanDarcy_1;


PROCEDURE TestKahanDarcy_2*;
(*
Oberon does not pass this test.
=========================
Oberon behaves wrong --like Java-- at this subject.
I suppose this is a minor problem. Perhaps only perfect arithmetic would pass this test. Is perfect floating-point arithmetic possible?
*)
(*
Test #2 of William Kahan and Joseph D. Darcy to know if the machine --the programming language-- computes accuracely the numeric operations. (Note: William Kahan is the person who designed the IEEE-754 standard for floating-point binary arthimetic)

View page 39 at "How Java's Floating-Point Hurts Everyone Everywhere" (http://www.cs.berkeley.edu/~wkahan/JAVAhurt.pdf)

Let be the function H(x) defined like this:
H(x) = E(Q(x) * Q(x))
E(z) = "if x = 0 then 1 else (exp(z) - 1) / z"
Q(x) = abs(x - sqrt(x*x + 1)) - (1 / (x + sqrt(x*x + 1))

If we take x= 15.0, 16.0, 17.0, 18.0, ... 9999.0 then the value of H(x) ought to be 1.
If we found that H(x) = 0, then the CPU --the language-- is not perfect computing numeric operations.
*)
VAR x: REAL;

PROCEDURE Q (x: REAL): REAL;
BEGIN
RETURN ABS(x - Math.Sqrt(x*x + 1)) - (1 / (x + Math.Sqrt(x*x + 1)))
END Q;

PROCEDURE E (z: REAL): REAL;
BEGIN
IF z = 0 THEN
RETURN 1
ELSE
RETURN (Math.Exp(z) - 1 ) / z
END;
END E;

PROCEDURE H (x: REAL): REAL;
VAR
q: REAL;
BEGIN
q := Q(x);
RETURN E(q * q)
END H;

BEGIN (* TestKahanDarcy_2 *)
StdLog.Ln;
StdLog.String("***** TestKahanDarcy_2 *****"); StdLog.Ln;
StdLog.Ln;

x := 15;
WHILE x <= 100 DO
StdLog.Real(H(x)); StdLog.String("   ");
(* IF Q(x) * Q(x) = 0.0 THEN StdLog.String("...IS ZERO !!   ") ELSE StdLog.String("...is not zero   ") END; *)
(* StdLog.Real(ABS(x - Math.Sqrt(x*x + 1))); StdLog.String(" - "); StdLog.Real(1 / (x + Math.Sqrt(x*x + 1))); *)
IF ENTIER(x) MOD 10 = 0 THEN StdLog.Ln END;
x := x + 1
END;

StdLog.Ln
END TestKahanDarcy_2;

END TestArithmeticInOberon.

TestArithmeticInOberon.TestingRealSums;
TestArithmeticInOberon.TestingAssociativity;
TestArithmeticInOberon.TestingDivideByZero;
TestArithmeticInOberon.TestingOverflow;
TestArithmeticInOberon.TestKahanDarcy_1;
TestArithmeticInOberon.TestKahanDarcy_2;
« Last Edit: August 03, 2010, 02:06:56 PM by manumart1 » Logged
cfbsoftware
Full Member
***
Posts: 107


WWW
« Reply #1 on: January 10, 2010, 04:52:57 AM »

I have used the BlackBox IDE and Windows XP to run the Test, and I would be very happy if someone read this and make the necessary changes to the Oberon language in order to solve what I think are problems.
I have insufficient experience in the theory of mathematical programming to discuss the finer points of your post but I do have a couple of relevant general comments:

1. Be careful to distinguish between "language design" issues and "language implementation" issues.

2. Note that BlackBox implements the language Component Pascal. Although this is based on Oberon-2 there are major implementation differences. A number of problems related to floating-point processing have been raised previously on the BlackBox mailing list. Some of these have been fixed in the latest release candidate (1.6-rc6) which is not listed on their website. You are more likely to find others with experience of the BlackBox issues on the BlackBox mailing list rather than here.

3. There are compiler switches / options available in the BlackBox compiler to trap integer overflow etc. There are arguments both for and against what the default value should be. I tend to agree with you today, but I might think differently tomorrow. It depends on the context.

Quote
I confess my ignorance about the intricacies of floating-point and integer arithmetic.
I recommend that you read "What Every Computer Scientist Should Know About Floating-Point Arithmetic" for explanations of some of your concerns:

http://docs.sun.com/source/806-3568/ncg_goldberg.html

I don't claim to understand all of it Wink
Logged

Chris Burrows
Astrobe v7.0 (Feb 2019): Oberon for ARM Cortex-M3, M4 and M7 Microcontrollers
http://www.astrobe.com
manumart1
Newbie
*
Posts: 7


« Reply #2 on: January 23, 2010, 10:38:30 AM »

I am very grateful to cfbsoftware for the link "What Every Computer Scientist Should Know About Floating-Point Arithmetic" (http://docs.sun.com/source/806-3568/ncg_goldberg.htm").

It looks hard, but I am going to read it with great interest.

Thank you
Logged
manumart1
Newbie
*
Posts: 7


« Reply #3 on: February 27, 2010, 10:35:35 AM »

Suppose you have bought two things: one costed 7.19 euros and the other 1.18 euros. So the total price is 8.37 euros, is not it?

In Java:
Code:
double a = 7.19;
double b = 1.18;
double total = a + b;
System.out.println("total = "+ total);

In Oberon (Component Pascal, BlackBox):
Code:
a, b, total: REAL;
a := 7.19; b:= 1.18;
total := a + b;
StdLog.String("total = "); StdLog.Real(total); StdLog.Ln;

The answer in Java and Oberon is the same:

   8.370000000000001

This arithmetic anomaly is disturbing. How can it be? Even the simple calculator of my mobile telephone knows how to compute this sum correctly !

Of course this problem arises because there are finite decimal numbers than can only be represented in binary by an infinite sequence of bits. For instance, if you convert the decimal number 2.35 into binary, you obtain:

   10.0101100110011001100110... (the 4 bits 0110 repeat forever)

But you can not store infinite bits in the computer. If you take only 53 bits then the decimal number actually represented is (using by hand the Windows calculator):

   2.3499999999999996447286321199499

but not 2.35


In the article "Where's your point? Tricks and traps with floating point and decimal numbers" (http://www.ibm.com/developerworks/java/library/j-jtp0114/) by Brian Goetz, I have read the following paragraph:
Quote
Don't use floating point numbers for exact values.
Some non-integral values, like dollars-and-cents decimals, require exactness.
Floating point numbers are not exact, and manipulating them will result in rounding errors.
As a result, it is a bad idea to use floating point to try to represent exact quantities like monetary amounts.
Using floating point for dollars-and-cents calculations is a recipe for disaster.
Floating point numbers are best reserved for values such as measurements, whose values are fundamentally inexact to begin with.

Brian Goetz advise to use the class BigDecimal in Java to treat with numbers that represent money. Note that this class uses decimal --and not binary-- arithmetic.

I wonder if it not would be helpful to have in Oberon a new primitive data type called DECIMAL(p,s) similar to the data type offered by some relational databases. "p" stands for precision, and "s" for scale. For instance DECIMAL(10,2) means "a signed number with 10 digits, two of them are fractionals. Therefore its values range from -99999999.99 to +99999999.99". And all the operations with variables of this type, will be performed in decimal fixed-point, rather than binary floating-point. Since hardware typically only provide binary floating-point support, the decimal arithmetic would have to be implemented by the compiler.

If the idea of a new primitive data type does not seems good, you can think about an utility user data type similar to the BigDecimal class in Java. Perhaps Oberon already has this type, I do not know.


----------

Changing the topic, now I leave the convenience of decimal fixed-point arithmetic to treat with variables holding money, and I focus in explicit binary floating-point arithmetic.

As Brian Goetz says, floating-point arithmetic is not exact due to limited precision and roundoffs, but it is okey for variables holding values from a sensor, because those values are approximations and they have never been originally in decimal like the money are.

If you have a decimal constant in your program, do not expect that that value will be exactly converted into binary.

Taking an example from "Comparing floating point numbers" (http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm) by Bruce Dawson, these are some consecutives floating-point values using 32 bits:
   ...
   1.99999976
   1.99999988
   2.00000000
   2.00000024
   2.00000048
   ...

Between 2.00000000 and 2.00000024 there are a lot (infinite) real numbers, but each of them happen to be mapped into only one of two floating-point numbers: either 2.00000000 or 2.00000024.

       2.00000000       2.00000024
   ...------+----------------+------...
            <-------||------->


One thing are the real numbers (they are an ideal; they are infinite) and other thing are the floating-point numbers (they are concrete; under a given representation --32 or 64 bits-- there exists a limited number of them).

With 32 bits it is easy to imagine that the infinite real numbers between 2.00000012 and 2.00000023 will be repaced by the floating-point number 2.00000024, and real numbers between 2.00000001 and 2.00000011 will be repaced by the floating-point number 2.00000000.

So "2.00000014 = 2.00000023" is true because both of them are replaced by 2.00000024.
But "2.00000011 = 2.00000013" is false because it is like evaluating "2.00000000 = 2.00000024".
Note the inconsistency: 2.00000011 and 2.00000013 are considered different, but actually they are "more equal" than 2.00000014 and 2.00000023 are.

If you have in your program the constant 2.00000015 (32 bits) then the true number that the computer will be working with will be 2.00000024. Putting it simply, the computer is not able to know about 2.00000015; that number is beyond its representation capability (using 32 bits) and instead it has to use 2.00000024.

And even this may vary: it is not the same to have the constant permanently stored in a fixed memory cell --something which happens when you declare a constant--, than to use a bare literal constant (not previously declared) inside an expression. In the latter case, the value of the volatile constant will sprout for the first time in a CPU register, which tipically has more bits of precision, and so the value will be closer to 2.00000015 than 2.00000024 is.

Similarly happen with 64 bits, but the floating-point numbers are more precise.

These seem to be the different floating-point numbers under 64 bits:
   ...
   2.0000000000000000
   2.0000000000000004
   2.0000000000000010
   2.0000000000000013
   2.0000000000000018
   2.0000000000000020
   2.0000000000000027
   2.0000000000000030
   ...

And because of that, the real numbers 2.0000000000000012 and 2.0000000000000015 are mapped into the same floating-point number 2.0000000000000013, and they look to be equal !! (you can try it)

As you can see, floating-point representation is full of surprises:

  • Sometimes you find that two expressions known to be equal are different (7.19 + 1.18 # 8.37)
  • Other times you find the opposite (2.0000000000000012 = 2.0000000000000015)

Bruce Dawson says that you can not use happily the equal comparison operator with floating-point numbers. For example, you can compute "(a+b)+c" on one hand, and "a+(b+c)" on the other. Although the result will have to be the same, due to roundoffs it easily will not be.

What is needed here is a relaxed replacement operator for equality, which takes into account the discrete (not continuous) distribution of the floating-point numbers over the real axis. Instead of asking "are these numbers equal?" you should ask "are they roughly equal?"

Traditionally people have used an epsilon (very small) value: if the difference between the two numbers under comparison is less than a given epsilon, then they are considered as being equal.

But Bruce Dawson proposes a different strategy: Take the 32 (o 64) bits that represent a number in the IEEE-754 format, and consider those bits as an integer number. Then simply subtract the integer representation of the two floating-point numbers. Because the IEEE-754 standard has been designed intentionally so, the difference gives to you how many representable floating-point values there are between them (plus one). This difference is called ULPS (UnitS in the Last Place), and is a more convenient value than the usual epsilon to measure the proximity of two floating-point numbers.

Caution: When subtracting the integer values, special care have to be taken with the bit patterns representing special numbers (subnormals, zeroes, infinites, NANs). Details are in the article by Bruce Dawson.

For instance, with 32 bits the integer value derived for the bits that represent the floating-point number 2.00000000 is 1073741824. The greater consecutive representable floating-point numbers are: 2.00000024, 2.00000048,... which have respectively the integer values 1073741825, 1073741826,... (Later in the article by Bruce Dawson, you can see that it is more convenient to take the twos-complement integer value, rather than the simple signed magnitude)

Bruce Dawson suggest a function named ALMOST_EQUAL(a, b, n) defined as follows:

Being "a" and "b" two floating-point numbers of the same precision in the IEEE-754 format, and being "n" an integer value greater or equal than zero, then, ALMOST_EQUAL(a, b, n) returns true if and only if, the absolute value of the difference between the integers numbers derived for the interpretation of the bits stored in "a" and "b" as integer values, is less or equal than "n".

Another way to define the function is that between "a" and "b" there are no more than "n-1" representable floating-point numbers, excluding "a" and "b"; if "n" is zero then "a" and "b" have to be exactly the same number in order to the function to return true.

Therefore, when you specify n=1, you want to test if "a" is exactly equal to "b" or if "a" and "b" are two consecutive representable values; the order between "a" and "b" does not matter.

"n" is the looseness or laxity of the comparison, that you are willing to accept in order to consider as equals two numbers. As "n" increase, the less strict you are.

As an aside, this laxed equal operator is commutative, but not transitive: "ALMOST_EQUAL(x, y, n) AND ALMOST_EQUAL(y, z, n)" does not imply ALMOST_EQUAL(x, z, n); but it implies ALMOST_EQUAL(x, z, (n+n)).

Example: The 32 bits floating-point numbers 2.00000000 and 2.00000048 are separated by only one another floating-point number: 2.00000024. So the difference between their integer values are 2. Therefore:
   ALMOST_EQUAL(2.00000000, 2.00000048, 0) is false
   ALMOST_EQUAL(2.00000000, 2.00000048, 1) is false
   ALMOST_EQUAL(2.00000000, 2.00000048, 2) is true
   ALMOST_EQUAL(2.00000000, 2.00000048, 3) is true

Instead of ALMOST_EQUAL, I find easier to understand a function named DISTANCE such that:
   DISTANCE(a, b) <= n  <==>  ALMOST_EQUAL(a, b, n) = true

This function DISTANCE(a,b) may be provided by the compiler or by an utility module, and may be useful sometimes when you want to test if two floating-point numbers are "the same", meaning this that the two numbers are close "enough" to each other. When you use this function, you are trying to compensate the roundoffs of the floating-point arithmetic.


Summarizing:

1.- If you are dealing with exact monetary quantities (what of them are not?), it would be desirable to have the data type DECIMAL(p,s) with decimal fixed-point arithmetic.

2.- If the quantities you are working with, come from inherent inexact sources such as sensors, then, fine, work with floating-point numbers. But be very aware of the territory you are walking over. Floating-point representation is "as is". In particular, do not expect that a fractional decimal number (a constant in your program, or a value from the user input or from the database) will be exactly translated into binary; most of the time it will not; instead it will be replaced by the nearest floating-point number available under the representation system used by the machine. In order to compare for equality two floating-point numbers, somebody could find useful a function named DISTANCE(a, b).
« Last Edit: March 02, 2010, 03:49:23 PM by manumart1 » Logged
Bernhard T.
Administrator
Full Member
*****
Posts: 164


« Reply #4 on: March 01, 2010, 03:31:52 PM »

just to let you know: You can teach BlackBox to trap on (integer) overflow, see the enclosed Docu (compiled and posted to the BlackBox mailing list in 2006 by Gerard Meunier):

Compiler Options

In DevCompiler:

checks          (0):   Enable index range checks and type guard checks (inxchk, typchk & ptrinit in DevCPC486) (default).
allchecks       (1):   Enable overflow checks and range checks (ovflchk & ranchk in DevCPC486).
assert        (2):   Execute ASSERT instructions (assert in DevCPV486) (default).
obj               (3):   Enable code output (outObj in DevCPE) (default except in interface modules).
ref             (4):   Record references to variables (outRef in DevCPE) (default).
allref          (5):   Record more references, about RECORDs & static ARRAYs (outAllRef & outURef in DevCPE) (default).
srcpos       (6):   Record positions in source (outSrc in DevCPE) (default).
hint           (29): Insert additional error marks (warnings) in source text (hint in DevCompiler.Module & hints in DevCPC486).
oberon      (30): Compatibility with Oberon, relative to the use of IN and OUT (oberon in DevCPM.options).
errorTrap   (31): Makes the compiler trap (HALT(100)) if an error in the source is detected (trap in DevCPM.options).

DevCompiler.CompileOpt(opt: ARRAY OF CHAR) compiles the focus text with the options modified along opt.

The chararacters in opt enable or disable different options:

first '-'       excludes srcpos.
second '-'   excludes allref.
third '-'       excludes ref.
fourth '-'     excludes obj.
first '!'        excludes assert.
second '!'    excludes checks.
'+'             includes allchecks.
'?'              includes hint.
'@'            includes errorTrap.
'$'             includes oberon.

When compiling a module list (CompileModuleList or CompileThis), it's possible to add the same characters
just after any module name (with no space between), to apply the corresponding options to its compilation.

regards
     Bernhard

PS: I am sure you can change DevCompiler to switch all checks on by default ...

PS2: The non-associativity of floating point arithmetic is nothing really new and already noted in Knuth's
excellent Volume II, Chapter 4 of The Art of Computer Programming which was originally published in 1969
(2nd Ed. 1981, 3rd Ed. 1997).

PS3: If you really want someting like DECIMAL(10,2) could use the Type Integers.Integer on your Cents and
ask for  Dollars/Euros by dividing by 100. The problem is that you loose the operators, but you could port
module Integers back to Oberon. Here we are back to the ETH-Oberon, which allows for operator overloading
and self defined operators in its current version (contrary to Component Pascal & BlackBox).
« Last Edit: March 01, 2010, 11:36:22 PM by Bernhard T. » Logged
manumart1
Newbie
*
Posts: 7


« Reply #5 on: April 17, 2010, 08:54:28 AM »

At the article "Good Ideas, Through the Looking Glass" by Niklaus Wirth (http://www.inf.ethz.ch/personal/wirth/Articles/GoodIdeas_origFig.pdf) one can read the following:

Quote

3.1. Representation of Numbers

(..) Virtually all early computers (..) featured base 10, that is, a representation by decimal digits, just as everybody was used to and had learnt in school.

(..) a decimal digit requires 4 bits (..) Yet, the decimal representation was retained for a long time, and even persists today in the form of library modules.

The reason is that people insisted in believing that all computations must be accurate. However, errors occur through rounding, for example after division. The effects of rounding may differ depending of the number representation, and a binary computer may yield different results than a decimal computer. Because traditionally financial transaction -- and that is where accuracy matters! -- were computed by hand with decimal arthmetic, it was felt that computers should produce the same results in all cases, in other words, commit the same errors.

Although the binary form will in general yield more accurate results, the decimal form remained the preferred form in financial applications, as a decimal result can easily be hand-checked if required. Although perhaps understandable, this was clearly a conservative idea.


These words are very instructive.

Perhaps there is nothing really wrong with saying that 7.19 + 1.18 = 8.370000000000001; you can always round off to two fractional decimal digits. Although the first time I was faced with this I felt repugnance, it is only due to an human prejudice caused by the fact that we have ten fingers in our hands.  Smiley
« Last Edit: April 17, 2010, 09:00:36 AM by manumart1 » Logged
manumart1
Newbie
*
Posts: 7


« Reply #6 on: August 03, 2010, 02:13:58 PM »

In a previous post I said:
Quote
(..) it surprises me a lot that if I have an INTEGER variable holding a positive value, and if I only sum positive quantities to it, then when the maximum allowable value has been passed over, that variable gets a negative value assigned to it, and the program continues happily without abending its execution. I would rather expect a runtime error
(..) From my point of view this is a grave error, because the abstraction "INTEGER" offered by the language has been broken silently at runtime
(..) To say that it is the responsibility of the programmer to insure that the result of a computation will not produce a value beyond the data type, is like to say that it is his responsibility to insure that working with an array he will never use an index position out of its bounds. The language C does not make array bound checking, and it has been worthly critized because of this.


At ["Embedded Systems and Real-Time Programming" Niklaus Wirth, 2001, LNCS 2211, pp.486-492] I have read something related to this:
Quote
(page 492) In our programming pligth, we rightly expect to receive support from programming languages and their compilers. But even at run-time we are used to rely on checks detecting mistakes such as indices out of array bounds, arithmetic overflow, and other rare cases. When relying on such implicit checks, we are in a state of sin, because they detect mistakes that should have been avoided a priori by a proper design.

Proper design; that is the key.

According to this, an integer overflow produced at run-time is due to careless programming, and a careful thinking would avoid it. Before running our program we must read it very carefully from beginning to end, and fully understand it in advance.

As Niklaus Wirth have stated somewhere else, a program text is an abstract, mathematical artefact, and we should be able to reason with it in its own terms; that is, using only the theory and the abstractions, the artificial world that the language provides to us. In that reasoning, we should avoid thinking about the implementation of the language in a given platform.


At ["The Essence of Programming Languages" Niklaus Wirth, 2003, LNCS 2789, pp.1-11] I found another paragraph related to this:
Quote
(page 5) Seldom can abstractions be implemented without impurity. It cannot be if infinity is involved, as in the case of numbers. Then a proper implementation guarantees that any computation transgressing the rules of the abstraction is notified or terminated. If, for example, an addition yields a sum outside the representable range, i.e. causes an overflow, then the program is aborted. The same holds for accessing an array with an index outside the declared bounds. These are assumed to be exceptional cases, occurring rarely, and their observation must not slow down a normal computation.


Good holidays
Logged
manumart1
Newbie
*
Posts: 7


« Reply #7 on: October 01, 2010, 04:13:23 PM »

Quote
(..) it surprises me a lot that if I have an INTEGER variable holding a positive value, and if I only sum positive quantities to it, then when the maximum allowable value has been passed over, that variable gets a negative value assigned to it, and the program continues happily without abending its execution. I would rather expect a runtime error (..)

I don't like that fact, but one can take advantage of it and write easily a function to get an integer hashcode from a string:

Code:
PROCEDURE HashCode (s: ARRAY OF CHAR): INTEGER;
VAR k, indexLastChar, hc: INTEGER;
BEGIN
indexLastChar := LEN(s$) - 1;
hc := 0; FOR k := 0 TO indexLastChar DO hc := 31 * hc + ORD(s[k]) END;
RETURN hc
END HashCode;

If the string is long enough, the sum operations will cause overflows, but they will be undetected and the computation will not stop notifying the arithmetic errors produced. But well... don't worry, be happy. You just wanted to get an integer value deterministically derived from the string.

This is exactly the way the hashCode method of the Java String class works:
Quote
public int hashCode()
   Returns a hash code for this string. The hash code for a String object is computed as
      s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
   using int arithmetic, where s[k] is the k-th character of the string, n is the length of the string, and ^ indicates exponentiation. (The hash value of the empty string is zero.)

Regards
« Last Edit: October 01, 2010, 04:17:39 PM by manumart1 » Logged
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines Valid XHTML 1.0! Valid CSS!