Core Library: Heron's Formula

Heron's Formula for Area of a Triangle

CONTENTS


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:

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