10-31-2022, 12:13 PM
(10-29-2022, 07:58 PM)savan Wrote: Kako su 1947 godine napravili prvi kopijuter, ima slicno nesto vezano za korenovanje i druge matematicke operacije... https://aclanthology.org/www.mt-archive....h-1947.pdf jako zanimljiv dokument
Kao što rekoh, metod je odličan, iako je prastar. Drago mi je da se barem nekad koristio i u računarstvu, mada mi se čini da se od njega u zadnje vreme odustalo, jer su računari postali veoma brzi i niko više ne broji taktove. Glavni problem kod ove iterativne formule (uostalom kao i kod svih takvih formula) jeste početno rešenje, odnosno vrednost koju usvajamo na početku iteracija. Većina nas bi za koren iz 1500 usvojilo u svakom slučaju neki broj blizu 40, jer je 40^2=1600, što je dosta blizu tačne vrednosti. I za tu početnu vrednost (40) opet bi nam trebale 2 iteracije na nekih 6-7-8 značajnih cifara rešenja. Jedini je problem što računar, za razliku od ljudi, nije u stanju da proceni broj 40 kao dosta dobru aproksimaciju za početnu vrednost iteriranja. Zato sam ja ubacio poziciju vodeće jedinice u binarnom zapisu, što računar može lako da sračuna. Onda se broj pratećih nula prepolovi, što je gruba aproksimacija tog korena na 32. Da budemo iskreni, mogao se i 32 upotrebiti kao početna vrednost za Heronovu formulu, ali tad nam bi trebalo 3 iteracije da dođemo do praktično iste tačnosti. Od vrste mikrokontrolera, a i kompajlera zavisi da li je brže uraditi jednu iteraciju više u floating-pointu ili umesto toga 6 oduzimanja celog broja od celog broja. Meni se učinilo da primena sukcesivnog oduzimanja rednih neparnih brojeva idealno može da se uklopi u ovu priču, ali kao što rekoh, bio bih razočaran kad bi se ovaj moj metod pokazao kao najboljim dosad. A on je uostalom kombinacija 2 prastara metoda: babilonskog, kao i činjenice da zbir rednih neparnih brojeva uvek daje kvadrat ukupnog broja upotrebljenih neparnih brojeva.
Nisu napisali u Tvom citiranom članku koju vrednost su koristili kao početnu. Veliki broj autora koji su kod računara primenili Heronovu formulu, kreću od broja 1 kao početne vrednosti. Ta početna vrednost bi nas, za slučaj korena iz 1500, odvela na 7-8 iteracija, umesto 2. Da bih uštedeo tih 5-6 floating-point iteracija, uveo sam šift udesno i 6 celobrojnih oduzimanja. Ideja mi je bila da što kasnije pređem u floating-point; tako sam i stigao do 38 kao prve aproksimacije. Bolje nije moglo. Još jedna velika prednost predloženog metoda: - UVEK su nam potrebne samo 2 iteracije da se od najbližeg celobrojnog broja dođe do tačne vrednosti korena (sa tačnošću 32-bitnog zapisa broja). Ako za početnu vrednost usvojimo 1, onda nam za manje brojeve treba par iteracija, za 1500 nam treba 7-8, a za milion verovatno 15-20 iteracija. Onda bismo nakon svake iteracije morali da proveravamo (ne mi, već program) koliko imamo tačnih cifara (što se svodi na dodatni gubitak vremena), da bismo znali kad da stanemo sa iteriranjem, itd, itd.
Vrlo sličan predlog imam i za korenovanje floating-point brojeva. Pošto je on zapisan sa 1.mantisom i binarnim eksponentom, onda je broj 1500. napisan kao 1.46484375 * 2^10. I ovde se koristi Heronova formula, a početna vrednost se dobije tako što se eksponent prepolovi (dakle, umesto 10 biće 5). Tad je početna vrednost 1.46484375 * 2^5 = 46,875. Sad su nam potrebne 3 iteracije i to možemo fiksirati u programu.
U ovoj maloj misaonoj vežbi, ideja mi je bila da pokažem na neke jednostavne, a verovatno već zaboravljene tehnike, koje mogu da uštede vreme i veličinu koda, što je bitno kod malih mikrokontrolera.
Jasno je zašto sam ga predložio onim kojima je vreme bitno, jer tu možemo da fiksiramo broj iteracija na samo 2.
Inače, prvi elektronski računar sa složenijim računskim operacijama, napravio je 1936. Nemac Konrad Cuze. Dotada je Bebidž imao svoju diferencijalnu mašinu koja je samo sabirala i oduzimala; zahvaljujući diferencijalnom metodu simulirala je množenje i deljenje. Trebalo je da radi na vodenu paru. BTW, prvu mašinu koja je radila na vodenu paru napravio je Heron - (Heronova kugla). Cuzeova treća verzija računara koji je 1941. napravio u dnevnoj sobi svojih roditelja, bila je prvi potpuno automatski digitalni programibilni računar koji je stvarno radio. Uništen je 1943. u bombardovanju Berlina. Cuze je bio građevinski inženjer koji se, između ostalog, bavio i aerodinamikom; u to doba avione su projektovali mašinci i građevinci. Njegov Z3 je koristio brojevne matrice za proračun wing flutter-a. Ne znam kako se ovo prevodi na srpski, radi se o problemu aeroelastičnosti, gde pri određenim brzinama krila aviona počnu da "lepršaju", tj da osciluju. Na osnovu opisa rada, jasno je da se radi o veoma kompleksnim proračunima. Pošto procesori još nisu postojali, radio je pomoću brojnih releja, tako da mu je "clock" bio samo desetak Herca. Brojevi su mu imali zapis od 22 bita. Kasnije je ustanovljeno da je bio Tjuring-kompletan računar, iako se njih dvojica nisu poznavali. Bar ne u to doba. Sva 3 računara (Z1, Z2 i Z3) imali su floating-point aritmetiku, a Z3 je računao i kvadratni koren. Ne znam koju tehniku je primenio, ali u Minhenu u muzeju postoji replika Z3, pa možda jednog dana i saznam.
