АЛГОРИТМ ЕВКЛИДА

Алгоритм Евклида для целых чисел Проще сформулировать алгоритм Евклида так: если даны натуральные числа a и b и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится наибольший общий делитель gcd (НОД). Отношение a/b представимо в виде цепной дроби q0+1/(q1+ ...) от кратностей, образующихся при вычитании, на последнем месте размещается НОД.


a=225, b=10, f=fractions2(a b), f=?,

function: fractions2(a b),
var q r R f, if b=0, f=[a 0], 
else, R=b, r=b, f=b,
while r>0, q=floor(a/b), f={[f q]},  
R=r, r=a-q*b, if r>0, a=b, b=r, end, end,
f=block(f 1 size(f)), f={[f R]}, end,
return f,
end,

function: gcd(a b),
var q r R f, 
if b=0, R=a, else, R=b, r=b, 
while r>0, q=floor(a/b), 
R=r, r=a-q*b, if r>0, a=b, b=r, end, end,
end, return R,
end,

Древнегреческие математики называли этот алгоритм ἀνθυφαίρεσις или ἀνταναίρεσις — «взаимное вычитание». Этот алгоритм не был открыт Евклидом, так как упоминание о нём имеется уже в Топике Аристотеля. В «Началах» Евклида он описан дважды — в VII книге для нахождения наибольшего общего делителя двух натуральных чисел и в X книге для нахождения наибольшей общей меры двух однородных величин. В обоих случаях дано геометрическое описание алгоритма, для нахождения «общей меры» двух отрезков.

Историками математики (Цейтен и др.) было выдвинуто предположение, что именно с помощью алгоритма Евклида (процедуры последовательного взаимного вычитания) в древнегреческой математике впервые было открыто существование несоизмеримых величин (стороны и диагонали квадрата, или стороны и диагонали правильного пятиугольника). Впрочем, это предположение не имеет достаточных документальных подтверждений. Алгоритм для поиска наибольшего общего делителя двух натуральных чисел описан также в I книге древнекитайского трактата Математика в девяти книгах.

Ряд математиков средневекового Востока (Сабит ибн Курра, ал-Махани, Ибн ал-Хайсам, Омар Хайям) попытались построить на основе алгоритма Евклида теорию отношений, альтернативную по отношению теории отношений Евдокса, изложенной в V книге «Начал» Евклида. Согласно определению, предложенному этими авторами, четыре величины, первая ко второй и третья к четвёртой, имеют между собой одно и то же отношение, если при последовательном взаимном вычитании второй величины в обеих парах на каждом шаге будут получаться одни и те же неполные частные.

Разложение числа Число x представимо в виде цепной дроби от целых частей [1/r] инверсных остатков q0=[1/x], q1=[1/(x-q0)], ...


x=567/56, f=fractions(x), f=?,

function: fractions(x),
var q r f, r=x, q=floor(x), 
f=q, r=r-q, for var i=0:20, 
if r>0.0000001, r=1/r, q=floor(r), 
f={[f q]}, r=r-q, else, break, end, 
end, return f,
end,

Подходящая дробь Подходящей дробью назывется конечная цепная дробь длиною n, задающая число рациональным приближением. Эйлер вывел рекуррентные формулы для вычисления числителя a и знаменателя b подходящей дроби

a-1=1, a0=q0, an=qnan-1+an-2, b-1=0, b0=1, bn=qnbn-1+bn-2.


%РАЗЛОЖЕНИЕ В ЦЕПНУЮ ДРОБЬ,
x=PI, f=fractions(x), 
% ПОДХОДЯЩЕЕ РАЦИОНАЛЬНОЕ ЧИСЛО a/b, 
n=2,  
a=rational2(f 1 n), b=rational2(f 0 n), 
[a b]=?, [x a/b]=?, f=?,

function: rational2(f b n),
var i n r a b, 
if typeof(f)=typeof(2), 
if b>0, a=f, else, a=1, end, else, 
if n>size(f), n=size(f), end,
if b>0, a=f[0], else, a=1, end,
for i=1:n, r=f[i]*a+b, 
b=a, a=r, end, end, 
return a,
end, 

function: fractions(x),
var q r f, r=x, q=floor(x), 
f=q, r=r-q, for var i=0:20, 
if r>0.0000001, r=1/r, q=floor(r), 
f={[f q]}, r=r-q, else, break, end, 
end, return f,
end,

Цепная дробь является периодической тогда и только тогда, когда число является квадратичной иррациональностью, т.е. имеет форму (a+b√c)/d, где c не является точным квадратом.

Можно сравнить цепную дробь для π в альфе

Вопрос возникает, как по 9.6603 вылавливается квадратичная иррациональность 1+5√3, ведь периодичность не проверить. Кстати, радикал из пяти, имеет более быструю сходимость, чем корни квадратные из 2, 3 и 7.

Начнем с простого √2=1.4142136... видна неустойчивость фракций (не 2)


x=sqrt(2), x=1.4142136,
f=fractions(x), x=restore(f), f=?, x=?,

function: fractions(x),
var q r f, r=x, 
q=floor(x), f=q, r=r-q, 
for var i=0:20, if r>0.0000001, 
r=1/r, q=floor(r), f={[f q]}, r=r-q, 
else, break, end, end, return f,
end,

function: restore(f),
var i n, if typeof(f)=typeof(2), 
x=f, else, n=size(f), x=f[n], 
n=n-1, for i=n:-1:0, x=f[i]+1/x, end,
end, return x,
end,

Периодичность: √2 - 2; √3 - 1,2; √5 - 4; √6 - 2,4; √7 - 1,1,1,4; √8 - 1,4; √10 - 6; √11 - 3,6.

ТУЛБОКС NUMBERS

Тулбокс numbers включает в себя операции разложения на фракции рациональных и вещественных чисел на основе алгоритма Евклида, а также переборный алгоритм аппроксимации числа иррациональным выражением, позволяющим найти формулы для уровней M-матриц, совпадающие с итогом аналитического исследования.

M7 Применим алгоритм иррациональной аппроксимации для оценки формулы для уровня M-матрицы седьмого порядка

a:b:c:d:1=0.1771:0.2152:0.6076:0.8229:1

Связи a=1/(3+√7), b=a/(1-a)=a/d, с=1-a-b=d-b, d=1-a, m=1/√(a2+b2+5), справедлива оценка нормы m=(5+7*√(7))/53=0.444.


%toolbox numbers, n=7, 
x=0.1771, q=sqrt(n), abс=irrapp(1/x q 30), abс=?, 
% оценка x=с/(a+bq)=1/(3+√7)



Rambler's Top100