Core Library: Heron's Formula

Heron's Formula for Area of a Triangle

Introduction
Program and Output Files
Results from Core
Results from Maple

INTRODUCTION

Heron's formula for the area of a triangle with side lengths of a, b and c is given by

	A = sqrt( s(s-a)(s-b)(s-c) )

where s = (a+b+c)/2. This formula, when implemented in a straightforward manner in machine arithmetic, is inaccurate for ``needle like triangles''. An extensive discussion of this issue is found in Kahan's paper ``Miscalculating Area and Angles of a Needle-like Triangle'', July 19, 1999 (work in progress). This paper is available from http://www.cs.berkeley.edu/~wkahan/Triangle.pdf. Kahan gave a prescription for how to compute the area A accurately using machine arithmetic. The following table is an excerpt from Kahan's paper. There are 12 input instances. The last 2 columns are the corresponding areas computed with machine arithmetic using a "Naive" and a "Kahan's" implementation, respectively.

======================================================================================
No  	a 		b		c 		Naive 		Kahan's	
======================================================================================
1 	10  		10  		10 		43.30127019 	43.30127020 
--------------------------------------------------------------------------------------
2 	-3		5  		2  		2.905		Error 
--------------------------------------------------------------------------------------
3	100000		99999.99979 	0.00029 	17.6		9.999999990
--------------------------------------------------------------------------------------
4	100000		100000		1.00005		50010.0		50002.50003 
--------------------------------------------------------------------------------------
5	99999.99996	99999.99994	0.00003		Error		1.118033988 
--------------------------------------------------------------------------------------
6	99999.99996	0.00003		99999.99994	Error		1.118033988 
--------------------------------------------------------------------------------------
7	10000		5000.000001	15000		0		612.3724358 
--------------------------------------------------------------------------------------
8	99999.99999	99999.99999	200000		0		Error 
--------------------------------------------------------------------------------------
9	5278.64055	94721.35941	99999.99996	Error		0 
--------------------------------------------------------------------------------------
10	100002		100002		200004		0		0 
--------------------------------------------------------------------------------------
11	31622.77662	0.000023	31622.77661	0.447		0.327490458 
--------------------------------------------------------------------------------------
12	31622.77662	0.0155555	31622.77661	246.18		245.9540000 
--------------------------------------------------------------------------------------

PROGRAM AND OUTPUT FILES:

heron.cc:
a CORE program to compute each of Kahan's input instances to any specified precision. The point of this example is to show that any programmer can write robust (even guaranteed precision) code using our library, and in the most straightforward manner. This is a general property of our library. If this program is compiled as ``heron'' (see Makefile) then you can invoke it in any one of the following three alternative ways
```
	% heron
	% heron 54
	% heron 54 11
	
```
to compute the areas of the 12 sample triangles to 54 bits of guaranteed precision, and to print each value with up to 11 digits (counting decimal point). Of course, you can substitute your own values for 54 and 11.

heron.m:
Maple implementation of the same program.

Core Output
with "heron 54 11"

Core Output
with "heron 100 11"

Core Output
with "heron 100 30"

Core Output
with "heron 200 30"

RESULTS FROM CORE:

Core's number substantially agrees with Kahan's number, except for test4. Also, the last bit of Kahan's result are off by one in case of test1, test3 and test7.

Core Library Version 1.2.2
------------------- Problem 1 --------------------------
(a,b,c) = (10, 10, 10)
   Kahan's Area = 43.30127020
   Core's Area  = 43.30127019
------------------- Problem 2 --------------------------
(a,b,c) = (-3, 5, 2)
   Kahan's Area = Error
   Core's Area  = Error
------------------- Problem 3 --------------------------
(a,b,c) = (100000, 99999.99979, 0.00029)
   Kahan's Area = 9.999999990
   Core's Area  = 9.999999989
------------------- Problem 4 --------------------------
(a,b,c) = (100000, 100000, 1.00005)
   Kahan's Area = 50002.50003
   Core's Area  = 50002.50000
------------------- Problem 5 --------------------------
(a,b,c) = (99999.99996, 99999.99994, 0.00003)
   Kahan's Area = 1.118033988
   Core's Area  = 1.118033988
------------------- Problem 6 --------------------------
(a,b,c) = (99999.99996, 0.00003, 99999.99994)
   Kahan's Area = 1.118033988
   Core's Area  = 1.118033988
------------------- Problem 7 --------------------------
(a,b,c) = (10000, 5000.000001, 15000)
   Kahan's Area = 612.3724358
   Core's Area  = 612.3724357
------------------- Problem 8 --------------------------
(a,b,c) = (99999.99999, 99999.99999, 200000)
   Kahan's Area = Error
   Core's Area  = Error
------------------- Problem 9 --------------------------
(a,b,c) = (5278.64055, 94721.35941, 99999.99996)
   Kahan's Area = 0
   Core's Area  = 0
------------------- Problem 10 --------------------------
(a,b,c) = (100002, 100002, 200004)
   Kahan's Area = 0
   Core's Area  = 0
------------------- Problem 11 --------------------------
(a,b,c) = (31622.77662, 0.000023, 31622.77661)
   Kahan's Area = 0.327490458
   Core's Area  = 0.327490458
------------------- Problem 12 --------------------------
(a,b,c) = (31622.77662, 0.0155555, 31622.77661)
   Kahan's Area = 245.9540000
   Core's Area  = 245.9540000
---------------------------------------------------------

RESULTS FROM MAPLE:

We implemented the naive program in Maple (file heron.m above). When Maple precision is set to 13 digits ("Digits := 13;"), then Maple agrees with Kahan's numbers except for test4. In this case, Maple's answer is 50002.499999, not 50002.50003. Basically, CORE and Maple are in agreement. Here are the results from Maple:

---------------------------------------------------------
maple>testall(13);
=========== Problem 1 =========
 (a,b,c) = (10.000000, 10.000000, 10.000000)
 Kahan's area = 43.301270
 Maple's area = 43.301270
=========== Problem 2 =========
 (a,b,c) = (-3.000000, 5.000000, 2.000000)
 Kahan's area = ERROR
 Maple's area = ERROR
=========== Problem 3 =========
 (a,b,c) = (100000.000000, 99999.999790, .000290)
 Kahan's area = 10.000000
 Maple's area = 10.000000
=========== Problem 4 =========
 (a,b,c) = (100000.000000, 100000.000000, 1.000050)
 Kahan's area = 50002.500030
 Maple's area = 50002.499999
=========== Problem 5 =========
 (a,b,c) = (99999.999960, 99999.999940, .000030)
 Kahan's area = 1.118034
 Maple's area = 1.118034
=========== Problem 6 =========
 (a,b,c) = (99999.999960, .000030, 99999.999940)
 Kahan's area = 1.118034
 Maple's area = 1.118034
=========== Problem 7 =========
 (a,b,c) = (10000.000000, 5000.000001, 15000.000000)
 Kahan's area = 612.372436
 Maple's area = 612.372436
=========== Problem 8 =========
 (a,b,c) = (99999.999990, 99999.999990, 200000.000000)
 Kahan's area = ERROR
 Maple's area = ERROR
=========== Problem 9 =========
 (a,b,c) = (5278.640550, 94721.359410, 99999.999960)
 Kahan's area = 0.000000
 Maple's area = 0.000000
=========== Problem 10 =========
 (a,b,c) = (100002.000000, 100002.000000, 200004.000000)
 Kahan's area = 0.000000
 Maple's area = 0.000000
=========== Problem 11 =========
 (a,b,c) = (31622.776620, .000023, 31622.776610)
 Kahan's area = .327490
 Maple's area = .327490
=========== Problem 12 =========
 (a,b,c) = (31622.776620, .015556, 31622.776610)
 Kahan's area = 245.954000
 Maple's area = 245.954000
---------------------------------------------------------

Note: Maple rounds the numbers for Kahan's results (thus in problem 3, Kahan's 9.999999990 is output as 10.000000).
Postscript: Kahan has confirmed that his original answer for Problem 4 was published incorrectly, and affirmed CORE's answer

Heron's Formula for Area of a Triangle

CONTENTS

INTRODUCTION

PROGRAM AND OUTPUT FILES:

RESULTS FROM CORE:

RESULTS FROM MAPLE: