Matematička Indukcija


…dio teksta napisanog 1996 o nekim temama iz matematike…. Cjelokupan tekst može se pogledati ovdje.

Uvodne riječi

Inspirisan skromnim iskustvom u prenošenju znanja mojim prijateljima i kolegama na fakultetu, odlučio sam da pokušam napisati ovaj tekst, u kojem sam obradio na nestandardan način neke teme iz područja matematike, koje se studiraju na prvoj godini Mašinskog fakulteta u Bihaću. Gotovo sve knjige iz matematike tako strogo obrađuju teme kao što i sama matematika to zahtjeva. Pokušao sam sebi dati malo slobode da na jedan nestandardan način potenciram i obradim neke detalje koji površno gledajući ne zahtijevaju mnogo pažnje, a temelj su u stvaranju prave slike i rasuđivanja u matematici.

Mnogi studenti dobijaju komplekse i razne male „traume“ kada ugledaju te silne teoreme, te matematičke simbole i zadatke. Koristio sam jedan, više simbolički način u rješavanju zadataka, a ne odstupajući od standarda rješavanja. Na taj način želio sam približiti i dati više hrabrosti studentima da se upuste u proučavanje te tako neophodne grane nauke i objasniti sve te strogo definisane zakone kroz jednu vrstu humora sa puno simbolike a koji u biti ostaju tamo gdje su uvijek pripadali – u matematici.

Protekli rat je učinio da mnogi studenti koji pohađaju I godinu nisu dolazili u dodir sa mnogim stvarima iz matematike, koje se obrađuju u srednjim školama. Kada jedan takav ratni srednjoškolac počinje da susreće sve te maloprije navedene stvari pada u jednu vrstu averzije prema matematici bez koje nikako ne može da napreduje. Averzija i strah od matematike u studentu živi cijelo vrijeme i jednostavno ga koči. U takvom stanju student postaje fobičan na svaku novu informaciju. On tada traži druge putove spoznaje: drži se strogih šablona uči na pamet određene teoreme i formule, jednostavno vodi jednu ogorčenu bitku s matematikom.

Prije nego što počnete čitati prve stranice ovog teksta, neka mi ne zamjere svi oni koji smatraju ovo nečim što ne pripada ovoj temi. Moj jedini cilj je u tome da ovaj djelić matematike bude lakše shvatljiv svim onima koji zbog rata to nisu dobili.

Bahrudin Hrnjica
U Bihaću, decembra 1996. godine.

Neki studenti i srednjoškolci, pri prvom susretu sa matematičkom indukcijom dobiju nekakav, nazvao bi ga »induktivni otpor« u moždanoj zavojnici. Radi smanjivanja i potpunog uklanjanja induktivnog otpora predlažem vam slijedeće.

» Zaboravite sve što ste znali, do sada, o Principu matematičke indukcije!«.

Kada ste obrisali i uklonili sve moždane vijuge glede matematičke indukcije, uvest ću vas u nju jednim drugim u biti istim putem. Prije nego što krenem u tu čudesnu i nevjerojatnu stvarnost ispičaću vam priču tko je kriv za to što nemate sna, i za sve noćne more koje dobijate od matematičke indukcije.

Sve je počelo ne tako davno, negdje blizu 20-tog stoljeća, kada je L. Peano ljetovao oko Venecije. U to doba dosta se govorilo o brojevima, posebno na gradskim trgovima i pijacama. Ali Peana, kao matematčara, nije zanimalo koliko šta košta, nego nešto sasvim drugo. On je razmišljao o tome kako sve te brojeve, koji su tako često u razgovoru i upotrebi, definiše i zasnuje na matematičkim osnovama, odnosno kako brojeve definisati pomoću jednog zatvorenog neproturječnog i konačnog skupa aksioma.

Jednog dana tako je i bilo…

Definicija 1 : Skupom Prirodnih bojeva zovemo svakim skupom N za čija ma koja dva elementa clip_image002 i clip_image004 postoji odnos da clip_image004[1] slijedi poslije clip_image002[1], i koji zadovoljavaju slijedeće aksiome.

Aksioma 1: 1 je prirodan broj.

( To je revolucionarno otkriće koje je mali korak za ljude sa trga a veliki za Peana)

Aksioma 2: Svaki prirodan broj clip_image002[2] ima svoj slijedeći broj clip_image004[2].

(Također ništa veći korak od prvog)

Aksioma 3: clip_image006. (Ili, jedan nije slijedeći broj ni za koji prirodan broj)

Aksiom 4: clip_image008. Dva prirodna broja su jednaka ako su im jednaki njihovi sljedeći brojevi.

Napomena

Ova aksioma proizašla je nakon napornog rada na njivi gdje je Peano brao tek sazrjeli limun. »I limun je žut zar ne«.

Peta Peanova aksioma-aksioma poznata je pod nazivom »Noćna mora«. Aksioma zbog koje vi ne spavate, ne jedete, aksioma koja je frustrirala najviše studenata od svih Peanovih aksioma. Njen treći naziv je u narodu poznat pod imenom AKSIOMA INDUKCIJE.

Aksioma 5: Ako neki skup M prirodnih brojeva ima svojstvo:

· 1ϵM

· ako postoji prirodan brojclip_image010, pa također i njegov clip_image012. Tada M sadrži sve prirodne brojeve tj. M je identičan sa skupom prirodnih brojeva.

Nešto nije jasno? Da to je Aksioma indukcije. Šta, buni vas to što se spominju nekakvi skupovi M i N. Pa lijepo sam vam rekao da zaboravite sve što ste znali o matematičkoj indukciji.

Zadnja Peanova aksioma definiše matematićku indukciju.

Možda vam sad ništa nije jasno, ni matematička indukcija ni peanovi aksiomi. Možda vam je jedino jasno zašto je limun žut.

Tako sve počelo ( mislim na noćne more i branje limuna)…

To je bio čovjek koji je za sve kriv tj. definisao je matematičku indukciju. Reći ću vam nešto u povjerenju: Tu priču sam i ja čuo. Meni je bilo lakše, a vama…..?

Peta Peanova aksioma ili Aksioma indukcije modificirana je u teoremu. No prije nego je izložim pročitajte slijedeći primjer.

Zamislite da ste u vinskom podrumu i morate provjeriti kvalitet u 10 000 buradi. Jedino sto vlasnik želi od vas jeste da ga trijezni izvjestite da li je vino u svim buradima istog kvaliteta u roku od 15 minuta.

Sada kada je pred vama jedan gotovo nerješiv problem, ne klonite duhom. S takvim i sličnim situacijama priskače u pomoć ‘noćna mora’, hoću reći matematička indukcija.

Način na koji bi riješili ovakav problem sastoji se u sljedećem.

Probajte prvih nekoliko buradi s vinom. Uvjerite se da je vino istog kvaliteta. Sada ‘uzmite’ nasumice izabrano bure i pretpostavite da je vino zadanog kvaliteta (možete te ga čak i probati). Tada ispitajte vino u sljedećem buretu. Ako je ocjena ista kao kod pretpostavljenog bureta, možete otići vlasniku i obavijestiti ga da ste riješili problem odnosno da je vino istog kvaliteta.

Vlasnik će vam povjerovati jer poznaje princip matematičke indukcija.

Napomena

Ni u kom slučaju nemojte popiti previše vina.«.

Ovo ne morate čitati

U matematici postoje dva načina rasuđivanja:

Deduktivno

Induktivno

Deduktivni način rasuđivanja vodi do toga da morate probati vino u svim buradima i onda tako pijani date izvještaj vlasniku o kvalitetu vina u buradima. Drugim riječima dedukcija je način rasuđivanja u matematici koji se bazira na tome da sve pojedine zaključke dobijamo iz jednog općeg zakona.

Induktivni način zaključivanja, koji smo već prezentirali u primjeru, vodi do toga da pojedinačnim zaključivanjema dolazimo do jednog općeg zaključka.

Ako se sada svo to vino i burad zamijeni sa prirodnim brojevima dobijamo: princip matematičke indukcije.

Definicija 2 : PRINCIPA MATEMATIČKE INDUKCIJE. Ako neka tvrdnja P(n), koja zavisi od prirodnog broja n, vrijedi za prvih nekoliko prirodnih brojeva, te ako iz pretpostavke, da vrijedi za neki prirodni broj n=k tvrdnja P(k) vrijedi i za n=k+1, pomenuta tvrdnja vrijedi za sve prirodne brojeve odnosno za svaki prirodan broj n.

Za početak riješi ćemo jedan primjer. Sljedeći primjer je najjednostavniji primjer koji se rješava pomoću matematičke indukcije. Doista, jednostavnijeg primjera nema. Primjer je toliko jednostavan da ga ne možemo zvati zadatak.

Primjer 1 : Potrebno je provjeriti da li:

clip_image014

vrijedi za sve prirodne brojeve.

Dokaz:

Prije samog početka vratite se na definiciju matamatičke indukcije. Nakon što ste još jednom pročitali definiciju, pročitajte je još jednom , i obratite pažnju na prvi dio rečenice. Definicija teoreme kaže da svaku trvdnju, bilo ona u obliku prmjera, ili zadatka, teoreme ili vinskog podruma – potrebno je provjerili validnost tvrdnje za prvih nekoliko prirodnih brojeva.

Uzmimo da je n=1.

Sada se dešava sljedeće (pošto je n=1):

clip_image016

vidimo da, ako izračunamo desnu stranu, dobijamo:

clip_image018.

To znači da početna tvrdnja (1) vrijedi za prvi prirodan broj, što ne povlači da vrijedi ako je n=2, u to se moramo uvjeriti.

Ako je n=2, primjer se svodi na:

clip_image020

odnosno,

clip_image022

Vidimo da je tvrdnja (1) tačna i za n=2. Sada možemo preći na drugi korak jer nema smisla provjeravati dalje pojedinačno validnost trvdnje primjera 1. Međutim, ako se radi o vinskim buradima provjerava se najmanje prvih deset.

Pošto ste savladali prvi korak predlažem da pročitate ponovo definiciju matematičke indukcije i obratite pažnju na drugi dio rečenice tj. ‘ako iz pretpostavke da vrijedi na n=k …’.

Ovo znači da moramo izabrati neki prirodan broj k, znači bilo koji. Pošto je bilo koji, to ne možemo reći da je primjerice 5, 15 ili 155. Samim tim mi se nismo ograničili na određeni.

Pretpostavimo da za bilo koji n=k vrijedi tvrdnja (1). Na matematičkom jeziku zadnja rečenica izgleda sljedeće:

clip_image024

Sada pročitajte ponovo definiciju i pažnju stavite na zadnji dio rečenice ‘tvrdnja vrijedi za n=k’. To znači da moramo dokazati da tvrdnja vrijedi za n=k iz pretpostavke (2). U stvari mi sebi nešto pretpostavimo da bi smo s tom pretpostavkom nešto dokazali. To je isto kada moramo pretpostaviti da će vino poteći iz bureta prije nego natočimo čašu, inače ne bi ni otvarali bure.

Ovo je najbitniji momenat procedure dokazivanja baziranog na matematičkoj indukciji. Treći dio najjednostavnije možemo riješiti ako se pravimo da ništa ne znamo.

Napišimo pretpostavku:

clip_image026

U pretpostavku moramo uključiti sljedeći broj broja k tj. k+1 jer to definicija zahtjeva od nas. Ako sada, pošto ništa ne znamo, imamo na umu da jednoj ekvivalentnosti (bilo ona pretpostavljena ili ne) možemo dodati isti broj sa lijeve i desne strane i da ona i tada ostaje nepromijenjena (identična), tada smo primjer dokazali. Kako?

Dakle dodajmo lijevoj i desnoj strani sljedeći broj broja k. Broj koji je dodan je boldiran. Dobijamo:

clip_image028

Sada je potrebno lijevu i desnu stranu izmanipulisati tako da, gdje je god stajao broj k, mora biti sljedeći broj k+1. Jedino u takvom slučaju zadovolji ćemo definiciju 1, odnosno onog tipa iz Italije.

Pogledajmo lijevu stranu izraza (4). Tamo je k bio na posljednjem mjestu u jednakosti (2), sada stoji k+1. Znači tu smo odradili posao. Na desnoj strani imamo:

clip_image030

Postupiti ćemo kao da se nista ne dešava i uradi ćemo sve ono što se može uraditi na tako „oskudnoj“ desnoj strani. Sabraćemo razlomak sa k+1. Imamo:

clip_image032

Izvlačenjem zajedničkog člana k+1 u brojniku dobijamo sljedeće:

clip_image034

Odnosno

clip_image036

Promatrajući desnu stranu uočavamo da, gdje je god bio broj k i k+1 sada stoje sljedeći brojevi : k+1 i k+2 (odnosno (k+1)+1). A to znači da smo iz pretpostavke dokazali da tvrdnja vrijedi za n=k+1 prirodan broj.

Po posljednji put pročitajte definiciju, a pažnju usmjerite prema zadnjoj odnosno drugoj rečenici: ‘Tvrdnja vrijedi za svaki prirodan broj’.

Ako definicija kaže tako onda budite sigurni da ste stvarno dokazali primjer 1. Ako nevjerujete u to, predlažem vam da odete na pusto ostrvo sa šleperom papira i hrane, te polahko krenite od 1. Ostatak života ćete sigurno potrošiti dokazujući tvrdnju deduktivno, a možda ćete dospjeti i do naslovnica svjetskih časopisa pod naslovom ‘Čovjek sa pustog ostrva izmišlja toplu vodu’.

Ako ste shvatili prethodni primjer predlažem vam da odete u podrum i probate vino u 11-tom buretu.

Zadatak 1 : Dokazati primjenom matematičke indukcije da:

clip_image038

vrijedi za svaki prirodan broj.

Rješenje:

Čim pogledamo zadatak primjetićemo da je lijeva strana zbir prvih n neparnih brojeva (desna strana je njihova vrijednost).

Ako je n=1 dobijamo,

clip_image040, tj. clip_image018[1]

clip_image042, tj. clip_image044

Pretpostavimo da je za n=k tvrdnja 6 tačna odnosno da je:

clip_image046

Smatrajući da su prva dva koraka razumljiva problem predstavlja korak 3, odnosno da iz pretpostavke 7, dokažemo da tvrdnja vrijedi i za n=k+1, što definicija hoće „reći“, da dokažemo da tvrdnja vrijedi i tada kada ubacimo u zbir i sljedeći neparni broj od broja 2k-1, odnosno 2k+1.Lijevoj i desnoj strani dodajemo broj 2k+1.

Možda se pitate: Zašto baš 2k+1? Zašto nije neki drugi, ljepši broj?

Pa jednostavno zato što je limu žut, tj. Pošto definicija traži od nas, da stavimo u glavnu ulogu broj k+1.

Kod postavljanja u glavnu ulogu broja k+1, morate ići na to da što jeftinije prođete s tim glumcem. Hoću reći da morate biti što ljenji glede rješavanja matematičkih zadataka.

Broj 2k+1 je sljedeći broj od broja 2k-1. Evo zašto: Kada u broj 2k-1, umjesto k stavimo sljedeći broj tj. k+1 imamo:

clip_image048

Pretpostavimo:

clip_image050

Prije nekoliko godina, vjerojatno kroz neku maglu prisjećate se 8 razreda kada vam je nastavnik govorio da je:

clip_image052

Zbog tog razloga desna strana jednakosti (8) poprima oblik:

clip_image054

Ponovo ista situacija kao i u primjeru. Gdje je god stajao broj k, sada stoji broj k+1. Zaključak se svodi na primjer:

Poprincipu matematičke indukcije naš zadatak 1 je dokazan.

Savjet

Kod bilo kojeg rješavanja ovakvih tipova zadataka uvijek kod trećeg koraka idemo na to da kada dodamoneki broj dodajemo uvijek sljedeći u nizu na lijevoj strani (na strani gdje je suma). Tada više posla sa lijevom stranom nemamo, samo je (lijevu stranu jednakosti) vučemo za sobom i sređujemo desnu stranu.

Vidjeli ste kako se neke sume dokazuju primjenom matematičke indukcije. Međutim, postoji mnogo tipova drugih zadataka koji se rješavaju ovom metodom.

Pokušaću vam objasniti kako se djeljivost nekog broja može dokazati ovom metodom (matematičkom indukcijom). Također ćemo krenuti od jednog primjera.

Primjer 2 : Dokazati da je:

clip_image056

dijeljivo sa 2 za svaki prirodan broj.

Dokaz:

Ako ste zaboravili definiciju (postupak) matematičke indukcije pročitajte je.

Provjeravamo tvrdnju za prvih nekoliko prirodnih brojeva:

Za n=1, clip_image058 , tj. 4 je dijeljivo sa 2, odnosno simbolički zapisano:

clip_image060.

Za n=2, clip_image062 , tj. 10 je dijeljivo sa 2, odnosno simbolički zapisano

clip_image064.

Vidimo da naš primjer vrijedi za prva dva prirodna broja.

Sad ćemo pretpostaviti da naša tvrdnja odnosno prosti primjer vrijedi za bilo koji broj k. Ako smo to učinili tada našu pretpostavku možemo napisati na matematičkom jeziku kao:

clip_image066, gdje je clip_image068

Za one kojim nije jasna zadnja jednakost neka ne čitaju sljedeći dio teksta.

Ako je neki prirodan boj Ž dijeljiv sa prirodnim brojem 2, tada je:

clip_image070, drugim riječima, to znači dakada podjelimo broj Ž sa brojem 2 dobijemo neki prirodni broj Č.

Ako zadnju jednakost pomnožimo sa 2 dobijamo:

clip_image072,

a što je isto kao kad smo napisali:

clip_image074

Pomoću pretpostavke (11), trebamo dokazati da je:

clip_image076

Ponovo kao i svaki put kada radimo 3 korak pravimo se da ništa ne znamo:

clip_image078

clip_image080

Ako niste shvatili zadnje jednakosti tada uzmite teku iz prvog razreda srednje škole i ponovite stepene, ako je niste naložili.

Vidimo da je izraz u zagradi isti kao i naša pretpostavka pa je dijeljiva sa 2, tj.

clip_image082

Zadnja jednakost nam daje za pravo da zaključimo kako je clip_image084 djeljivosa 2, a definicija da je primjer 2 tj. clip_image086 djeljiv sa 2 za svaki prirodan broj n.

Ako niste sigurni u ovaj dokaz postupate kao i u prethodnom primjeru br. 1.

Ovo ne morate čitati

Kada kažemo“vidimo da smo dokazali i za n=k+1“ to znači u bukvalnom smislu (razmišljanjem jednog prosječnog osnovca) da mi u stvari pretpostavku uzmemo, malo je prevrnemo, odjenemo je u odjeću, počešljamo je, kupimo joj nove cipele i od jedne pepeljuge postane princeza. Znači mi tu u stvari ništa ne dokazujemo u smislu dugotrajnih sudskih procesa, svjedočenja, advokata, porote i slično. Samo dodamo saberemo i izvučemo zajednički član i pretpostavka za čudo postane upravo ono što mi trebamo dobiti, a to je jednakost za n=k+1.

Čudno zar ne?

……..


Luigi Peano 1858-1918

yield naredba u C#


yield je ključna riječ (naredba) koja se pojavila izlaskom C# 2.0 i Visual Studio 2005. Oficijelna (MSDN) definicija kaže da je ovo ključna riječ koja upućuje informaciju kompajleru da metoda u kojoj se pojavljuje yield posjeduje dio koda za iteraciju. Kada kompajler naiđe na ovu riječ on formira klasu u koju implementira logiku i način na koji će se yield izvršavati. Ovo znači da yield nije osobina .NET Frameworka, nego čisto C# programskog jezika. U bloku za iteraciju yield se koristi zajedno sa return za vraćanje vrijednosti u objekat enumeracije. yield se može koristiti i sa break da bi se prekinula iteracija. yield koristi tzv. lazy evaluaciju, da se evaluacija odigrava u vrijeme izvršavanja ovog koda. Pogledajmo sljedeći dio koda:

static IEnumerable<int> F()
{  return 1;
   return 2; // Nikad se neće izvršiti
}

U ovom kodu imamo naredbu return jednu iza druge. Naravno druga naredba neće se nikad izvršiti, odnosno metoda F() uvijek vraća vrijednost 1. Pogledajmo gornji kod kada koristimo yield:

static IEnumerable<int> F()
{
  yield return 1;
  yield return 2; // Može biti izvršeno
}

Za razliku od prethodnog primjera, yield zajedno sa return naredbom će vratiti vrijednost 2 kada se ova metoda poziva kroz foreach petlju.

static IEnumerable<int> F()
foreach(var item in F())
 Console.WriteLine(item.ToString());

Kada izvršimo ovaj dio koda izlaz na konzoli je sljedeći:

Izlaz:
1
2

Potrebno je imati na umu određena ograničenja prilikom korištenja ove naredbe

  • Ako yield koristimo izvan bloka metoda, operatora kompajler će prijaviti grešku
  • yield se ne može koristiti unutar anonimne funkcije
  • yield ne smijemo također koristiti u bloku finally
  • yield return ne smijemo koristiti kada try posjeduje catch u bilo kojoj varijanti

Primjena yield naredbe u rješavanju problema

Sa yield naredbom vrlo elegantno možemo rješavati određene probleme pogotovi kada je potrebno da se određenom iteracijom dobije rezultat. Jedan od problema koji se vrlo jednostavno rješava je prebrojavanje prostih brojeva.

Prebrojavanje prostih brojeva

U jednom od postova implementirana je metoda za provjeravanje prostih brojeva, bez korištenja yield naredbe, kada se govorilo od ParallelFx. U narednom tekstu data je implementacija prebrojavanja prostih brojeva manji od n uz upotrebu yield naredbe.

//Prebrojavanje prostih brojeva manji od n
public static IEnumerable<int> VratiProsteBrojeve (int n)
{
  yield return 2;
  yield return 3;
  for (int i = 4; i < n; i++)
  {
   bool bprostBroj = true;
   for (int j = 2; j*j <= i; j++)
    if (i % j == 0)
     bprostBroj = false;
  if(bprostBroj)
   yield return i;
  }
static void Main(string[] args)
{
   //Prebrojavanje prostih brojeva manji od n
   foreach (var item in VratiProsteBrojeve (10))
     Console.WriteLine(item.ToString());
   //Press any key to continue...
   Console.Read();
}

Obzirom da posjedujemo metodu za prebrojavanje prostih brojeva otvaraju nam se bezbroj mogućnosti da kroz LINQ također vršimo određene upite. Npr. Želimo da izračunamo sumu prostih brojeva manjih od n. Ništa lakše:

var suma = Program. VratiProsteBrojeve (n).Sum();

Sada naš izlaz na konzolu izgleda kao na sljedećoj slici.

Ako želimo da izračunamo sumu kvadrata prostih brojeva manji od n imamo sljedeći primjer:

var sumaKvadrata = (from p in VratiProsteBrojeve (n) select p * p).Sum();

Rastavljanje na proste faktore

Svi smo učili iz matematike u Osnovnoj školi rastavljanje broja na proste faktore. U ovom primjeru ćemo vidjeti na koji način koristimo yield naredbu prilikom rješavanja problema koji zahtjevaju korištenje rekurzije. Uradimo prvo pješice jedan primjer čisto da se podsjetimo šta to znači. Npr. rastavi na proste faktore broj 10.10=2*5, jer su 2 i 5 prosti brojevi.Potrebno je sada implementirati algoritam za rastavljanje broja na proste faktore. U narednom primjeru prikazana je metoda za foktoriziranje broja:

//Rastavljanje broja n na proste faktore n=n1*n2*n3*...nn; ni-prosti brojevi
public static IEnumerable<string> Foktoriziraj(string izraz, int n)
{
   //Ako je 1 vrati izraz
   if (n == 1)
     yield return izraz;
   else
    {
     //Prolazimo sve brojeve manje od n
     for (int i = 2; i <= n; i++)
       {
         //Ako je n djeljiv sa i
         if ((n % i) == 0)
          {
            int q = n / i;
            //Zapišimo u izraz broj i
            if (!izraz.EndsWith("= ")) izraz += " * ";
               izraz += i.ToString();
            //Sada q postaje n i primjenjujemo isti postupak sve dok ne postane 1
             foreach (string podizraz in Foktoriziraj(izraz, q))
               yield return podizraz;
             yield break;
           }
        }
     }
}

Ako želimo da broj 100 rastavimo na proste faktore pozovimo gornju metodu u sljedećoj formi.

Console.WriteLine(Foktoriziraj("100 = ", 100).SingleOrDefault());

yieldoutput001

U koliko želimo rastaviti na proste faktore prvih 10 prirodnih brojeva potrebno je:

for (int i = 1; i < 10; i++ )
   Console.WriteLine(Foktoriziraj(i.ToString() + " = ", i).SingleOrDefault());

Rezultat je dan na sljedećoj slici:

yieldoutput002

Reference:

  1. www.msdn.com
  2. The C# Programming Language 3th edition, Anders Hejlsberg
  3. http://startbigthinksmall.wordpress.com/2008/06/09/behind-the-scenes-of-the-c-yield-keyword/
  4. http://www.codeproject.com/KB/cs/IEnumerableAndYield.aspx

Visual Studio 2010 i C# 4.0 IV DIO: Parallelfx i rješavanje sistema linearnih jednačina


Najznačajnija novina u VS 2010 po mom mišljenju je ParallelFx biblioteka za paralelno programiranje koja iskorištava višejezgrene procesore. O ovoj novini pisao sam na nekoliko postova:
  1. ParallelFx nova generacija konkurentnog programiranja
  2. ParallelFx II dio-PLINQ
  3. Izračunavanje broja PI i implementacija prekoParallelFx
U ovom dijelu biće prezentirana primjena ParallelFx na rješavanje sistema linearnih jednačina. Više detalja oko same biblioteke možete pronaći na gornjim linkovima.
Uvod

Jako puno inženjerskih problema pri procesu rješavanja svodimo na rješavanje sistema linearnih jednačina, koje onda rješavamo jednom od standardnih matematičkih metoda. Rješavanje sistema linearnih jednačina zahtjeva znatno procesorsko vrijeme kao i znatnu količinu memorije za pohranjivanje. Kada rješavamo sisteme sa većim brojem nepoznatih 100, 1000, 10000 i više, vrijeme izvršavanja klasičnim metodama i algoritmima se smanjivalo se kako su se procesori razvijal. Obzirom da se takt procesora više ne može povećavati, a daljnje proširenje svodi se na višejezgrene procesore, naši algoritmi za rješavanje ostali su na istom nivou. Naime, svi ti algoritmi bazirani su na sekvencijalno načinu izvršavanja koda pa višejezgreni procesori nemaju efekta u rješavanju. Pojavom više jezgrenih procesora šire su se počeli razvijati algoritmi za paralelno procesuiranje, a tako i paralelni algoritmi za rješavanje sistema jednačina kao i drugih algoritama koji zahtjevaju značajno procesorsko vrijeme. Paralelni algoritmi za rješavanje određenih inženjerskih procesa pojavili su se početkom 90-tih godina i s njima su se koristile samo velike kompanije poput NASA-e i sličnih, a koji su imali znatne materijalne i financijske resurse. U tu svrhu povezivali su se hiljade procesora koji su onda paralelno izvršavali dijelove koda, a na kraju su se sublimirali i davali rješenja. Tada još nisu bili poznati višejezgreni procesori poput današnjih pa su se procesori povezivali klasično gdje su zauzimali znatno prostora.

servers

Slika 1. 1000-Pentium Beowulf-Style Cluster Computer (www.genetic-programming.org/)

Npr. John Koza tvorac genetskog programiranja, povezao je 1000 procesora gdje je vršio svoja ispitivanja i proračune sa paralelnim algoritmom genetskog programiranja (O genetskom programiranju već sam pisao ). Pojavom višejezgrenih procesora paralelno programiranje postalo je dostupno i običnim „smrtnicima“ a samim tim i šira upotreba paralelnog načina programiranja.

Gaussova metoda eliminacije

Jedna od najpopularnijih metoda rješavanja sistema linearnih jednačina je Gaussova metoda koja koristi princip eliminacije kojom se u konačnom broju iteracija na kraju dobija jedno rješenje, od kojeg se u povratnom smjeru dolazi do drugih rješenja. Linearni sistema od clip_image006 jednačina sa clip_image006[1] nepoznatih clip_image008 je skup jednačina clip_image010 slijedeće matrične forme:

clip_image012

clip_image014

clip_image016

Gdje su clip_image018i clip_image020 realni brojevi članovi matrice. Sistem zovemo homogenim ako su svi članovi matrice kolone slobodnih članova clip_image020[1] jednaki nuli; inače sistema zovemo nehomogeni. Korištenjem matrica i njihovih operacija, jednačine clip_image010[1] možemo posmatrati kao matrični jednačinu:

clip_image022

Gdje je matrica clip_image024 clip_image026 matrica

clip_image028,

dok su matrice kolona nepoznatih označavamo sa clip_image030 , a matricu kolona slobodnih članova označavamo sa clip_image032. Formalni zapisi ovih matrica dati su sljedećim izrazima respektivno:

clip_image034 ,

clip_image036.

Proširena matrica sistema clip_image038 je matrica reda clip_image040 koju definišemo kao:

clip_image042

Rješenje sistema linearnih jednačina je skup brojeva clip_image044 koji zadovoljavaju svih clip_image006[2] jednačina, a vektor rješenja sistema linearnih jednačina clip_image046 je vektor koji zadovoljava matričnu jednačinu. Način na koji se rješavaju sistemi linearnih jednačina Gaussovim sistemom eliminacije možete pogledati iz referenci koje su stavljene na kraju ovog članka. Da bi implementirali algoritma za rješavanje sistema linearnih jednačina potrebno je poznavati ovu metodu, te imati na umu procesorsko vrijeme i memoriju koju će algoritam zauzimati.

Algoritam Gausove metode eliminacije

Način na koji rješavamo sisteme jednačina „pješice“ najbolji je način kako da započnemo implementaciju algoritma. Za informaciju, na internetu postoje hiljade stranica na kojima se mogu naći algoritmi za rješavanje sistema linearnih jednačina u raznim programskim jezicima. S toga ova implementacija koja je data nije ništa revolucionarno.

Algoritam Gauss clip_image048 – proširena matrica sistema

ULAZ : Proširena matrica sistema koja definiše clip_image050 članova clip_image052, gdje je clip_image054, a clip_image056– predstavlja broj nepoznati. 1.

Nakon učitavanja matrice sistema potrebno je izvršiti triangulaciju matrice, gdje je po definiciji zadnjih član takve matrice rješenje clip_image058. 2. Obrnutim postupkom uz poznavanje rješenja clip_image058[1] dolazimo do rješenje clip_image060, i tako do rješenja clip_image062

IZLAZ : Vektor rješenja  clip_image064.gif. Izvorni kod ovog algoritma dat je u nastavku:

//Gaussova metoda eliminacije
for (int k = 0; k <= brKol - 2; k++)
 {
  // Prvo potrazimo najveci koeficijent u kolonama kao Pivot, zbog preciznosti rezultata
  double pivot = matSistema[k][k];
  for (int i = k + 1; i <= brVrsta - 1; i++)
   {
    if (pivot < Math.Abs(matSistema[i][k]))
    {
      double[] temp = matSistema[k];
      matSistema[k] = matSistema[i];
      matSistema[i] = temp;
    }
  }
 // Triangulacija
 for (int j = k + 1; j <= brVrsta - 1; j++)
  {
    m[j][k] = matSistema[j][k] / matSistema[k][k];
    for (int p = k; p <= brKol - 1; p++)
    {
      matSistema[j][p] = matSistema[j][p] - m[j][k] * matSistema[k][p];
    }
  }
 }
//
double[] rjesenje = new double[brKol - 1];
rjesenje[brKol - 2] = matSistema[brVrsta - 1][brKol - 1] / matSistema[brVrsta - 1][brKol - 2];
 for (int i = brVrsta - 2; i >= 0; i--)
 {
   double sum = 0.0;
   for (int j = brKol - 2; j >= i + 1; j--)
    {
      sum = sum + matSistema[i][j] * rjesenje[j];
    }
   rjesenje[i] = (1 / matSistema[i][i]) * (matSistema[i][brKol - 1] - sum);
 }
return rjesenje;

Kada smo implementirali algoritam za rješavanje sistema linearnih jednačina potrebno je sada analizirati kod i vidjeti gdje bi se mogla izvršiti paralelizacija da bi naš algoritam bio brzi od konvencionalnog odnosno da bi mogao iskorištavati današnja višejezgrene procesore. Prije nego se upustimo u analizu koda potrebno je pretpostaviti da će naš algoritam rješavati više od 500 jednačina odnosno tražiti više od 500 nepoznati. Ako bi algoritam rješavao manje jednačina paralelizacija ne bi imala smisla jer se vrijeme izvršavanja sekvencijalnog koda bilo brže od paralelnog. Ako pogledamo gornju implementaciju mjesta gdje bi paralelizirali kod je samo na dijelovima pri triangulaciji matrice i izračunavanju rješenja. Na ova dva mjesta imamo ugnježdene petlje, a one u algoritmu troše najviše procesorskog vremena.

Kako algoritam počinje…

On uzima prvu kolonu i provjerava da li u danoj koloni prvi član po apsolutnoj vrijednosti je najveći član od svih desnih kolona. Ako to slučaj nije tada se traži kolona u kojoj je prvi član najveći i te dvije kolone zamjenjuju mjesta. To možemo slobodno uraditi zbog osobina matrica. Kada se normalizira kolona tada se vrši triangulacija odnosno za svaku vrstu ispod posmatrane elementi kolone moraju biti nule (Gaussov postupak eliminacije). U ovom koraku se koriste dvije ugnježdene petlje (crveno obojen kod) kojim se ovo ostvaruje. Ovaj dio kod je najpogodniji za paralelnu implementaciju. Razlog zašto se ne ide na paralelnu implementacije prve petlje je taj što se mora ispoštovati poredak kolona, a u paralelnoj implementaciji to ne možemo postići jednostavno. Drugi dio koda pri kojem se na osnovu triangulacije matrice izračunavaju rješenja također koristi dvije ugnježdene petlje, a samim tim i dio koda koji bi mogao biti kandidat za paralelnu implementaciju. Ovaj dio koda također se mora izvršavati u striktno definisanom redu tj. prvo se izračunava zadnja vrsta, pa predzadnja i td. do prve vrste. Kada bi ovaj dio koda bio implementiran paralelno narušili bi poredak, a tako i rješenja ne bi bila izračunata tačno. Na osnovu analize paralelna implementacija kod izgleda na sljedeći način:

//Gaussova metoda eliminacije
for (int k = 0; k <= brKol - 2; k++)
{
  // Prvo potrazimo najveci koeficijent u kolonama kao Pivot, zbog preciznosti rezultata
  double pivot = matSistema[k][k];
  for (int i = k + 1; i <= brVrsta - 1; i++)
  {
    if (pivot < Math.Abs(matSistema[i][k]))
     {   double[] temp = matSistema[k];
       matSistema[k] = matSistema[i];
       matSistema[i] = temp;
     }
  }
 // Triangulacija
 Parallel.For(k + 1, brVrsta, j =>
 {
   m[j][k] = matSistema[j][k] / matSistema[k][k];
   for (int p = k; p <= brKol - 1; p++)
   {
     matSistema[j][p] = matSistema[j][p] - m[j][k] * matSistema[k][p];
   }
 }
             );
}
//
double[] rjesenje = new double[brKol - 1];
rjesenje[brKol - 2] = matSistema[brVrsta - 1][brKol - 1] / matSistema[brVrsta - 1][brKol - 2];
for (int i = brVrsta - 2; i >= 0; i--)
 {
   double sum = 0.0;
   for (int j = brKol - 2; j >= i + 1; j--)
    {
      sum = sum + matSistema[i][j] * rjesenje[j];
    }
   rjesenje[i] = (1 / matSistema[i][i]) * (matSistema[i][brKol - 1] - sum);
 }
 return rjesenje;

Vidimo da paralelna verzija algoritma se nije puno promijenila a što Parallelfx čini vrlo efikasnom bibliotekom.

Testiranje sekvencijalnog i paralelnog algoritma

Sada kada smo implementirali algoritam potrebno ga je i testirati na višejezgrenim PC mašinama da bi smo se uvjerili da naš paralelni algoritam brže radi od sekvencijalog. U tu svrhu generirano je 5 csv datoteka u kojim stoje proširene matrice sistema od 10, 50, 100, 500 i 1000 nepoznatih, kojim ćemo izvršiti testiranje algoritma. Sistemi su jednostavni čija su rješenja sve jedinice. Test aplikacija je koncipirana tako da učitava sisteme jednačina iz csv datoteka rješava sisteme koristeći sekvencijalni i paralelni algoritam te na konzolu izbacuje vremena koja su potrošena pri rješavanju. Test koji je prezentiran ovdje rađen je na Intel Core 2 Quad CPU Q6600 2,4 GZ:

CoreQuad

Rezultat testa je sljedeći:

restest

Iz testa možemo primijetiti da sistemi preko 100 nepoznati daju bolje rezultate kod paralelne implementacije i možemo smatrati okvirno da je to neka granica preko koje bi trebali koristiti paralelnu implementaciju algoritma. Kako broj nepoznatih raste tako raste razlika između paralelne i sekvencijalne implementacije algoritma. Kompletan izvorni kod algoritma i testa može se skinuti sa ovog linka. Projekt je rađen u Visual Studiu 2010 beta 1koji se može skinuti sa ovog linka.

Reference

  1. http://blogs.msdn.com/pfxteam/
  2. Ćamila Ljubović, Matematika, IPSvjetlost Sarajevo 1997
  3. http://geeks.netindonesia.net/blogs/norman

Remake: Broj u text sa C#


U nekom od prethodnih postova pisao sam o malom MFC demo programu u kojem sam implementirao jednostavnu klasu koja decimalni broj zapisuje slovima. Ovaj demo proizašao je iz čiste potrebe da u svojim komercijalnim aplikacijama implementiram ovo svojstvo. Na isti način pojavila se potreba da se ova klasa portuje i na .NET jezik C#. Verzija radi na bosanskom jeziku, a moguće je selekcijom na checkbox prikazati i hrvatsku veziju tekstualnog broja.

WPF aplikacija

Demo aplikacija slična je prethodnoj gdje se uz osnovna podešavanja naziva valute i 100-tog dijela iste, odabirajuću varijantu bosanskog ili hrvatskog jezika, unosom broja te aktivacijom dugmeta pojavljuje textualni prikaz. Na ovom linku možete pronaći C# primjer sa source kodom.

Izračunavanje broja PI i implementacija preko ParallelFX


Uvod

Pretražujući po arhivi staroj i više od 20 godina, slučajno sam naletio na jedan matematički časopis „Matematika – stručno metodički časopis“ Zagreb 1987 godina. Pored ostalog u časopisu se nalazi i članak o računanju broja PI pomoću računara. Pomenuti članak daje i izvornji kod u PASCAL-u za izračunavanje broja PI na 1000 decimala.

Odmah se javila ideja na koji način ovaj problem ponovno aktivirati te ga osvježiti novim tehnologijama. Prije bilo kakvog upuštanja u ovaj problem, naravno „konsultovao“ se sa Google, te potražio aktuelnosti povodom ovog problema.

Na wikipediji sam pronašao Machine-ov algoritam za računanje broja PI (dosta svjež članak 16. Feb. 2009).

Nadalje, našao sam podatak ko drži Ginisov rekord u izračunavanju broja decimala, to je japanski profesor sa 1,24 triliona cifara.

Nadalje, postoji na internetu bezbroj primjera sa source codeom izračunavanja broja PI u skoro svakom programskoj jeziku. Na kraju ovo posta biće pobrojani neki zanimljivi linkovi u vezi ovog problema.

Teorija o broju PI

PI je realan broj koji definišemo kao omjer obima i dijametra kruga . Često ovu konstantu zovu još i Archimedes-ova konstanta ili Ludolph-ov broj. Prije 13 godina otkrivena je BBP formula.

John Machine engleski naučnik prvi je razvio efikasan algoritam za izračunavanje broja PI. Osnovna vrijednost ove formule je da brže konvergira od tada dostupnih formula poput Leibnic – ove formule, i postaje vrlo praktična pri izračunavanju. Machine-ova formula za izračunavanje broja Pi data je sljedećim izrazom:

……………………(1)

Ovom formulom Machine je došao do 100 cifara broja PI. Da bi se gornja formula mogla koristiti razvija se u Taylorov red na sljedeći način:

clip_image006_asdtrwe12345 , gdje je …………………(2)

Pored osnovne formule za izračunavanje broja PI, postoji čitav niz formula koje su se kasnije razvijale a sve imaju sljedeći zapis:

, gdje su i cijeli brojevi.

Shodno gornjem zapisu definisane su Machine formule sa dva i više izraza.

Formule sa dva izraza:

…………………(3)

…………………(4)

…………………(5)

Formule sa 4 izraza:

clip-image010 …………………(6)

clip-image024 …………………(7)

Formule sa 6 i 7 izraza i koje su najefikasnije u izračunu broja PI:

clip-image026 …………………(8)

clip-image028 …………………(9)

Više informacija oovim formulama može se naći na wikipedia.

Implementacija u C#

S obzirom da želimo računati decimale broja PI veće od broja decimala standardnih typova podataka u .NET, potrebno je implementirati apstraktni tip koji će imati mogućnost prikaza broja sa više od 100 decimala odnosno cifara.

Postoji bezbroj implementacija ovakovog tipa podataka na internetu. Na CodeProject postoji C++ verzija izračunavanja broja PI na više hiljada decimala. Također, na CodeProject postoji C# članak o računanju sa velikim brojevima. U ovaj blog ne bi stale sve implementacije koje su napravljene u C, C++, PASCAL, JAVA i td o računanju broja PI, a koje se nalaze na internetu.

Implementacija koju sam odabrao za ovaj post je implementacija je od Julian-a M Bucknall Chief Technology Officer u Developer Express. Članak koji je on napisao o izračunavanju broja PI nalazi se na ovom linku. On u svom članku objašnjava implementaciju izračunavanja broja PI ,te prezentira metode osnovnih algebarskih operacija: +, -, *, /. Inače, svaka implementacija koja manipuliše sa velikim brojavima bazira se na računanju odnosno sabiranju, oduzimanju djeljenju i množenju na način kako smo to radili u osnovnoj školi, ili tačnije pismeno sabiranje, oduzimanje, dijeljenje i množenje.

Kada želimo dva broja sabrati, tada činimo na sljedeći način:

123546546
+ 25487888
_________________
149034434

Sabiranje radimo tako što krećemo od jedinica te zbrajanje potpisujemo na mjesto jedinica rezultata. Ukoliko je zbir veći od deset pišemo jedinice a desetice pamtimo i prenosimo je u sljedeće sabiranje. Na analogan način vrše se ostale algebarske operacije. Julian je u svom članku potanko opisao implementaciju koju nećemo ovdje ponavljati.

Analiza klase BigNumber

Julianova BigNumber klasa sadrži osnovne operacije, nekoliko metoda verifikacije te ArcTan metodu koja vrijednost arctg funkcije razvija u Taylorov red i izračunava svaki član pojedinačno. Ova metoda uzima argumente UInt32 multiplicand, UInt32 reciprocal, gdje se prvi argument množi sa arctg, a drugi je nazivnik broja nad kojim se vrši arctg operacija.

U primjeru koji je dao korištena ja Machinova formula (1). Analizirajući formulu (1) vidi se da drugi izraz formule znatno brže konvergira u odnosu na prvi. U testovima koje sam provodio za 50.000 decimala prvi izraz konvergira za otprilike 17 sekundi dok drugi izraz za oko 4 sekunde. Više detalja kasnije u postu.

Implementacija Paralelnog izračunavanja

1. Paralelizam kod operacija +,-,*,/

Sagledavajući klasu i analizirajući gdje bi se mogla izvršiti implementacija paralelnog izračunavanja otpala je prva varijanta da se paralelizam primjeni u metodama osnovnih operacija. Ovdje je situacija da se pri izračunavanju polazi od jedinica, kada se jedinice izračunaju prelazi se na desetice i td. Primjećujemo da se ne može vršiti paralelno izračunavanje jedinica i desetica i sl.

2. Paralelizam kod izračunavanja ArcTan metode

Druga varijanta također poslije dublje analize, nije polučila značajniju efikasnost iz razloga što se ova metoda izvršava dosta sekvencijalno. Npr. Prvo se izračuna x, zatim se u while petlji računaju članovi taylorovog reda na način da se na osnovu prethodnog dobija novi član reda. Opet i u ovom slučaju paralelizam se ne bi isplatio implementirati.

3. Paralelizam kod izračunavanja članova izraza machinove formue

Jedina mogućnost koja je ostala je ta da se izrazi u formuli (1) paraleliziraju. Ovo je moguće jer su neovisni jedan od drugog. Poslije izračunavanja izraza dolazi njihovo sublimiranje, zavisno od operacije sabiranja ili oduzimanja.

Da bi paralelizirali gornje koristićemo metodu Parallel.Invoke (stara Do metoda iz decembarskog CTP-a). Svi testovi koji su rađeni implementirani su sa Junskim CTP izdanjem ParallelFX.

Test 1: Sekvencijalna i paralelna implementacija formule (1)

Poslije implementacije pokrećemo prvi test :

1. Formula (1)

2. Broj decimala 10.000

3. PC Intel Core 2 Quad 2,4 MHz

Rezultat testa:

clip-image030

Iz prezentiranog testa vidi se da nismo puno uštedjeli vremena. S obzirom da se radi o 4 jezgre ipak ova implementacije je nezadovoljavajuća.

Obrazloženje: Parallel.Invoke metoda poziva dvije metode, odnosno paralelno se izvršavanju dvije metode, maksimalna efikasnost implementacije bila bi 100%. Međutim test je pokazao svega 20%. Razlog tome leži u činjenici da drugi izraz clip_image1006_asdtrwe12345 brže konvergira od prvog izraza. To znači da se drugi izraz završio za 0,153 sec, dok se prvi izraz izvršava ostatak vremena. Obzirom da Invoke metoda mora sačekati sve niti da se završe pa tek onda da se nastavi izvršavanje koda.

Iz ovoga zaključujemo da moramo promijeniti formulu, te uzeti formulu koja ima više izraza i u kojoj izrazi imaju približno jednaku konvergenciju. U idealnom slučaju na posmatranom PC mogli bi dobiti punu brzinu kada bi izrazi imali istu konvergenciju i kada bi broj izraza u formulu iznosio 4. Tada bi vrijeme paralelnog i sekvencijalnog izvršavanja bilo 4:1 što bi bio maximalni efekat.

Iz tog razloga potrebno je izabrati jednu od formula 6,7 ili 8. Formula 9 nije upotrebljiva jer bi bilo potrebno posebno implementirati dijeljenje velikog broja sa velikim brojem što će možda biti predmet jednog drugog blog posta.

S druge strane konvergencije izraza u formulama 6,7 i 8 dosta brže konvergiraju u odnosu na formulu (1). Da bi dokazali konvergenciju napravimo sljedeći test:

Test 2: Sekvencijalna usporedba konvergencija Formula (1) i (7)

1. Formula (1) (7)

2. Broj decimala 10.000

3. PC Intel Core 2 Quad 2,4

4. Sekvencijalna implementacija

Rezultat testa:

clip-image034

Iz testa se vidi da formula (7) brze konvergira od formule (1). Mijenjanjem formule bez paralelizma smo obezbijedili brze izvršavanje za oko 15 %.

Test 3 Paralelna implementacije formule (7)

1. Formula (7)

2. Broj decimala 10.000

3. PC Intel Core 2 Quad 2,4

Rezultat testa:

clip-image034

Primjenom formule 7 na 10.000 decimala efikasnost se popela na 100%.

Test na 100.000 decimala rezultat je pokazao sljedeće:

clip-image038

Iz prethodnog testa mogli smo vidjeti da kada se broj decimala povećava, povećava se i razlika u vremenu izvršavanja. Razlika u vremenima 1. i 2. prethodnog testa je utjecaj formiranja niti kod paralelnog izvršavanja Invoke metode.

Test 4. Paralelna implementacija formule (8)

1. Formula (8)

2. Broj decimala 10.000

3. PC Intel Core 2 Quad 2,4

clip-image040

Zadnjim testom vidimo da formula 8 sporije konvergira od formule 7, kada je u pitanju sekvencijalna implementacija, dok je paralelna implementacija dosta brža. Razlog tome je što u formuli (8) postoji više od jednog izraza koji sporije konvergira u odnosu na formulu (7), a obzirom da invoke metoda optimizira sve paralelne niti i koristi „work stealing“ tj. kada se izraz sa najbržom konvergencijom izvrši nit se ne uništava nego se posuđuje izrazu koji čeka na izvršavanje.

Rezultati su čak bolji od prezentiranog kada se koristi više decimala, što ostavljam čitaocu na testiranje.

Zaključak

Ovim člankom prezentiran je način kako operacije koje zahtjevaju značajno procesorsko vrijeme implementirati i iskoristiti višejezgrene procesore, a samim tim i smanjiti vrijeme izvršavanja. Takodjer, je prikazan jedan od načina primjene ParallelFX u sekvencijalnim implementacijama. Implementacija paralelnog izvršavanja koda moguća je samo u slučajevima kada je vrijeme izvršavanja sekvencijalnog koda značajno dugo, a vrijeme potrebno za formiranje niti za paralelno izvršavanje zanemarljivo u odnosu na ukupno vrijeme. Također , pokazan je jedan od načina na koji je potrebno pristupiti problemu kada želimo primjenjivati ParallelFX. Prezentacija pokazuje da ParallelFX biblioteka ne zahtjeva značajnu izmjenu koda prilikom implementacije, što predstavlja najvažniju činjenicu prezentiranu ovim člankom. Svaki sekvencijalni kod se ne može uspješno paralelno implementirati. Faktori koji utiču su mnogobrojni, i različiti od slučaja do slučaja. S toga prije svake implementacije nužna je detaljna analiza.

Source code ovog članaka sa implementacijom svih testova koji su provedeni nalazi se ovdje.