<  1  2  3  4  5  6  7  8  9  10  11  12

maszyna różnicowa

Maszyna Różnicowa - komputer specjalizowany
(Difference Engine)

czyli, Maszyna mechaniczna
do obliczania kolejnych wartości wielomianu

Część I

Spis treści

Wstęp

Maszyna różnicowa, czyli komputer wyspecjalizowany do obliczania wartości wielomianów (teoretycznie dowolnego stopnia), jest największym osiągnięciem człowieka w historii rozwoju ludzkości, choć zapomnianym. Zaletą tego niezwykłego i na owe czasy wykraczającego poza rozwój techniki i myśli ludzkiej komputera jest to, że może być zbudowany zarówno w wersji mechanicznej, elektronicznej, jak i dowolnej innej przyszłościowej technologii.

Jest to maszyna, która może przeprowadzać obliczenia zarówno w sposób szeregowy jak i równoległy. W wersji równoległej wykazuje bardzo dużą szybkość pracy. Wykonana w technologii krzemowej jest bez porównania szybsza od najszybszego uniwersalnego komputera (mowa tu o mikroprocesorze). Wiele setek operacji dodawania, jakie wykonuje współczesny mikroprocesor, może wykonać w kilku zaledwie ruchach. Aż się nie chce wierzyć.

Sama potrzeba obliczania wartości wielomianów towarzyszy nam na każdym kroku, szczególnie w nauce i technice, np: obliczanie trajektorii lotu pocisków przy uwzględnieniu warunków naturalnych środowiska i zmian tych warunków, obliczanie toru ruchów sond i statków kosmicznych w polu grawitacyjnym ziemi czy innych ciał niebieskich, sporządzanie tablic matematycznych, czy też obliczanie szeregu wartości funkcji, aproksymowanych wielomianami, itd.

Maszyna różnicowa została wynaleziona właśnie do sporządzania tablic służących do wyznaczania trajektorii ruchu pocisków armatnich, lub tablic matematycznych.

Konstrukcyjnie, maszyna różnicowa opiera się na takich samych zasadach obliczeń, jakie wykorzystuje współczesny mikroprocesor. Podstawowym elementem konstrukcyjnym jej jest sumator (potrafiący dodawać liczby). Maszyna posiada ich zestaw, a więc jest to pewnego rodzaju urządzenie komputerowe, przetwarzające dane, wraz z możliwością wprowadzania liczb do maszyny i wyprowadzania z niej w postaci wyników obliczeń. Maszyna prowadzi obliczenia od stanu początkowego, który się ustawia (resetuje), czyli tak, jak tradycyjny komputer.

Poprzez zestaw sumatorów oraz zaimplementowane, w konstrukcji maszyny, wzory matematyczne, pozwala osiągnąć niespotykane w innych konstrukcjach (mało złożonych urządzeń), możliwości.

Dzięki możliwości budowania sumatorów w szerokiej gamie różnych technologii (elektronicznej, mechanicznej lub innej przyszłosciowej technologii), maszyna różnicowa nadaje się do najszybszego testowania możliwości budowy komputerów cyfrowych w innej technologii niż krzemowa.

Podkreślić należy raz jeszcze, że maszyna ta fascynuje największym przełożeniem jej możliwości, do prostoty konstrukcji maszyny, że wszystkich urządzeń, jakie do tej pory stworzył człowiek oraz dużą szybkością pracy jej wersji równoległej.

To, czy maszyna jest szeregowa czy równoległa, zależy tylko od programu prowadzania jej obliczeń, a nie konstrukcji maszyny.

Jest dobitnym przykładem wielkości matematyki. Zasada działania jej opiera się właśnie na matematyce. Jest czystym przełożeniem matematyki na reprezentację tej matematyki w maszynie. Można by też powiedzieć, że jest obopólnym dziełem zarówno matematyki, jak i jej kostruktora, który ją wynalazł.

Jedyną wadą tej maszyny jest jej specjalizacja, w miejsce uniwersalności dzisiejszego komputera, ale i tak pokrywa ona szeroki wachlarz różnych zastosowań (choć dzisiaj, jej miejsce zajmuje komputer).

Rys historyczny

W roku 1623 niemiecki matematyk, astronom i konstruktor Wilhelm Schickard opracował pierwszą mechaniczną maszynę liczącą do wykonywania podstawowych operacji arytmetycznych.

W roku 1642 podobnego wyczynu dokonał również francuski matematyk, fizyk i konstruktor Blaise Pascal.

W roku 1674 niemiecki matematyk Gottfried Wilhelm Leibniz udoskonalił maszynę Pascala, a w roku 1822 francuski konstruktor i biznesmen Thomas de Colmar opracował mechaniczną maszynę liczącą, której ulepszona wersja doczekała się seryjnej produkcji i powszechnej sprzedaży.

Ówczesna maszyna licząca potrafiła dodawać, odejmować, mnożyć i dzielić. O tym, jakie liczby maszyna ma rachować i jakie działania ma wykonywać decydował człowiek. Na owe czasy maszyna była wielkim ułatwieniem dla osoby, której praca związana była z ciągłym rachowaniem. Potrafiła odciążyć człowieka w jego pracy umysłowej, zwanej kalkulacją, poprzez wykonywanie jedynie mechanicznych czynności na maszynie.

Jednakże w owym czasie były zadania wymagające większego nakładu pracy rachunkowej. Wymagały one wykowania szeregu powtarzających się działań elementarnych, jak dodawanie i mnożenie, w czym posiadanie mechanicznego kalkulatora wcale nie zmniejszało pracy, ale nadal czyniło ją nadal żmudną, nudną i podatną na błędy człowieka.

Szczególnie widać to było przy obliczaniu wartości wielomianów. Praca ta związana była z produkcją wielkich tablic matematycznych i wykonywana była przez sporą ilość zatrudnionych rachmistrzów. Posługiwali się oni dotychczas znanymi mechanicznymi kalkulatorami, które ułatwiały pracę, lecz jej nie zmniejszało. Jak wielką pracę mieli do wykonania przedstawię poniżej.

Wielkość nakładu pracy przy obliczaniu wartości wielomianów

Przy obliczeniu wartości f(x) pewnego wielomianu n-tego stopnia o postaci:

f(x) = anxn + an-1xn-1 + an-2xn-2 + ... + a1x1 + a0

gdzie an < > 0, a liczby a0, a1, a2, ..., an są współczynnikami wielomianu, rachmistrz wykonując obliczanie wprost ze wzoru wielomianu musi wykonać [2n-1] mnożeń i[n] dodawań ([n-1] mnożeń musi wykonać dla obliczenia potęg, a [n] mnożeń dla przemnożenia przez współczynniki i na końcu [n] dodawań).

Jeżeli rachmistrz ułatwi sobie zadanie i skorzysta z innego przedstawienia wielomianu (według schematu Hörnera)

f(x) = (...((anx + an-1)x + an+2)x + ... + a1)x1 + a0

to ilość potrzebnych operacji można zmniejszyć do: [n] mnożeń i [n] dodawań, czyli o [n-1] mnożeń mniej w stosunku do metody bezpośredniej.

W końcu, jeżeli rachmistrz ma za zadanie obliczyć [m] wartości wielomianu f(x) dla kolejnych wartości x= (x1,x2,...,xm) to musi wykonać [m*(2n-1)] mnożeń i [m*n] dodawań korzystając z bezpośredniego wzoru lub[m*n] mnożeń i [m*n] dodawań korzystając ze schematu Hörnera.

Duża ilość działań potrzebnych do obliczenia kolejnych wartości wielomianu spowodowała, że zaczęto poszukiwać innych metod obliczeń, bardziej efektywnych. Prace ówczesnych matematyków np. Newtona doprowadziły do opracowania lepszych sposobów obliczeń. Taką metodą obliczeń, która bardzo poprawiła efektywność liczenia, była metoda różnic skończonych. Umożliwia ona obliczenie kolejnej wartości wielomianu za pomocą jedynie [n] dodawań. Mnożyć już nie potrzeba.

Jaką można osiągniąć oszczędność czasu wykorzystując metodę różnic, przedstawia poniższa tabela.

Wielkość nakładu pracy na obliczanie 10-ciu kolejnych wartości
wielomianu 6-tego stopnia
Metoda obliczania Ilość kolejnych operacji do wykonania
mnożenie dodawanie łącznie
Obliczanie wprost ze wzoru 110 60 170
Skorzystanie ze schematu Hörnera 60 60 120
Skorzystanie z metody różnicowej 0 60 60
Równoległa maszyna różnicowa 0 2 2

Patrząc się na ostatnią pozycję powyższej tabeli pragnę przypomnieć, że mamy tu do czynienia jedynie z maszyną mechaniczną zbudowaną z przekładni zębatych, a nie z superkomputerem wieloprocesorowym.

Nad automatyzacją obliczeń wielomianów metodą różnicową zastanawiał się już w roku 1786 J.H. Müller opracowując projekt maszyny różnicowej. Jego kontynuatorem był Charles Babbage, który w roku 1821 r. zbudował pierwszy model maszyny różnicowej, z dwoma różnicami, potrafiącą przeliczać wielomiany drugiego stopnia. Charles Babbage rozpoczął też prace nad maszyną różnicową z sześcioma różnicami do przeliczania wielomianów do 6-tego stopnia.

Siła maszyny różnicowej zawiera się przede wszystkich w jej prostej budowie. Składa się ona z n+1 takich samych sumatorów, które można oznaczyć jako S0,S1,...,Sn. Zadaniem sumatora jest przechowywanie liczby (wyniku sumowania) oraz wykonywanie operacji sumowania liczb. Jedna z tych liczb jest przechowywana w sumatorze, a druga pobierana z sąsiedniego sumatora reprezentującego wyższą różnicę (wyższy numer). Sumator S0 jest przeznaczony na przechowywanie kolejnych wartości funkcji wielomianu, a sumatory S1,...,Sn służą do przechowywania kolejnych różnic. Sumatory mają zdolność ustawienia w nich wartości początkowej i wykonywania operacji sumowania między przyległymi sumatorami. Schematyczną budowę maszyny różnicowej przedstawia poniższy rysunek.
f(x) D D2 D3 D4 D5 D6 ... Dn-1 Dn
S0 S1 S2 S3 S4 S5 S6 ... Sn-1 Sn

Ustawienie wartości początkowych
w sumatorach		 Poszczególne sumatory wykonują
operacje sumowania
sumator S0= wartość funkcji f(x)
sumator S1 = wartość różnicy D
sumator S2 = wartość różnicy D2
sumator S3 = wartość różnicy D3
sumator S4 = wartość różnicy D4
sumator S5 = wartość różnicy D5
sumator S6 = wartość różnicy D6
. . . . . . . . . . . 
sumator Sn-1 = wartość różnicy Dn-1
sumator Sn = wartość różnicy Dn 		S0 = S0 + S1
S1 = S1 + S2
S2 = S2 + S3
S3 = S3 + S4
S4 = S4 + S5
S5 = S5 + S6
S6 = S6 + S7
. . . . . . . . .
Sn-1 = Sn-1 + Sn
Sn = stała wartość

Kolejność sumowania zależy
od techniki sumowania.

Metoda różnicowa nadaje się do obliczenia kolejnych wartości wielomianu do n-tego stopnia, dla których kolejne wartości zmiennej x są równoodległe, o stałą wartość h, np. f(x), f(x+h), f(x+2h), f(x+3h),..., f(x+i*h).

Na wstępnie pragnę objaśnić pojęcie różnicy, jakie występuje w tej metodzie. Jest to po prostu różnica pomiędzy wartościami funkcji f(x) obliczonymi dla dwóch różnych wartości zmiennych x, oddalonych o stałą wielkość h, np: Df(x+h) = f(x+h) - f(x). Kolejne różnice są różnicami pomiędzy wartościami niższych różnic, np: D2 f(x+h) = D f(x+h) - Df(x), itd.

Występują dwie metody sumowania przyległych sumatorów, przy założeniu, że sumujemy zawsze sumatory przyległe - do liczby przechowywanej w sumatorze o mniejszym numerze dodajemy liczbę przechowywaną w sumatorze o numerze większym:

  • Metoda I sumowania, od sumatora Sn-1 w kierunku sumatora S0.

    Cechą charakterystyczną tej metody jest to, że suma liczb przechowywanych w dwóch przyległych sumatorach może być liczona wówczas, kiedy w danej serii sumowań, liczba w sumatorze o numerze niższym ma jeszcze starą wartość, a liczba w sumatorze o numerze wyższym ma już nową wartość otrzymaną w wyniku sumowania w sumatorach o wyższych numerach.

  • Metoda II sumowania, od sumatora S0 w kierunku sumatora Sn-1.

    Cechą charakterystyczną tej metody jest to, że w danej serii sumowań, suma liczb z dwóch przyległych sumatorów, może być liczona wówczas, kiedy liczby te mają jeszcze starą wartość.

W różnych materiałach, na temat maszyny różnicowej, obie metody są używane wzajemnie, wprowadzając trochę zamieszania, i wywołując sugestię, że popełniono pewną pomyłkę.

Poniższa tabela przedstawia szczegóły obu tych metod. Dla ułatwienia zrozumienia przedstawiono dwa stany sumatorów: stan po zsumowaniu dla wartości zmiennej x i stan po zsumowaniu dla wartości zmiennej x+h.

wielomian: f(x) = anxn + an-1xn-1 + an-2xn-2 + ... + a1x1 + a0
Metoda I Metoda II

x f(x) Df(x) ...
x+h f(x+h) Df(x+h) ...

Kolejną wartość funkcji liczymy:

f(x+h) = Df(x+h) + f(x)

Stąd kolejne różnice są równe:

Df(x+h) = f(x+h) - f(x)
D2f(x+h) = Df(x+h) - Df(x);
D3f(x+h) = D2f(x+h) - D2f(x);
D4f(x+h) = D3f(x+h) - D3f(x);
D5f(x+h) = D4f(x+h) - D4f(x);
D6f(x+h) = D5f(x+h) - D5f(x);
. . . . . . . . . . . . . . .
Dnf(x+h) = Dn-1f(x+h) - Dn-1f(x)
= R (stała)
Dn+1f(x+h) = Dnf(x+h) - Dnf(x)
= 0
x f(x) Df(x) ...
x+h f(x+h) Df(x+h) ...

Kolejną wartość funkcji liczymy:

f(x+h) = Df(x) + f(x)

Stąd kolejne różnice są równe:

Df(x) = f(x+h) - f(x)
D2f(x) = Df(x+h) - Df(x);
D3f(x) = D2f(x+h) - D2f(x);
D4f(x) = D3f(x+h) - D3f(x);
D5f(x) = D4f(x+h) - D4f(x);
D6f(x) = D5f(x+h) - D5f(x);
. . . . . . . . . . . . . . .
Dnf(x) = Dn-1f(x+h) - Dn-1f(x)
= R (stała)
Dn+1f(x) = Dnf(x+h) - Dnf(x)
= 0
Kolejne wartości funkcji wielomianu n-tego stopnia
i poszczególnych różnic
Metoda I Metoda II
Dnf(x+h) = Dnf(x)
Dn-1f(x+h) = Dn-1f(x) + Dnf(x+h)
. . . . . . . . . . . . .
D5f(x+h) = D5f(x) + D6f(x+h);
D4f(x+h) = D4f(x) + D5f(x+h);
D3f(x+h) = D3f(x) + D4f(x+h);
D2f(x+h) = D2f(x) + D3f(x+h);
Df(x+h) = Df(x) + D2f(x+h);
f(x+h) = f(x) + Df(x+h); 		f(x+h) = f(x) + Df(x)
Df(x+h) = Df(x) + D2f(x);
D2f(x+h) = D2f(x) + D3f(x);
D3f(x+h) = D3f(x) + D4f(x);
D4f(x+h) = D4f(x) + D5f(x);
D5f(x+h) = D5f(x) + D6f(x);
. . . . . . . . . . . . .
Dn-1f(x+h) = Dn-1f(x) + Dnf(x)
Dnf(x+h) = Dnf(x)
W sposób skrótowy sumowanie w niżej pokazanej maszynie
można przedstawić następująco:

f(x) D D2 D3 D4 D5 D6 ... Dn-1 Dn

Metoda I Metoda II
Dn pozostawiamy bez zmian

Sumujemy kolejno (od Dn-1
do f(x))

Dn-1 = Dn-1 + Dn
. . . . . . . . . . . . .
D5 = D5 + D6
D4 = D4 + D5
D3 = D3 + D4
D2 = D2 + D3
D = D + D2
f(x+h) = f(x) + D

Sumujemy kolejno
od f(x) do Dn-1)

f(x+h) = f(x) + D
D = D + D2
D2 = D2 + D3
D3 = D3 + D4
D4 = D4 + D5
D5 = D5 + D6
. . . . . . . . . . . . .
Dn-1 = Dn-1 + Dn
Dnpozostawiamy bez zmian

Dla metody I kolejną wartość funkcji można przedstawić następująco:

f(x+h) = f(x) + Df(x+h)
= f(x) + Df(x) + D2f(x+h)
= f(x) + Df(x) + D2f(x) + D3f(x+h)
= f(x) + Df(x) + D2f(x) + D3f(x) + D4f(x) + D5f(x) + D6f(x) +
... + Dnf(x+h);

dodawanie wykonuje się w następującej kolejności

f(x+h) = f(x) + (Df(x) + (D2f(x) + (D3f(x) + (D4 f(x) + (D5f(x) + D6f(x)))))) dodawanie odbywa się od sumatora Sn-1

Charakterystyczną cechą metody różnic zastosowaną do wielomianu n-tego stopnia jest to, że dla każdej wartości zmiennej x wartość różnicy Dnf(x) jest stała, a wartość różnicy Dn+1f(x) jest równa zero (co oczywiście wynika ze stałej wartości Dnf(x)).

Ustawienie początkowe maszyny różnicowej

Aby można było przeliczać kolejne wartości wielomianu należy rozpocząć od ustawienia wartości początkowych liczb (wartości różnic startowych) na sumatorach maszyny.

Jest kilka metod obliczenia różnic początkowych. Wybiorę metodę najprostszą, opartą na obliczeniu kolejnych różnic na podstawie pobranej próbki kilku kolejnych wartości funkcji. Dla wielomianu n-tego stopnia musimy dysponować próbką n+1 kolejnych wartości tej funkcji. Metoda ta jest na tyle ciekawa, że sama maszyna różnicowa nam te różnice sama obliczy i w ten sposób automatycznie się ustawi.

Jeszcze nie natknąłem się w materiałach poświęconych maszynie różnicowej na informacje dotyczące samoczynnego ustawiania się maszyny różnicowej (autoinicjowanie) i w ten sposób o braku potrzeby obliczania różnic początkowych. Jeżeli nikt tej własności maszyny dotychczas nie zauważył, może przeoczyłem, to jestem pierwszym, który odkrył tą dodatkową cechę tej, z jednej strony bardzo prostej, a z drugiej strony bardzo potężnej maszyny, będącej bezpośrednim ucieleśnieniem matematyki w przyrodzie. Na wszelki wypadek podaję datę swojego odkrycia - 09.11.2007.

Obliczanie różnic

Najpierw pokażę, jak znaleźć wzory na poszczególne różnice, a następnie przedstawię, jak sama maszyna różnicowa może nam w tym pomóc, sama się inicjując.

Maszyna różnicowa szeregowa

Metoda sumowania I

a/ Obliczenie pierwszej różnicy

Df(x+h) = f(x+h) - f(x)
podstawiając x = x-h otrzymujemy wzór na pierwszą różnicę w punkcie x:

Df(x) = f(x) - f(x-h);

b/ Obliczenie drugiej różnicy

D2f(x+h) = Df(x+h) - Df(x)
= f(x+h) - f(x) - (f(x) - f(x-h))
= f(x+h) - 2f(x) + f(x-h);

podstawiając x = x-h otrzymujemy wzór na drugą różnicę w punkcie x:

D2f(x) = f(x) - 2f(x-h) + f(x-2h);

c/ Obliczenie trzeciej różnicy

D3f(x+h) = D2f(x+h) - D2f(x)
= f(x+h) - 2f(x) + f(x-h) - f(x) + 2f(x-h) - f(x-2h)
= f(x+h) - 3f(x) + 3f(x-h) - f(x-2h);

podstawiając x = x-h otrzymujemy wzór na trzecią różnicę w punkcie x:

D3f(x) = f(x) - 3f(x-h) + 3f(x-2h) - f(x-3h);

d/ Obliczenie czwartej różnicy

D4f(x+h) = D3f(x+h) - D3f(x)
= f(x+h) - 3f(x) + 3f(x-h) - f(x-2h) - f(x) + 3f(x-h) - 3f(x-2h) + f(x-3h)
= f(x+h) - 4f(x) + 6f(x-h) - 4(x-2h) + f(x-3h)

podstawiając x = x-h otrzymujemy wzór na czwartą różnicę w punkcie x:

D4f(x) = f(x) - 4f(x-h) + 6f(x-2h) - 4(x-3h) + f(x-4h);

e/ Obliczenie piątej różnicy

D5f(x+h) = D4f(x+h) - D4f(x)
= f(x+h) - 4f(x) + 6f(x-h) - 4(x-2h) + f(x-3h) - f(x) + 4f(x-h) - 6f(x-2h) + 4(x-3h) - f(x-4h)
= f(x+h) - 5f(x) + 10f(x-h) - 10f(x-2h) + 5f(x-3h) - f(x-4h)

podstawiając x = x-h otrzymujemy wzór na piątą różnicę w punkcie x:

D5f(x) = f(x) - 5f(x-h) + 10f(x-2h) - 10f(x-3h) + 5f(x-4h) - f(x-5h)

f/ Obliczenie szóstej różnicy

D6f(x+h) = D5f(x+h) - D5f(x)
= f(x+h) - 5f(x) +10f(x-h) - 10f(x-2h) + 5f(x-3h) - f(x-4h) - f(x) + 5f(x-h) - 10f(x-2h) + 10f(x-3h) - 5f(x-4h) + f(x-5h)
= f(x+h) - 6f(x) + 15f(x-h) - 20f(x-2h) + 15f(x-3h) - 6f(x-4h) + f(x-5h)

podstawiając x = x-h otrzymujemy wzór na szóstą różnicę w punkcie x:

D6f(x) = f(x) - 6f(x-h) + 15f(x-2h) - 20f(x-3h) + 15f(x-4h) - 6f(x-5h) + f(x-6h)

Zakładając, że stopień wielomianu n = 6, to dalsze różnice będą wynosiły zero.

Metoda sumowania II

a/ Pierwsza różnica będzie równa:

Df(x) = f(x+h) - f(x);

b/ Obliczenie drugiej różnicy.

Podstawiając x = x+h do wzoru na pierwszą różnicę otrzymujemy:

Df(x+h) = f(x+2h) - f(x+h)

Druga różnica będzie równa

D2f(x) = Df(x+h) - Df(x)
= f(x+2h) - f(x+h) - f(x+h) + f(x)
= f(x+2h) - 2f(x+h) + f(x);

D2f(x) = f(x+2h) - 2f(x+h) + f(x);

c/ Obliczenie trzeciej różnicy.

Podstawiając x = x+h do wzoru na drugą różnicę otrzymujemy:

D2f(x+h) = f(x+3h) - 2f(x+2h) + f(x+h);

Trzecia różnica będzie równa:

D3f(x) = D2f(x+h) - D2f(x)
= f(x+3h) - 2f(x+2h) + f(x+h) - f(x+2h) + 2f(x+h) -f(x)
= f(x+3h) - 3f(x+2h) + 3f(x+h) - f(x);

D3f(x) = f(x+3h) - 3f(x+2h) + 3f(x+h) - f(x);

d/ Obliczenie czwartej różnicy.

Podstawiając x = x+h do wzoru na trzecią różnicę otrzymujemy:

D3f(x+h) = f(x+4h) - 3f(x+3h) + 3f(x+2h) - f(x+h);

Czwarta różnica będzie równa:

D4f(x) = D3f(x+h) - D3f(x)
= f(x+4h) - 3f(x+3h) + 3f(x+2h) - f(x+h) - f(x+3h) + 3f(x+2h) - 3f(x+h) + f(x)
= f(x+4h) - 4f(x+3h) +6f(x+2h) - 4(x+h) + f(x)

D4f(x) = f(x+4h) - 4f(x+3h) + 6f(x+2h) - 4(x+h) + f(x);

e/ Obliczenie piątej różnicy.

Podstawiając x = x+h do wzoru na czwartą różnicę otrzymujemy:

D4f(x+h) = f(x+5h) - 4f(x+4h) +6f(x+3h) - 4(x+2h) + f(x+h);

Piąta różnica będzie równa:

D5f(x) = D4f(x+h) - D4f(x)
= f(x+5h) - 4f(x+4h) + 6f(x+3h) - 4(x+2h) + f(x+h) - f(x+4h) + 4f(x+3h) - 6f(x+2h) + 4(x+h) - f(x)
= f(x+5h) - 5f(x+4h) + 10f(x+3h) - 10f(x+2h) + 5f(x+h) - f(x)

D5f(x) = f(x+5h) - 5f(x+4h) + 10f(x+3h) - 10f(x+2h) +5f(x+h) - f(x)

e/ Obliczenie szóstej różnicy.

Podstawiając x = x+h do wzoru na piątą różnicę otrzymujemy:

D5f(x+h) = f(x+6h) - 5f(x+5h) + 10f(x+4h) - 10f(x+3h) + 5f(x+2h) - f(x+h)

Szósta różnica będzie równa:

D6f(x) = D5f(x+h) - D5f(x)
= f(x+6h) - 5f(x+5h) + 10f(x+4h) - 10f(x+3h) + 5f(x+2h) - f(x+h) - f(x+5h) + 5f(x+4h) - 10f(x+3h) + 10f(x+2h) - 5f(x+h) + f(x)
= f(x+6h) - 6f(x+5h) + 15f(x+4h) - 20f(x+3h) + 15f(x+2h) - 6f(x+h) + f(x)

D6f(x) = f(x+6h) - 6f(x+5h) + 15f(x+4h) - 20f(x+3h) + 15f(x+2h) - 6f(x+h) + f(x)

Zakładając, że stopień wielomianu wynosi n = 6 to dalsze różnice będą wynosiły zero.

Zestawienie wzorów

Sposoby sumowania w maszynie różnicowej szeregowej

W metodzie I sumowanie odbywa się począwszy od sumatora Sn-1 , a kończąc na sumatorze S0 .

W metodzie II sumowanie odbywa się począwszy od sumatora S0, a kończąc na sumatorze Sn-1 .

Metoda I i II Maszyna różnicowa szeregowa
x f(x) Df(x) D2f(x) D3f(x) D4f(x) D5f(x) D6f(x)
x+h f(x+h) Df(x+h) D2f(x+h) D3f(x+h) D4f(x+h) D5f(x+h) D6f(x+h)
= D6f(x)

Sumowanie w sumatorach odbywa się następująco:

Operacja Metoda I Metoda II
1
2
3
4
5
6
7 		D6f(x+h) = D6f(x) + 0
D5f(x+h) = D5f(x) + D6f(x+h)
D4f(x+h) = D4f(x) + D5f(x+h)
D3f(x+h) = D3f(x) + D4f(x+h)
D2f(x+h) = D2f(x) + D3f(x+h)
Df(x+h) = Df(x) + D2f(x+h)
f(x+h) = f(x) + Df(x+h) 		f(x+h) = f(x) + Df(x)
Df(x+h) = Df(x) + D2f(x)
D2f(x+h) = D2f(x) + D3f(x)
D3f(x+h) = D3f(x) + D4f(x)
D4f(x+h) = D4f(x) + D5f(x)
D5f(x+h) = D5f(x) + D6f(x)
D6f(x+h) = D6f(x) + 0
Uwaga! Wartości początkowe różnic dla każdej z metod są inne.
Operacje 1,..,7 są wykonywane po kolei.

Ustawienie początkowe maszyny różnicowej szeregowej

Metoda sumowania I

Wartości początkowe sumatorów wynoszą:

Df(x) = f(x) - f(x-h)
D2f(x) = f(x) - 2f(x-h) + f(x-2h)
D3f(x) = f(x) - 3f(x-h) + 3f(x-2h) - f(x-3h)
D4f(x) = f(x) - 4f(x-h) + 6f(x-2h) - 4(x-3h) + f(x-4h)
D5f(x) = f(x) - 5f(x-h) + 10f(x-2h) - 10f(x-3h) + 5f(x-4h) - f(x-5h)
D6f(x) = f(x) - 6f(x-h) + 15f(x-2h) - 20f(x-3h) + 15f(x-4h) - 6f(x-5h) + f(x-6h)

Metoda sumowania II

Wartości początkowe sumatorów wynoszą:

Df(x) = f(x+h) - f(x)
D2 f(x) = f(x+2h) - 2f(x+h) + f(x)
D3 f(x) = f(x+3h) - 3f(x+2h) + 3f(x+h) - f(x)
D4f(x) = f(x+4h) - 4f(x+3h) + 6f(x+2h) - 4f(x+h) + f(x)
D5f(x) = f(x+5h) - 5f(x+4h) + 10f(x+3h) - 10f(x+2h) +5f(x+h) - f(x)
D6f(x) = f(x+6h) - 6f(x+5h) + 15f(x+4h) - 20f(x+3h) +15f(x+2h) - 6f(x+h) + f(x)

Współczynniki we wzorach na poszczególne różnice tworzą trójkąt Pascala, na podstawie którego możemy znaleźć wzory na kolejne różnice, większe niż 6.

1
1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5  10  10  5  1
1  6  15  20  15  6  1
1  7  21  35  35  21  7  1
1  8  28  56  70  56  28  8  1
1  9  36  84  126  126  84  36  9  1
. . . . . . . . . . . . . . . . . . .

Trójkąt Pascala

Maszyna różnicowa równoległa
(The Parallel Difference Engine)

Podczas sumowania liczb przechowywanych w sumatorach przyległych Metodą I czy II, sumowanie nie może odbywać się jednocześnie, ponieważ może zaistnieć przypadek, że w trakcie danego sumowania może zostać użyta liczba z sumatora znajdującego się w trakcie składowania wyniku z innego sumowania.

Z tego więc względu, w celu izolacji sąsiednich par sumatorów, biorących udział w sumowaniu, proces ten należy wykonywać po kolei. Taką metodę sumowania nazywa się szeregową. W metodzie tej, dla wielomianu n-tego stopnia, należy wykonać n sumowań po kolei (pomiędzy kolejnymi wyliczeniami wartości tego wielomianu).

Możemy również odizolować pary sumatorów poprzez dodawanie najpierw w sumatorach o numerach nieparzystych, a następnie w sumatorach o numerach parzystych i numerze zero nawet. W grupie sumatorów nieparzystych lub grupie parzystych i 0 operacje sumowania mogą być wykonywane jednocześnie. Dla wielomianu dowolnego stopnia ilość operacji wykonywanych po kolei wynosi wówczas 2.

Równoległe sumowanie różnic

Metoda I Maszyna różnicowa (równoległa)
x f(x) Df(x) D2f(x+h) D3f(x+h) D4f(x+2h) D5f(x+2h) D6f(x+3h)
x+h n f(x) Df(x+h) D2f(x+h) D3f(x+2h) D4f(x+2h) D5f(x+3h) D6f(x+4h)
p f(x+h) Df(x+h) D2f(x+2h) D3f(x+2h) D4f(x+3h) D5f(x+3h) D6f(x+4h)
= D6f(x+3h)
n - sumowanie w sumatorach o numerze nieparzystym
p - sumowanie w sumatorach o numerach parzystych i numerze zero

Metoda II Maszyna różnicowa (równoległa)
x f(x) Df(x-h) D2f(x-h) D3f(x-2h) D4f(x-2h) D5f(x-3h) D6f(x-3h)
x+h n f(x) Df(x) D2f(x-h) D3f(x-h) D4f(x-2h) D5f(x-2h) D6f(x-3h)
p f(x+h) Df(x) D2f(x) D3f(x-h) D4f(x-h) D5f(x-2h) D6f(x-2h)
=D6f(x-3h)
n - sumowanie w sumatorach o numerze nieparzystym
p - sumowanie w sumatorach o numerach parzystych i numerze zero

Operacje wykonywane w maszynie różnicowej równoległej
Ope-
racja		 Metoda I Metoda II
1 jednoczesne sumowanie w sumatorach nieparzystych
D5f(x+3h) = D5f(x+2h) + D6f(x+3h)
D3f(x+2h) = D3f(x+h) + D4f(x+2h)
Df(x+h) = Df(x) + D2f(x+h) 		Df(x) = Df(x-h) + D2f(x-h)
D3f(x-h) = D3f(x-2h) + D4f(x-2h)
D5f(x-2h) = D5f(x-3h) + D6f(x-3h)
2 jednoczesne sumowanie w sumatorach parzystych i sumatorze
wartości funkcji
D6f(x+3h) = D6f(x) + 0
D4f(x+3h) = D4f(x+2h) + D5f(x+3h)
D2 f(x+2h) = D2f(x+h) + D3f(x+2h)
f(x+h) = f(x) + Df(x+h) 		f(x+h) = f(x) + Df(x)
D2f(x) = D2f(x-h) + D3f(x-h)
D4f(x-h) = D4f(x-2h) + D5f(x-2h)
D6f(x-2h) = D6f(x-3h) + 0
Uwaga! Operacje 1,2 są wykonywane po kolei, a sumowania w
zakresie danej operacji jednocześnie

Ustawienie początkowe maszyny różnicowej równoległej

Metoda sumowania I (równoległa)

f(x) Df(x) D2f(x+h) D3f(x+h) D4f(x+2h) D5f(x+2h) D6f(x+3h)

Korzystając ze wzorów na wartości początkowe dla maszyny szeregowej (metoda I) i podstawiając dla drugiej i trzeciej różnicy x=x+h, dla czwartej i piątej różnicy x=x+2h, a dla szóstej różnicy x=x+3h otrzymujemy następujące wzory na wartości początkowe:

Df(x) = f(x) - f(x-h)
D2 f(x+h) = f(x+h) - 2f(x) + f(x-h)
D3 f(x+h) = f(x+h) - 3f(x) + 3f(x-h) - f(x-2h)
D4f(x+2h) = f(x+2h) - 4f(x+h) + 6f(x) - 4f(x-h) + f(x-2h)
D5f(x+2h) = f(x+2h) - 5f(x+h) + 10f(x) - 10f(x-h) + 5f(x-2h) - f(x-3h)
D6f(x+3h) = f(x+3h) - 6f(x+2h) + 15f(x+h) - 20f(x) + 15f(x-h) - 6f(x-2h) + f(x-3h)

Metoda sumowania II (równoległa)

f(x) Df(x-h) D2f(x-h) D3f(x-2h) D4f(x-2h) D5f(x-3h) D6f(x-3h)

Korzystając ze wzorów na wartości początkowe dla maszyny szeregowej (metoda II) i podstawiając dla pierwszej i drugiej różnicy x=x-h, dla trzeciej i czwartej różnicy x=x-2h, a dla piątej i szóstej różnicy x=x-3h otrzymujemy następujące wzory na wartości początkowe:

Df(x-h) = f(x) - f(x-h)
D2f(x-h) = f(x+h) - 2f(x) + f(x-h)
D3f(x-2h) = f(x+h) - 3f(x) + 3f(x-h) - f(x-2h)
D4f(x-2h) = f(x+2h) - 4f(x+h) + 6f(x) - 4f(x-h) + f(x-2h)
D5f(x-3h) = f(x+2h) - 5f(x+h) + 10f(x) - 10f(x-h) + 5f(x-2h) - f(x-3h)
D6f(x-3h) = f(x+3h) - 6f(x+2h) + 15f(x+h) - 20f(x) + 15f(x-h) - 6f(x-2h) + f(x-3h)

Jak widzimy, otrzymane wzory na wartości początkowe dla metody I i metody II są identyczne.

Skrótowe zestawienie informacji o maszynie różnicowej

Maszyna różnicowa-szeregowa (Metoda I)
Jeżeli oznaczymy y-6 = f(x-6h),..,y0 = f(x), to
dla próbki kolejnych wartości funkcji:

y-6, y-5, y-4, y-3, y-2, y-1, y0

początkowe wartości w punkcie y0 wynoszą
y0
D = y0 - y-1
D2 = y0 - 2y-1 + y-2
D3 = y0 - 3y-1 + 3y-2 - y-3
D4 = y0 - 4y-1 + 6y-2 - 4y-3 + y-4
D5 = y0 - 5y-1 + 10y-2 - 10y-3 + 5y-4 - y-5
D6 = y0 - 6y-1 + 15y-2 - 20y-3 + 15y-4 - 6y-5 + y-6

Obliczone wartości funkcji

y1, y2, y2, y3, ...

Sposób sumowania różnic i obliczania
kolejnych wartości funkcji

y0 D D2 D3 D4 D5 D6
5 4 3 2 1 < +
< +  
< +  
< +  
< +  
< + 6

Uwaga! Znak "<" oznacza sumator, do którego
ładowany jest wynik sumowania

Maszyna różnicowa szeregowa (Metoda II)
Jeżeli oznaczymy y0 = f(x),...,y6 = f(x+6h), to
dla próbki kolejnych wartości:

y0, y1, y2, y3, y4, y5, y6

Początkowe wartości w punkcie y0 wynoszą
y0
D = y1 - y0
D2 = y2 - 2y1 + y0
D3 = y3 - 3y2 + 3y1 - y0
D4 = y4 - 4y3 + 6y2 - 4y1 + y0
D5 = y5 - 5y4 + 10y3 - 10y2 + 5y1 - y0
D6 = y6 - 6y5 + 15y4 - 20y3 + 15y2 - 6y1 + y0

Obliczone wartości funkcji:

y1, y2, y2, y3, ...

Sposób sumowania różnic i obliczania
kolejnych wartości funkcji

y0 D D2 D3 D4 D5 D6
< + 1        
2 < +
3 < +
4 < +
5 < +
6 < +

Uwaga! Maszyna wyprowadza część
wartości z tych samych punktów x co wartości
początkowe, co może posłużyć do sprawdzenia
poprawności obliczonych wartości funkcji.

Znak "<" oznacza sumator, do którego
ładowany jest wynik sumowania

Maszyna różnicowa równoległa (Metoda I i II)
Jeżeli oznaczymy y-3 = f(x-3h),..,y0 = f(x),...,
y3 = f(x+3h), to dla próbki kolejnych wartości

y-3, y-2, y-1, y0, y1, y2, y3

początkowe wartości w punkcie y0 wynoszą
y0
D = y0 - y-1
D2 = y1 - 2y0 + y-1
D3 = y1 - 3y0 + 3y-1 - y-2
D4 = y2 - 4y1 + 6y0 - 4y-1 + y-2
D5 = y2 - 5y1 + 10y0 - 10y-1 + 5y-2 - y-3
D6 = y3 - 6y2 + 15y1 - 20y0 + 15y-1 - 6y-2 + y-3

Obliczone wartości funkcji

y1, y2, y2, y3, ...

Sposób sumowania różnic i obliczania
kolejnych wartości funkcji.
Zasada ogólna:
  1 - jednoczesne sumowanie do nieparzystych
  2 - jednoczesne sumowanie do parzystych i 0

Metoda I.

y0 D D2 D3 D4 D5 D6
3   2   1 < +
< +    
< +   
  5   4 < +  
< +    
< + 6  

Metoda II

y0 D D2 D3 D4 D5 D6
1 < +        
  2 < +
  3 < +
< + 4        
  5 < +
  6 < +

Uwaga! Maszyna wyprowadza część
wartości z tych samych punktów x co wartości
początkowe, co może posłużyć do sprawdzenia
poprawności obliczonych wartości funkcji.

Znak "<" oznacza sumator, do którego
ładowany jest wynik sumowania

Jak Maszyna Różnicowa sama oblicza różnice początkowe?

Aby maszyna mogła wyliczać kolejne wartości wielomianu, należy ustawić w sumatorach wartości początkowe liczb (różnic). Powyżej podałem wzory na obliczenie tych różnic, zarówno dla maszyny szeregowej jak i równoległej. Z drugiej strony ktoś by powiedział, co to za maszyna, skoro do jej rozruchu potrzebny jest dodatkowy kalkulator, aby wyliczyć dane początkowe. Wprowadza to utrudnienie i uzależnia pracę maszyny od człowieka. Ponadto w tych wzorach występuje operacja mnożenia, której tak bardzo starano się uniknąć przy obliczaniu wartości wielomianu.

Najlepszym wyjściem z tej nie komfortowej sytuacji jest po prostu nauczyć maszynę różnicową samej wyliczać różnice początkowe. Ponieważ maszyna składa się tylko z sumatorów, operacjami dostępnymi mogą być tylko dodawanie lub odejmowanie. Jako dane wejściowe do obliczeń posłuży (n+1) kolejnych wartości funkcji dla wielomianu n-tego stopnia.

Punktem wyjścia będzie metoda bezpośredniego obliczania różnic z n-1 kolejnych wartości funkcji. Dla ułatwienia niech n=6, a potem odkrytą regułę można rozszerzyć do dowolnego wielomianu [n].

y0
D11 =y1-y0
y1 D22 =D12-D11
D12 =y2-y1 D33 =D23-D22
y2 D23= D13-D12 D44 =D34-D33
D13 =y3-y2 D34 =D24-D23 D55 =D45-D44
y3 D24 =D14-D13 D45 =D35-D34 D66 =D56-D55
D14= y4-y3 D35= D25-D24 D56 =D46-D45
y4 D25= D15-D14 D46 =D36-D35
D15= y5-y4 D36 =D26-D25
y5 D26 =D16-D15
D16 =y6-y5
y6

Oznaczenia kolorów:
oznacza - wartość funkcji i różnice początkowe, dla sumowania w maszynie szeregowej metodą II
oznacza - wartość funkcji i różnice początkowe, dla sumowania w maszynie równoległej metodą I i II
oznacza - wartość funkcji i różnice początkowe, dla sumowania w maszynie szeregowej metodą I
oznacza - szósta różnica, która jest stała dla wielomianu n-tego stopnia

Z powyższego przedstawienia obliczania różnic początkowych wynika następujący algorytm działania sumatorów.

Obliczanie różnic początkowych w maszynie
można przedstawić następująco

Do maszyny różnicowej, jaką przedstawiono poniżej

y D D2 D3 D4 D5 D6 ... Dn-1 Dn

wstawiany kolejne wartości wielomianu:

a/ dla metody I sumowania różnic

yn yn-1 ... y6 y5 y4 y3 y2 y1 y0

b/ dla metody II sumowania różnic i metody równoległej

y0 y1 y2 y3 y4 y5 y6 ... yn-1 yn

Operacje wykonywane przez sumatory
Metoda I

kolejno n-ciągów operacji odejmowania. W każdym ciągu jest
obliczona kolejna różnica

1. Dn = Dn-1 - Dn,.., D6 = D5 - D6, D5 = D4 - D5, D4 = D3 - D4,
D3 = D2 - D3, D2 = D - D2, D = y - D

2. Dn = Dn-1 - Dn,.., D6 = D5 - D6, D5 = D4 - D5, D4 = D3 - D4,
D3 = D2 - D3, D2 = D - D2

3. Dn = Dn-1 - Dn,.., D6 = D5 - D6, D5 = D4 - D5, D4 = D3 - D4,
D3 = D2 - D3

4. Dn = Dn-1 - Dn,.., D6 = D5 - D6, D5 = D4 - D5, D4 = D3 - D4

5. Dn = Dn-1 - Dn,.., D6 = D5 - D6, D5 = D4 - D5

6. Dn = Dn-1 - Dn,.., D6 = D5 - D6
. . . . . . . . . . . . . . . . . . . . . .

n. Dn = Dn-1 - Dn
Metoda II

kolejno n-ciągów operacji odejmowania. W każdym ciągu jest
obliczona kolejna różnica

1. Dn = Dn - Dn-1,.., D6 = D6 - D5, D5 = D5 - D4, D4 = D4 - D3,
D3 = D3 - D2, D2 = D2 - D, D = D - y;

2. Dn = Dn - Dn-1,.., D6 = D6 - D5, D5 = D5 - D4, D4 = D4 - D3,
D3 = D3 - D2,D2 = D2 - D

3. Dn = Dn - Dn-1,.., D6 = D6 - D5, D5 = D5 - D4, D4 = D4 - D3,
D3 = D3 - D2

4. Dn = Dn - Dn-1,.., D6 = D6 - D5, D5 = D5 - D4, D4 = D4 - D3

5. Dn = Dn - Dn-1,.., D6 = D6 - D5, D5 = D5 - D4

6. Dn = Dn - Dn-1,.., D6 = D6 - D5
. . . . . . . . . . . . . . . . . . . . . .

n. Dn = Dn - Dn-1

Metoda równoległa I i II (dla n=6)

kolejno 6-ciągów operacji odejmowania. W każdym ciągu jest
obliczona kolejna różnica

1. r = D3,
D6 = D6 - D5, D5 = D5 - D4, D4 = D4 - D3,
D3 = D3 - D2, D2 = D2 - D, D = D - y,
y = r

2. r = D3,
D6 = D6 - D5, D5 = D5 - D4, D4 = D4 - D3,
D3 = D3 - D2, D2 = D2 - D,
D = r

3. r = D4,
D6 = D6 - D5, D5 = D5 - D4, D4 = D4 - D3,
D3 = D3 - D2,
D2 = r

4. r = D4,
D6 = D6 - D5, D5 = D5 - D4, D4 = D4 - D3,
D3 = r

5. r = D5,
D6 = D6 - D5, D5 = D5 - D4,
D4 = r

6. r = D5,
D6 = D6 - D5,
D5 = r

W celu wyłuskania wartości różnic potrzebny jest dodatkowy
rejestr - r

Podsumowanie

Maszyna różnicowa, aby obliczać kolejne wartości wielomianów dokonuje sumowania w parach przyległych sumatorów, natomiast, aby sama wyliczyć różnice początkowe i się ustawić do startu (autoinicjacja) dokonuje odejmowania w parach przyległych sumatorów.

Właściwie cecha obliczania różnic początkowych pretenduje maszynę do miana maszyny różnicowej.

Aby umożliwić zbudowanie modelu maszyny szeregowej podałem wzory wystarczające do tego celu. Wzory te umożliwiły mi zbudowanie komputerowego modelu maszyny różnicowej oraz przeprowadzenie symulacji zachowania tej maszyny, dzięki czemu mogłem sprawdzić poprawność powyższych wzorów oraz zbadać możliwości maszyny różnicowej.

Wyniki tej symulacji przedstawię w następnej części artykułu o maszynie różnicowej, ukazujące jej potężną moc. Nawiążę też do historii zbudowania pierwszej maszyny różnicowej.

Waldemar Wietrzykowski
Computational Neuroscience
Digital Intelligence Laboratory
email: mail

Zobacz też

Linki

dil

<  1  2  3  4  5  6  7  8  9  10  11  12

Copyright  © 11.11.2007 net3plus  mail