Приближённое сокращение дроби.

[KIA]

Это реально работает!
Согласно методу Ньютона или формуле Герона, мы как раз получаем приближение то с одной, то с другой стороны, поэтому можно взять любые два последовательно полученных числа. Ещё раз проиллюстрирую действия для корня из двух:
1/1 = 1
3/2 = 1,5
17/12 = 1,41666666666667
577/408 = 1,41421568627451
665857/470832 = 1,41421356237469
886731088897/627013566048 = 1,4142135623731
575684128022077/2171326443582699

Берём 665857/470832 и 886731088897/627013566048 и получаем (665857+886731088897)/(470832+627013566048) = 768398401/543339720 = 1,4142135623731

То есть, дробь 886731088897/627013566048 привели к более простой 768398401/543339720

Вопрос только вот по этой фразе "имеет наименьшие числитель и знаменатель среди всех рациональных чисел, лежащих в этом промежутке", есть где-нибудь доказательство?

Сообщение отредактировано: KIA - 17.03.16, 19:35

[OpenGL]

Цитата amk @ 17.03.16, 14:16

Точный алгоритм что-то не увидел.

Я его кратко описал ещё на первой странице

Цитата KIA @ 17.03.16, 19:33

Вопрос только вот по этой фразе "имеет наименьшие числитель и знаменатель среди всех рациональных чисел, лежащих в этом промежутке", есть где-нибудь доказательство?

Для двух произвольных дробей это неверно - между 4/9 и 11/18, например, есть дробь 1/2, а медианта при этом равна (4 + 11) / (9 + 18) = 15/27=5/9. Но для дробей, являющимися соседними в ряде Фарея это верно. Т.е, например, если дробь, которую ты приближаешь, находится в интервале от 0 до 1, то можно в качестве границ взять 0/1 и 1/1. Если нет, то в качестве второй границы можно взять "псевдо-дробь" 1/0 или выделить целую и дробную части и для дробной воспользоваться вышеуказанным алгоритмом.

[amk]

Цитата KIA @ 17.03.16, 19:33

Вопрос только вот по этой фразе "имеет наименьшие числитель и знаменатель среди всех рациональных чисел, лежащих в этом промежутке", есть где-нибудь доказательство?

Цитата OpenGL @ 17.03.16, 20:03

Но для дробей, являющимися соседними в ряде Фарея это верно.

Правильное замечание. Просто забыл об этом написать. Что границы промежутка, всегда соседние числа Фарея.

OpenGL, я видимо твоё описание прозевал.

Цитата KIA @ 17.03.16, 19:33

Это реально работает!

Работает. И приближение в некотором смысле получается лучше, чем в описанном методе. Но иногда, можно получить дробь с немного большим знаменателем, которая ближе к заданному числу.
Например, подходящие дроби для числа π: 3/1, 22/7, 333/106, 355/113, 103993/33102...
Если, например, ограничить знаменатель числом 32767, то лучшей из подходящих дробей будет широко известная 355/113, имеющая ошибку 2.7e-07.
А наилучшим при таком ограничении будет 102928/32763 с ошибкой -3.3e-09.

Однако надо заметить, что какого-то улучшения удаётся добиться только при знаменателях длиной 6, 15, 20, и 24 бита, и только при 15 битах ошибка уменьшается аж на два порядка