Mașină diferențială

Mașină diferențială expusă la Muzeul Științific de la Londra, construită după proiectul lui Babbage. Proiectul are aceeași precizie pe toate coloanele, dar când calculează polinoame convergente, precizia pe coloanele de ordin superior poate scădea. Mașina nu este o replică (nu s-a construit niciodată în timpul lui Babbage)

O mașină diferențială este un calculator automatic, mecanic, proiectat pentru tabelarea funcțiilor polinomiale. Atât funcțiile logaritmice cât și cele trigonometrice pot fi aproximate cu polinoame, deci o mașină diferențială poate calcula mai multe seturi de numere utile.

Istoric

Detaliu al mașinii diferențiale de la Muzeul Științific din Londra, pe care se văd unele roți numerice și roți dințate dintre coloane. Roțile dințate din stânga prezintă clar dinți de înălțime dublă. Roțile dințate din centru-dreapta sunt cu fața spre spatele mașinii, dar dinții de înălțime normală sunt clar vizibili. Se observă așezarea roților în oglindă și agățătoarele metalice dintre "6" și "7". Acestea din urmă duc înapoi transportul când "9" devine "0" în pașii de adunare (Pasul 1 şi Pasul 3).

A treia maşină diferenţială a lui Per Georg Scheutz

J. H. Müller, un inginer din armata hessiană, a avut ideea într-o carte publicată în 1786, dar nu a găsit finanțare pentru proiect.

În 1822, Charles Babbage a propus o astfel de mașină într-o adresă trimisă Royal Astronomical Society la 14 iunie, adresă intitulată „Notă privind aplicarea unor mașini în calculul tabelelor astronomice și matematice”. Această mașină utiliza sistemul de numerație zecimal și era acționată printr-o manivelă. Guvernul britanic a finanțat la început proiectul, dar a sistat finanțarea când a început să se vadă că mașina avea să coste mult mai mult decât se estimase inițial. Babbage a proiectat apoi mașina analitică, mai generală, după care a conceput un proiect nou pentru o mașină diferențială îmbunătățită („Difference Engine No. 2”) între 1847 și 1849. Inspirat de proiectul lui Babbage, Per Georg Scheutz a construit mai multe mașini diferențiale începând cu 1855; una a fost vândută în 1859 guvernului britanic.

Pe baza planurilor inițiale ale lui Babbage, Muzeul Științific din Londra a construit Difference Engine No. 2 între 1989 și 1991, sub coordonarea lui Doron Swade, pe atunci custode al departamentului de informatică, cu ocazia aniversării a 200 de ani de la moartea lui Babbage. În 2000, a fost terminată și imprimanta pe care o proiectase Babbage pentru mașina diferențială. Conversia proiectelor originare în desene tehnice potrivite pentru utilizarea în fabricație a relevat unele mici greșeli ale proiectului lui Babbage, care a trebuit să fie corectate. Odată terminate, atât mașina cât și imprimanta au funcționat și încă funcționează perfect. Mașina diferențială și imprimanta au fost construite cu toleranțele ce puteau fi realizate cu tehnologia secolului al XIX-lea, rezolvând o veche discuție privind fiabilitatea proiectului lui Babbage.

Deși „imprimanta” este astfel denumită aici, scopul ei principal era cel de a produce matrițe pentru tiparnițe; intenția lui Babbage era ca rezultatele mașinii să fie transmise direct tipografiilor, nu prin intermediul unui culegător care ar fi putut introduce greșeli. Tipărirea pe hârtie a rezultatelor este în principal un mijloc de verificare a performanțelor acesteia.

Pe lângă finanțarea construcției mecanismului de ieșire pentru Difference Engine No. 2 de la Muzeul Științific, Nathan Myhrvold a comandat construcția unei al doilea exemplar, care a devenit exponat al Muzeului de Istorie a Calculatoarelor din Mountain View, California începând cu 10 mai 2008.

Funcționare

Mașina diferențială este formată din mai multe coloane, numerotate de la 1 la N. Mașina poate stoca o valoare zecimală în fiecare coloană. Singura operație pe care o poate face este să adune valoarea unei coloane n + 1 cu cea a coloanei n pentru a produce noua valoare a coloanei n. Coloana N poate doar să stocheze o constantă, coloana 1 afișează (și eventual tipărește) valoarea calculului de la iterația curentă.

Mașina se programează prin setarea valorilor inițiale ale coloanelor. Coloana 1 se setează la valoarea polinomului la începutul calculelor. Coloana 2 se setează la valoarea obținută din prima și a doua derivată a polinomului la aceeași valoare a lui X. Fiecare dintre coloanele de la 3 la N se setează la o valoare calculată din primele $(n-1)$ derivate ale polinomului.

Temporizare

În proiectul lui Babbage, o iterație, adică un set complet de operații de adunare și propagare a transportului are loc o dată la fiecare patru rotații de manivelă. Coloanele pare și impare efectuează alternativ câte o adunare într-un ciclu. Șirul de operațiuni pentru coloana $n$ este deci:

1. Numără înainte și adună cu valoarea din coloana $n+1$ (Addition step)
2. Efectuează propagarea transportului la valoarea numărată
3. Numără înapoi până la zero, adunând la coloana $n-1$
4. Resetează valoarea numărată înapoi la valoarea inițială

Pașii 1,2,3,4 au loc pentru fiecare coloană impară, în vreme ce pașii 3,4,1,2 au loc pentru fiecare coloană pară.

Pași

Fiecare iterație creează un nou rezultat, ceea ce se realizează în patru pași corespunzători celor patru rotații complete ale manivelei. Cei patru pași sunt:

• Pasul 1. Toate coloanele pare (2,4,6,8) se adună la toate coloanele impare (1,3,5,7) simultan. Un braț interior rotește fiecare coloană pară pentru a determina numărarea până la zero pe fiecare roată. Pe măsură ce roțile numără până la zero, fiecare din ele își transferă valoarea unor roți dințate aflate între coloanele pare și cele impare. Aceste valori sunt transferate coloanei impare, determinând ca ele să numere în sus, adunând cele două valori. Valorile de pe coloanele impare care trec de la "9" la "0" activează o pârghie de propagare a transportului.
• Pasul 2. Propagarea transportului se realizează cu niște brațe spirale aflate în spate și care iau pe rând pârghiile de transport și incrementează roata superioară cu unu în caz că aceste pârghii sunt activate. Brațul spiral acționează roțile pe rând, astfel încât dacă însuși transportul de la un nivel determină transport la nivelul următor, și acesta să fie acționat corespunzător. În același timp, roțile dințate intermediare sunt readuse la poziția inițială, ceea ce le face să incrementeze roțile de pe coloanele pare înapoi la valorile inițiale. Roțile dințate intermediare sunt au dinți de lungime dublă pe o parte astfel încât să poată fi ridicate de pe roțile coloanelor impare, rămânând încă în contact cu cele de pe coloanele pare.
• Pasul 3. Este similar cu pasul 1, doar că aici coloanele impare (3,5,7) se adună la cele pare (2,4,6), iar coloana 1 își are valorile transferate printr-o roată dințată intermediară la mecanismul de tipărire din partea stângă a mașinii. Orice valoare de pe o coloană pară care trece de la "9" la "0" activează pârghia de transport. Valoarea de pe coloana 1, adică rezultatul evaluării polinomului, se trimite mecanismului imprimantei.
• Pasul 4. Este similar cu pasul 2, dar efectuează transportul pe coloanele pare, readucând coloanele impare la valorile inițiale.

Scăderea

Mașina reprezintă numerele negative în complement față de zece. Scăderea este doar o adunare cu un număr negativ reprezentat astfel. Aceasta funcționează exact la fel cu operațiile de scădere efectuate de calculatoarele moderne, care reprezintă numerele negative în complement față de doi.

Metoda diferențelor divizate

Maşina diferenţială de la Muzeul de Istorie a Calculatoarelor din Mountain View, California

Principiul mașinii diferențiale este metoda diferențelor divizate a lui Newton. Dacă valoarea inițială a unui polinom (și a diferențelor sale finite) se calculează în vreun fel dintr-o valoare a lui X, mașina diferențială poate calcula atunci oricâte valori apropiate, cu ajutorul acestei metode a diferențelor divizate. Se poate ilustra aceasta printr-un exemplu. Fie polinomul de gradul al doilea $p(x)=2x^{2}-3x+2$ pentru care se dorește tabelarea valorilor p(0), p(1), p(2), p(3), p(4) etc. Tabelul de mai jos se construiește după cum urmează: a doua coloană conține valorile polinomului, a treia coloană conține diferențele dintre cei doi vecini din a doua coloană, iar a patra coloană conține diferențele dintre cei doi vecini ai săi din a treia coloană:

x	p(x) = 2x2 − 3x + 2	diff1(x) = ( p(x+1) - p(x) )	diff2(x) = ( diff1(x+1) - diff1(x) )
0	2	-1	4
1	1	3	4
2	4	7	4
3	11	11
4	22

Se observă că valorile de pe a patra coloană sunt constante. Aceasta nu este doar o coincidență, ci este o proprietate fundamentală ce stă la baza funcționării metodei. Dacă se începe cu orice polinom de grad n, numărul de pe coloana n + 1 va fi întotdeauna constant, deoarece acea coloană reprezintă chiar derivata a n-a a funcției polinomiale de gradul n, care este întotdeauna o constantă.

Tabelul de mai sus s-a construit de la stânga la dreapta, dar se poate continua de la dreapta la stânga pe diagonală pentru a calcula alte valori ale polinomului.

Pentru a calcula p(5) se utilizează valorile de pe diagonala cea mai de jos. Se începe cu a valoarea constantă de pe a patra coloană, 4, și se copiază pe toată coloana. După aceea, se continuă pe a treia coloană adunând cu 11 pentru a obține 15. Apoi se continuă pe a doua coloană, cu valoarea anterioară, 22, la care se adaugă 15 de pe a treia coloană. Astfel, p(5) este 22+15 = 37. Pentru a calcula p(6), se aplică același algoritm pe valorile lui p(5): se ia 4 de pe a patra coloană, se adaugă la valoarea 15 de pe coloana a treia și se obține 19, apoi se adună cu a doua coloană, 37, și se obține 56, which is p(6).

Acest proces poate continua la nesfârșit. Valorile polinomului se produc fără a fi nevoie să se efectueze vreo înmulțire. O mașină diferențială are nevoie să știe doar cum să facă adunări. De la o buclă la alta, ea trebuie să stocheze 2 numere în cazul de față (ultimele elemente din prima și a doua coloană); dacă se dorește tabelarea unor polinoame de grad n, este nevoie de suficient spațiu pentru stocarea a n numere.

Mașina lui Babbage, construită în 1991, putea stoca 8 numere de câte 31 de cifre zecimale și putea astfel tabela polinoame de gradul al 7-lea la această precizie.

Valori inițiale

Valorile inițiale ale coloanelor se pot stabili calculând manual la început N valori consecutive ale funcției și apoi prin backtracking, calculând diferențele.

Col $1_{0}$ primește valoarea funcției la începutul calculelor, $f(0)$. Col $2_{0}$ este diferența dintre $f(1)$ și $f(0)$...

Dacă funcția de calculat este una polinomială, exprimată ca

$f(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{2}x^{2}+a_{1}x+a_{0}\,$

valorile inițiale se pot calcula direct din coeficienții constanți a₀, a₁,a₂, ..., a_n fără a fi nevoie de date efective. Valorile inițiale sunt deci:

• Col $1_{0}$ = a₀
• Col $2_{0}$ = a₁ + a₂ + a₃ + a₄ + ... + a_n
• Col $3_{0}$ = 2a₂ + 6a₃ + 14a₄ + 30a₅ + ...
• Col $4_{0}$ = 6a₃ + 36a₄ + 150a₅ + ...
• Col $5_{0}$ = 24a₄ + 240a₅ + ...
• Col $6_{0}$ = 120a₅ + ...
• $...$

Utilizarea derivatelor

Multe funcții uzuale sunt însă funcții analitice, care pot fi exprimate ca serii de puteri, de exemplu ca serii Taylor. Valorile inițiale se pot calcula cu orice grad de precizie; dacă se efectuează corect, mașina va da rezultate exacte la primii N pași. După aceasta, mașina va da doar o aproximație a valorilor funcției.

Seriile Taylor exprimă funcția ca sumă a derivatelor ei. Pentru multe funcții, derivatele de ordin superior se obțin trivial; funcția sinus, de exemplu, în 0 are derivatele 0 sau $+/-1$. Începând calculele de la 0, se poate obține seria simplificată Maclaurin

$\sum _{n=0}^{\infty }{\frac {f^{(n)}(0)}{n!}}(x)^{n}$

Aceeași metodă de calcul a valorilor inițiale după coeficienți se poate utiliza ca și la funcțiile polinomiale. Coeficienții polinomiali constanți vor avea valorile

$a_{n}\equiv {\frac {f^{(n)}(0)}{n!}}$

Ajustarea curbei

Problema cu metodele descrise mai sus o reprezintă acumularea erorilor care vor face ca seria să nu mai conveargă la funcția reală. O soluție ce garantează o eroare maxim constantă este ajustarea curbei. Se calculează un minim de N valori răspândite echilibrat de-a lungul intervalului pe care se efectuează calculele. Cu o tehnică de genul eliminării gaussiene, se găsește o interpolare polinomială de gradul N-1. Cu polinomul optimizat, valorile inițiale se pot calcula ca mai sus.