Ne znam sad koliko često se na kraju tih proračuna traži kvadratni koren od nekih ranije sračunatih zbirova, ali bih dodao par teorijskih razmišljanja o problemu kvadratnog korena.
Prvo treba videti da li se radi o korenu celobrojnih vrednosti (integer) ili onih u pokretnom zarezu (floating-point).
Celobrojni:
-što duže raditi u integer aritmetici, te tek na kraju preći u floating-point. To je jednostavno sa integerima. Pogleda se pozicija prve jedinice. Recimo da je to 11. To znači da se radi o celom broju između 1024 i 2047, zato što to može biti broj između 1 00000 00000 (=1024) i 1 11111 11111 (=2047). Zamislimo da je to broj 1500. Njegov koren je 38,7298... Ideja ovog mog postupka je da celobrojnom aritmetikom dođemo do najbližeg celog broja traženog korena (u ovom slučaju je to 38) i da tad pređemo u floating-point, što je i normalno jer ne možemo tako lako da decimale računamo sa integer aritmetikom. Kako doći do 38? Prvo da kažem, da je ovo moja ideja, nisam kopao po člancima, jer smatram da postojeća rešenja mogu da ograniče način razmišljanja. Takođe sam siguran da postoje bolja rešenja od ovog mog, jer da ne postoje, bio bih iskreno razočaran. Tako da ovaj moj post možete više shvatiti kao jednu matematičku vežbu moždanih vijuga, više nego kao konkretnu pomoć. Dakle, kako doći brzo i lako do broja 38 koji je jedna dobra aproksimacija i dobar (najbolji) početak za neki iterativni postupak koji će nam dati tačan rezultat. To sam zamislio kao skraćeni postupak ponovljenog oduzimanja rednih neparnih brojeva. Verovatno se ne sećate (ili nikad niste sami primetili) da je zbir prvih N neparnih brojeva u stvari N na kvadrat? Primer: 1+3+5+7+9=? Neću sabirati, jer znam da je rezultat 25, jer sam sabrao prvih 5 neparnih brojeva. Ako dodamo sledeći (11) dobićemo 6 na kvadrat, zatim dodamo sledeći neparan broj (13), to je 7 na kvadrat. E sad da ne bismo od broja 1500 oduzimali 38 rednih neparnih brojeva (u 38-oj iteraciji bismo došli do reda gde piše 113-75= 56 i tu stajemo jer oduzimanjem sledećeg neparnog broja (77) prelazimo u negativu - dakle, zaključujemo 1500= 38^2 + 56), moj metod se svodi na skraćivanje broja iteracija. U binarnom zapisu broja 1500 imamo 1 kao vodeći na 11-og poziciji. Tražimo kvadratni koren iz njemu bliskog broja, a to je 1 i deset nula iza njega, što se odmah zna da je 2^5 (polovina nula, time smo u stvari korenovali broj 1024), a to je 32. Onda radimo 33. iteraciju počev od razlike 1500 - 1024= 476 -> 476 - 65= 411. Odakle nam 65? To je 33-i neparni broj (33*2 -1). Onda redom oduzimamo 67, pa 69, pa 71, pa 73, pa 75. Kao što sam rekao tu stajemo, jer oduzimanjem 77, prelazimo u negativu. Mogli smo da krenemo od početka sa oduzimanja (oduzmemo 1, pa 3, pa 5...) ali bismo tako uzalud potrošili 32 oduzimanja da bismo došli do identičnog rezultata 1500 - 32^2= 476. Korenovanjem broja 1024 (jednostavnim prepolovljavanjem broja nula u binarnom zapisu - običan šift) smo uštedeli vreme za to. Nakon toga smo oduzeli još 6 neparnih brojeva pre prelaska u negativu i došli do zaključka da nam je potrebno ukupno 38 oduzimanja, tj da je broj 1500 nešto veći od 38^2, ali je manji od 39^2. Dakle, čistom integer aritmetikom došli smo do odlične prve aproksimacije korena iz 1500, a to je 38. Sad prelazimo u floating point, jer treba da sračunamo one decimale iza 38. Ne znam koje algoritme koriste kompajleri za 8-bitne procesore, ali pošto se sećam da je za prve PC računare korišćeni Intelovi 16-bitni procesori 8086 i 8088, a da su kvadratni koren računali tako što su logartmovali broj, podelili ga sa 2, pa ga onda antilogaritmovali. Tako su dobijali nešto vrlo približno kvadratnom korenu, jer algoritmi za logaritam i antilogaritam su komplikovaniji od korektnog algoritma za kvadratni koren, koji nisu primenili. Ko je čuo za prof. Dušana Slavića, zna o čemu pričam.
Da se vratimo korenu iz 1500. Još u doba Vavilona postojao je jedan približni algoritam za proračun kvadratnog korena. Taj postupak je zapisao Heron iz Aleksandrije (onaj što je izmislio formulu za proračun površine bilo kog trougla čije dužine stranica znamo). U toj formuli se koristi kvadratni koren, pa je logično što je Heron primenio najbolji dotada metod, a on je:
- Ako tražimo koren iz x i na neki način smo došli do približnog broja y, onda ćemo novi, tačniji y dobiti po formuli y=(y+x/y)/2. Npr: tražimo koren iz 10 i došli smo do zaključka da je to nešto veće od 3, onda je nova aproksimacija =(3+10/3)/2 = 3,16666. Sledeća iteracija je (3,166666+10/3,166666)/2 = 3,16228, što je koren iz 10 sa 6 značajnih cifara, tj 5 decimala.
Primenjeno na naš slučaj, gde tražimo koren iz 1500, što je 38,7298335 imamo u floating-pointu (38+1500/38)/2= 38,736842. Ovde je greška manja od 0,2 promila! Ne odustajemo, još jednu, konobar! (38,736842 +1500/38,736842)/2 = 38,7298341. Ovde možemo da stanemo, jer već imamo 8 značajnih dekadnih cifri, što prevazilazi tačnost floating-point aritmetike i kod 24 i kod 32 bita, što su približno 5 i 7 cifri...
Šta smo imali za ručak?
- jedan šift udesno da dobijemo broj 32 (korenovanjem broja 1024)
- 6 integer oduzimanja
- 2x primenu floating-point formule samo sa sabiranjem i deljenjem...
A dobili smo koren tačan do tačnosti kompajlera...
Imao sam nameru da objasnim i korenovanje floating-point broja, ali vidim da sam preterao u dužini posta i verovatno sam podavio većinu neopreznih čitalaca, pa odustajem. Zasada. Možda se nekome ovo i svidelo i daj Bože je primeni u svojim projektima. Recimo, dosta proračuna se može uraditi u celobrojnoj ili 24-bitnoj aritmetici i onda na kraju se u 32-bitnoj primeni Heronova formula i dobije se tačnost na par dodatnih decimala...
Prvo treba videti da li se radi o korenu celobrojnih vrednosti (integer) ili onih u pokretnom zarezu (floating-point).
Celobrojni:
-što duže raditi u integer aritmetici, te tek na kraju preći u floating-point. To je jednostavno sa integerima. Pogleda se pozicija prve jedinice. Recimo da je to 11. To znači da se radi o celom broju između 1024 i 2047, zato što to može biti broj između 1 00000 00000 (=1024) i 1 11111 11111 (=2047). Zamislimo da je to broj 1500. Njegov koren je 38,7298... Ideja ovog mog postupka je da celobrojnom aritmetikom dođemo do najbližeg celog broja traženog korena (u ovom slučaju je to 38) i da tad pređemo u floating-point, što je i normalno jer ne možemo tako lako da decimale računamo sa integer aritmetikom. Kako doći do 38? Prvo da kažem, da je ovo moja ideja, nisam kopao po člancima, jer smatram da postojeća rešenja mogu da ograniče način razmišljanja. Takođe sam siguran da postoje bolja rešenja od ovog mog, jer da ne postoje, bio bih iskreno razočaran. Tako da ovaj moj post možete više shvatiti kao jednu matematičku vežbu moždanih vijuga, više nego kao konkretnu pomoć. Dakle, kako doći brzo i lako do broja 38 koji je jedna dobra aproksimacija i dobar (najbolji) početak za neki iterativni postupak koji će nam dati tačan rezultat. To sam zamislio kao skraćeni postupak ponovljenog oduzimanja rednih neparnih brojeva. Verovatno se ne sećate (ili nikad niste sami primetili) da je zbir prvih N neparnih brojeva u stvari N na kvadrat? Primer: 1+3+5+7+9=? Neću sabirati, jer znam da je rezultat 25, jer sam sabrao prvih 5 neparnih brojeva. Ako dodamo sledeći (11) dobićemo 6 na kvadrat, zatim dodamo sledeći neparan broj (13), to je 7 na kvadrat. E sad da ne bismo od broja 1500 oduzimali 38 rednih neparnih brojeva (u 38-oj iteraciji bismo došli do reda gde piše 113-75= 56 i tu stajemo jer oduzimanjem sledećeg neparnog broja (77) prelazimo u negativu - dakle, zaključujemo 1500= 38^2 + 56), moj metod se svodi na skraćivanje broja iteracija. U binarnom zapisu broja 1500 imamo 1 kao vodeći na 11-og poziciji. Tražimo kvadratni koren iz njemu bliskog broja, a to je 1 i deset nula iza njega, što se odmah zna da je 2^5 (polovina nula, time smo u stvari korenovali broj 1024), a to je 32. Onda radimo 33. iteraciju počev od razlike 1500 - 1024= 476 -> 476 - 65= 411. Odakle nam 65? To je 33-i neparni broj (33*2 -1). Onda redom oduzimamo 67, pa 69, pa 71, pa 73, pa 75. Kao što sam rekao tu stajemo, jer oduzimanjem 77, prelazimo u negativu. Mogli smo da krenemo od početka sa oduzimanja (oduzmemo 1, pa 3, pa 5...) ali bismo tako uzalud potrošili 32 oduzimanja da bismo došli do identičnog rezultata 1500 - 32^2= 476. Korenovanjem broja 1024 (jednostavnim prepolovljavanjem broja nula u binarnom zapisu - običan šift) smo uštedeli vreme za to. Nakon toga smo oduzeli još 6 neparnih brojeva pre prelaska u negativu i došli do zaključka da nam je potrebno ukupno 38 oduzimanja, tj da je broj 1500 nešto veći od 38^2, ali je manji od 39^2. Dakle, čistom integer aritmetikom došli smo do odlične prve aproksimacije korena iz 1500, a to je 38. Sad prelazimo u floating point, jer treba da sračunamo one decimale iza 38. Ne znam koje algoritme koriste kompajleri za 8-bitne procesore, ali pošto se sećam da je za prve PC računare korišćeni Intelovi 16-bitni procesori 8086 i 8088, a da su kvadratni koren računali tako što su logartmovali broj, podelili ga sa 2, pa ga onda antilogaritmovali. Tako su dobijali nešto vrlo približno kvadratnom korenu, jer algoritmi za logaritam i antilogaritam su komplikovaniji od korektnog algoritma za kvadratni koren, koji nisu primenili. Ko je čuo za prof. Dušana Slavića, zna o čemu pričam.
Da se vratimo korenu iz 1500. Još u doba Vavilona postojao je jedan približni algoritam za proračun kvadratnog korena. Taj postupak je zapisao Heron iz Aleksandrije (onaj što je izmislio formulu za proračun površine bilo kog trougla čije dužine stranica znamo). U toj formuli se koristi kvadratni koren, pa je logično što je Heron primenio najbolji dotada metod, a on je:
- Ako tražimo koren iz x i na neki način smo došli do približnog broja y, onda ćemo novi, tačniji y dobiti po formuli y=(y+x/y)/2. Npr: tražimo koren iz 10 i došli smo do zaključka da je to nešto veće od 3, onda je nova aproksimacija =(3+10/3)/2 = 3,16666. Sledeća iteracija je (3,166666+10/3,166666)/2 = 3,16228, što je koren iz 10 sa 6 značajnih cifara, tj 5 decimala.
Primenjeno na naš slučaj, gde tražimo koren iz 1500, što je 38,7298335 imamo u floating-pointu (38+1500/38)/2= 38,736842. Ovde je greška manja od 0,2 promila! Ne odustajemo, još jednu, konobar! (38,736842 +1500/38,736842)/2 = 38,7298341. Ovde možemo da stanemo, jer već imamo 8 značajnih dekadnih cifri, što prevazilazi tačnost floating-point aritmetike i kod 24 i kod 32 bita, što su približno 5 i 7 cifri...
Šta smo imali za ručak?
- jedan šift udesno da dobijemo broj 32 (korenovanjem broja 1024)
- 6 integer oduzimanja
- 2x primenu floating-point formule samo sa sabiranjem i deljenjem...
A dobili smo koren tačan do tačnosti kompajlera...
Imao sam nameru da objasnim i korenovanje floating-point broja, ali vidim da sam preterao u dužini posta i verovatno sam podavio većinu neopreznih čitalaca, pa odustajem. Zasada. Možda se nekome ovo i svidelo i daj Bože je primeni u svojim projektima. Recimo, dosta proračuna se može uraditi u celobrojnoj ili 24-bitnoj aritmetici i onda na kraju se u 32-bitnoj primeni Heronova formula i dobije se tačnost na par dodatnih decimala...