Egy oldalaival meghatározott háromszög területének kiszámítására a Heron képletet szoktuk használni. Ez a gyakorlati alkalmazások többségében jól használható. Vannak azonban olyan esetek, amikor a Heron képlet a lebegőpontos számábrázolás korlátozott pontossága miatt nem ad helyes eredményt. Ilyen eset, amikor az úgynevezett tűszerű háromszögek (needle-like triangle) területét szeretnénk megkapni. A tűszerű háromszög olyan háromszög, amelynek két oldala sokkal hosszabb, mint a harmadik. Erre mutat példát az alábbi ábra tetején megrajzolt háromszög.
A tűszerű háromszögek területének pontosabb kiszámítására William Kahan matematikus – aki többek között a lebegőpontos számítások IEEE 754-1985 szabványának fő megalkotója volt – adott egy képletet, amelyet szintén az előbbi ábrán látható. Ehhez két kikötés tartozik. Az egyik, hogy a képlet használata előtt az oldalakat rendezni kell, hogy az „a” oldal legyen a legnagyobb és a „c” a legkisebb. A másik, hogy a négyzetgyök alatti szorzat tényezőiben a zárójelek lényegesek, azokat meg kell hagyni. Ennek oka, hogy a float típusú számok esetében az eredmény pontossága függhet a műveletvégzési sorrendtől. Erről egyszerűen meggyőződhetünk egy példával. Írassuk ki először azt, hogy print(0.1+0.2+0.3). Ennek eredménye 0.6000000000000001 lesz. Most tegyük zárójelbe a két utolsó tagot és írjuk ki így az eredményt: print(0.1+(0.2+0.3)). Ekkor az egzakt 0.6 érték jelenik meg.
A következőkben azt fogjuk vizsgálni, hogy tűszerű háromszögek esetén valóban pontosabb eredményt ad-e a Kahan képlet, mint a Heron képlet, és a pontosságbeli különbség mindig fennáll-e. Ehhez első lépésben egy-egy függvényt készítettünk az ábrán feltüntetett Heron és a Kahan képlet szerinti területszámításhoz.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
from math import sqrt def heron(a, b, c): if not (a < b + c and b < a + c and c < a + b): raise ValueError('Az a, b és c nem lehetnek egy háromszög oldalai.') s = sum((a, b, c)) / 2 return sqrt(s * (s - a) * (s - b) * (s - c)) def kahan(a, b, c): if not (a < b + c and b < a + c and c < a + b): raise ValueError('Az a, b és c nem lehetnek egy háromszög oldalai.') # Az oldalhosszak csökkenő sorrendbe rendezese. a, b, c = sorted((a, b, c), reverse=True) # A négyzetgyök alá kerülö szorzat egyes tényezöiben a zárójeleket meg kell tartani. p1, p2, p3, p4 = a + (b + c), c - (a - b), c + (a - b), a + (b - c) return 0.25 * sqrt(p1 * p2 * p3 * p4) |
A függvények által szolgáltatott eredmények pontosságának megítéléséhez a tesztekben a háromszöget nem a három oldalával, hanem az ábrán látható jelölések szerinti x, y és m szakaszokkal adjuk meg. Ebben az esetben a háromszög területét az egyszerű alap*magasság/2 képlettel tudjuk felírni, ami a közös összehasonlítási alap lesz. Másrészt a háromszög keskenységét, tűszerűségét az m értékével tudjuk egyszerűen beállítani.
A tesztprogramot alább látjuk. Ennek elve, hogy az x értékét széles határok között növeljük és megnézzük, hogy az egyes x értékekhez tartozó háromszögekre melyik képlet pontosabb. Amelyik pontosabb eredményt ad, az ahhoz tartozó esetszámláló értékét eggyel növeljük. Ha az összes háromszögre a terület ki lett számolva, akkor a végén a számlálók értéke, viszonyítva az összes vizsgált háromszög számával megadja, hogy összeségében melyik képlet bizonyult pontosabbnak.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
# TESZT # Megvizsgáljuk, hogy a különbözö oldalhosszúságű, egyre vékonyabb tűszerű háromszögek közül # relative hány eseteben ad a területre pontosabb értéket a Kahan és a Heron képlet. h = k = 0 # Azon előfordulások számlálói, ahol a Heron, illetve a Kahan képlet hibája kisebb. xr = range(100, 10_000_001, 100) for x in xr: m, y = 0.5, 10 # A háromszög oldalhosszainak meghatározása. a, b, c = x + y, sqrt(x ** 2 + m ** 2), sqrt(m ** 2 + y ** 2) # A terület egzakt Erteke. area = (x + y) * m / 2 # A terület kiszámítása a Heron és Kahan képletekkel. area_h, area_k = heron(a, b, c), kahan(a, b, c) # Azon esetek számolása, ahol a Kahan képlet eredménye pontosabb. if abs(area_h - area) > abs(area_k - area): k += 1 # Azon esetek számolása, ahol a Heron képlet eredménye pontosabb. if abs(area_h - area) < abs(area_k - area): h += 1 # Eredmények kiírása. stat_text = 'Az esetek {:.2%}-ban a {} képlet pontosabb eredményt ad.' print(stat_text.format(k / len(xr), 'Kahan')) print(stat_text.format(h / len(xr), 'Heron')) print('\nA legvékonyabb tűszerű háromszög oldalai és területszámitása:') print('a = {}, b = {}, c = {}'.format(a, b, c)) print('Egzakt terület = {}'.format(area)) print('Terület-Heron = {:<{w}}, hiba = {:.10f}'.format(area_h, abs(area_h - area), w=max(len(str(area_h)), len(str(area_k))))) print('Terület-Kahan = {:<{w}}, hiba = {:.10f}'.format(area_k, abs(area_k-area), w = max(len(str(area_h)), len(str(area_k))))) # Eredmények: # Az esetek 86.51%-ban a Kahan képlet pontosabb eredményt ad. # Az esetek 13.49%-ban a Heron képlet pontosabb eredményt ad. # # A legvékonyabb tűszerű háromszög oldalai és területszámitása: # a = 10000010, b = 10000000.000000013, c = 10.012492197250394 # Egzakt terület = 2500002.5 # Terület-Heron = 2500002.865170924 , hiba = 0.3651709240 # Terület-Kahan = 2500002.5538516925, hiba = 0.0538516925 |
A tesztadatok meglehetősen keskeny, tűszerű háromszögeket definiálnak, és a végeredményből levonhatjuk a következtetést, hogy a Kahan képlet összességében pontosabb eredményt ad. Ha kicsit tovább elemezzük az eredményeket, akkor az is megállapítható, hogy a Heron képlet a kevésbé keskeny esetekben produkál csak picit nagyobb pontosságot, de minél keskenyebb lesz a háromszög a Kahan képlet fog pontosabb területértékeket adni. A tesztünkben szereplő legkeskenyebb háromszögre számszerűen is láthatjuk az eltérést.
A float típus számábrázolási pontosságáról és vonatkozásairól a Python tudásépítés lépésről lépésre című e-könyvben a „Műveletek” fejezet „Számítási pontosság float típus esetén” című szakaszában, valamint a „Készétel fogyasztás – a szabványos könyvtár moduljainak használata” fejezet „Matematikai számítások támogatása” alfejezetben van kiemelten szó.