Машинное эпсилон может быть вычислено с помощью следующей программы:

{ Машинное Эпсилон: eps= min [ epsil | 1+epsil>1 ] }

type

MyReal =Single {Real} {Double} {Extended}; {Варианты вещ. типов}

var eps,

epsP1,

epsil,

epsilP1 : MyReal;

i : Integer;

fout : Text;

begin

Assign (fout, 'single.eps'); Rewrite(fout);

{С учетом варианта вещ.типов}

WriteLn(fout,'Вариант вещественного типа: Single');

i := 0;

eps := 1.0;

epsP1 := 2.0;

while epsP1 > 1.0 do

begin {eps=2^(-i) & (1+eps>1)}

eps := eps * 0.5;

epsP1 := eps + 1.0;

i := i + 1;

WriteLn(fout,'<',i:2,'> eps : ', eps,' 1 + eps :', epsP1:26);

{eps=2^(-i) & (1+eps=>1) & (1+2*eps>1}

end {while};

{eps=2^(-i) & (1+eps=1) & (1+2*eps>1}

epsil := 2.0 * eps;

epsilP1 := epsil + 1.0;

WriteLn(fout,'Stop :');

WriteLn(fout,'Эпсилон/2: ', eps,' 1+ эпс/2:', epsP1:26);

WriteLn(fout,'Эпсилон : ',epsil,' 1+ эпс :',epsilP1:26);

WriteLn(fout,'Сравните : 1 + Эпсилон/2(Extended) :', 1.0+eps:26);

Close (fout);

end.

При выполнении задания в качестве параметра точности следует использовать значение, определяемое с помощью eps..

----------------------------------------

Модифицировав программу для вычисления eps, можно определить и фактическую разрядность мантиссы (с учётом неявного бита и корректно обращаясь с результатами округления) для каждого из типов Single, Real, Double, Extended. Это осуществляется с помощью следующей программы:

type

Float = Single { Real} {Double} {Extended};{ Change me ! }

var eps,

epsP1,

epsil,

epsilP1 : Float;

i : Integer;

fout : Text;

b1, b2 : Boolean;

begin

Assign (fout, 'eps2Sng5.dat');

Rewrite(fout);

WriteLn(fout,'Single ...'); { Change me ! }

i := 0;

eps := 1.0;

epsP1 := 2.0;

b1 := true;

b2 := true;

while b1 and b2 do

begin

eps := eps * 0.5;

epsP1 := eps + 1.0;

i := i + 1;

b1 := (epsP1 > 1.0);

b2 := (epsP1-eps = 1.0);

WriteLn(fout,'<',i:2,'> eps : ', eps,' 1 + eps :', epsP1:26);

end {while};

epsil := 2.0 * eps;

epsilP1 := epsil + 1.0;

WriteLn(fout,'Stop : b1 =', b1, ' b2 =', b2);

WriteLn(fout,'Stop :: 1 + eps- (в регистрах) :', 1.0+eps:26);

WriteLn(fout,'Stop :: (1 + eps-) - eps- :', epsP1-eps :26);

WriteLn(fout,'Stop :: (1 + eps+) - eps+ :', epsilP1-epsil :26);

Close (fout);

end.

Билет №9 Общая схема итерации и №9 рекуррентные вычисления

Многие вычисления укладываются в следующую схему:

x:=x0;

while B(x) do x:=f(x); (2.1)

где x – мн-во переменных программы, x0 – их начальные значения, B(x) – булевская ф-ция (предикат) от переменных x, а f – ф-ция. В соответствии с семантикой цикла while–do предикат B(x) – условие продолжения цикла.

Схему (2.1) иногда называют схемой итерации (от латинского iteratio –повторение), а отдельные шаги цикла — итерациями.

Выбирая различные x, B и f, получим из схемы (2. 1) различные конкретные программы.

Например, полагая x=<u,v>, x0=<a,b>, ,,

получим известный алгоритм Евклида вычисления наибольшего общего делителя (НОД) чисел a и b:

var a, b, u, v, r: Integer;

…

{(a>0) & (b>0)}

u:=a; v:=b;

while v0 do

begin

r:=u mod v;

u:=v;

v:=r

end {u=НОД(a,b)}

Действительно, пусть цикл while-do в (2.1) завершился за n шагов и переменные x принимали последовательно значения, x₀, x₁, …, x_n – 1, x_n, тогда последовательность x_i (i  [0; n]) обладает свойствами:

1. x_i = f(x_i – 1) для всех i  [1; n];

2. x

   (2. 2)

   _i ≠ x_j при i ≠ j и i, j  [0; n]; (2.2)

3. B(x_i) для всех i  [0; n – 1]);

4. not B(x_n).

Свойство 1 следует из семантики оператора присваивания x:=f(x).

Свойство 2 выражает необходимое условие завершения цикла.

Свойства 3 и 4 следуют из семантики конструкции цикла while-do. Итерации заканчиваются, если существует n, соответствующее свойству 4. При этом значение n является наименьшим из всех таких значений, что определяется свойством 3.

Иногда свойства (2.2) схемы (2.1) рассматривают как “Теорему о линейном просмотре” поскольку такая программа осуществляет поиск среди значений x₀, x_i = f(x_i – 1), i > 0 значения x_i с минимальным индексом i ≥ 0, при котором истинно not B(x_i).