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

У меня возник вопрос, который не могу решить сам.
Суть такова, есть несократимая дробь (числитель/знаменатель), нужно сделать так, что бы числитель и знаменатель был не более чем заданное число и при этом, итоговое дробное число было как можно ближе к изначальному. На данный момент я целочисленно делю и числитель и знаменатель на 2 до тех пор(сокращая дробь по возможости), пока не будет достигнута нужная разрядность, но подозреваю, что это не самое точное решение. Если есть какие-то уже известные методики, то приветствуется любая информация.

Насколько данная операция критична по времени?
Насколько велики исходные значения числителя и знаменателя?

Цитата KIA @ 16.03.16, 05:39

У меня возник вопрос, который не могу решить сам.
Суть такова, есть несократимая дробь (числитель/знаменатель), нужно сделать так, что бы числитель и знаменатель был не более чем заданное число и при этом, итоговое дробное число было как можно ближе к изначальному. На данный момент я целочисленно делю и числитель и знаменатель на 2 до тех пор(сокращая дробь по возможости), пока не будет достигнута нужная разрядность, но подозреваю, что это не самое точное решение. Если есть какие-то уже известные методики, то приветствуется любая информация.

Не все дроби могут удовлетворять "заданному числу". Ибо может получится дробь 0/число.
Ну а методу я бы изобрел следующую, на примере ...

Пусть дано:
 
Дробь - 17/33
"Заданное число" - 3
 
int(17/3)=5
int(33/3)=11 <--- выбираем большее (11>5)
 
int(17/11)       1
------------ =  ----
int(33/11)       3

Или я не так понял задачу?

Добавлено 16.03.16, 06:53

Цитата JoeUser @ 16.03.16, 06:50

пока не будет достигнута нужная разрядность

Если все же "заданное число" - это разрядность, тогда используем для "первого деления" степень основания системы исчисления.

Воспользуйся аналогом двоичного поиска, только вместо середины отрезка бери медианту.

Добавлено 16.03.16, 06:55

Цитата JoeUser @ 16.03.16, 06:50

Ну а методу я бы изобрел следующую, на примере ...

И на твоём же примере это не работает К 17/33 ближе 2/3, а не 1/3.

Цитата JoeUser @ 16.03.16, 06:50

методу я бы изобрел следующую, на примере ...

Ну и сбойнула твоя метода - 2/3 ближе к исходнику.

Разделить числитель и знаменатель на число K (не обязательно целое) и округлить. K подбираем так, чтобы новые числитель и знаменатель удовлетворяли ограничению.

Цитата

Дробь - 17/33

"Заданное число" - 3

K=11 получим 2(1,5454545454545454545454545454545)/3

Сообщение отредактировано: Pavlovsky - 16.03.16, 07:03

OpenGL, Akina, да - согласен, неувязочка Точность хромает.

Цитата JoeUser @ 16.03.16, 07:02

Точность хромает.

Да в озвученных тобой условиях правильным ответом вообще является 1/2. То, что в результате значения числителя и знаменателя ограничены заданным значением, не запрещает им быть меньше этого предела.

Цитата Pavlovsky @ 16.03.16, 07:01

Разделить числитель и знаменатель на число K (не обязательно целое) и округлить. K подбираем так, чтобы новые числитель и знаменатель удовлетворяли ограничению.

Это не будет работать если числитель или знаменатель требуемого числа будут строго меньше ограничения. Например, для 2/7 и ограничения 6 ответ 1/4, а твоим алгоритмом - 1/3.

Добавлено 16.03.16, 07:14

Цитата Akina @ 16.03.16, 07:10

Да в озвученных тобой условиях правильным ответом вообще является 1/2.

Ха. А я-то и не заметил этого

KIA
Цепные дроби решают твою задачу оптимальным образом:

Цитата

подходящая дробь Pn/Qn является наилучшим приближением для x среди всех дробей, знаменатель которых не превосходит Qn;

Добавлено 16.03.16, 08:12
P.S. Только тебе надо уйти от начального рационального числа в сторону на небольшую величину, чтобы получить вещественное число, которое будешь приближать. То есть вместо m/n надо приближать m/n + eps, где eps подбирать экспериментально. Иначе цепная дробь быстро выродится, если число рациональное.

Цитата OpenGL @ 16.03.16, 07:13

Например, для 2/7 и ограничения 6 ответ 1/4, а твоим алгоритмом - 1/3.

1/3 (отклонение 1/21) на совсем чуть-чуть хуже чем 1/4 (отклонение 1/28).

Цитата Pavlovsky @ 16.03.16, 08:33

1/3 (отклонение 1/21) на совсем чуть-чуть хуже чем 1/4 (отклонение 1/28).

Это "чуть-чуть" можно довести до большой величины. Собственно, пример JoeUser это как раз иллюстрирует.

А где у нас топикстартер? или ему уже всё по барабану?

Цитата OpenGL @ 16.03.16, 08:52

Это "чуть-чуть" можно довести до большой величины.

Чем больше значение ограничения, чуть-чуть превратится совсем в мизерные значения.

Народ, а как вам такое:



Если я ниче не напутал с арифметикой, то останется только умножить числитель и знаменатель на нужную степень десятки, и отсечь дробную часть. Точность конечно теряется, но на пятом знаке после запятой. Че скажите, или опять шило?

Цитата JoeUser @ 16.03.16, 12:18

Че скажите, или опять шило?

Шило. Тут уже два простых метода описали, дающие 100% точность. Зачем ещё один, да ещё сложный и неточный?

Цитата OpenGL @ 16.03.16, 12:34

Тут уже два простых метода описали, дающие 100% точность.

Хотелось бы лицезреть "простоту" и "100% точность" на каком-нить примере, хотя бы 17/33.

Да на самом деле задача всё равно переборная получается.

Имеется M/N. Допустим, M<N. Необходимо найти ближайшую дробь, знаменатель которой не превышает K. Решение - для всех X от K до 2 рассчитать ближайшую дробь (числитель = INT(M*X/N), отклонение = M/N - INT(M*X/N)/X, где INT - математическое округление), и выбрать X, для которого ABS(отклонение) минимален.

Единственная зримая оптимизация - это при переборе (в сторону уменьшения) можно не проверять значения X, являющиеся делителями ранее проверенных.

Проблема метода - в точности вычислений.

Сообщение отредактировано: Akina - 16.03.16, 13:06

Цитата OpenGL @ 16.03.16, 07:13

Например, для 2/7 и ограничения 6 ответ 1/4

Нашел калькулятор логарифмов с нормальной точностью:

2/7 = 2^log2(2)/2^log2(7) = 2^1/2^2.8073549221 = 1/3.5000000001

Получите: 1/4

Цитата JoeUser @ 16.03.16, 12:52

Хотелось бы лицезреть "простоту" и "100% точность" на каком-нить примере, хотя бы 17/33.

А зачем? Видно, что это наколеночный велосипед, мало отличающийся от велосипеда Pavlovsky - то же самое деление числителя и знаменателя на одно и то же число. При наличии точных методов смысла в нём нет.

Простой брутфорс:

num=17 'числитель
den=33 'знаменатель
max=8  'предел
 
div=num/den
er=max
nn=0
dd=0
for n=1 to max
  d=clng(n/div)
  if d<=max then
    if er>abs(n/d-div) then
      er=abs(n/d-div)
      nn=n
      dd=d
    end if
  end if
next
 
msgbox cstr(nn) & "/" & cstr(dd)

Это VBScript, просто сохраните это в текстовый файл с расширением .vbs и запускайте.

Сообщение отредактировано: Mikle - 16.03.16, 13:25

Спасибо за цепные дроби, ещё не успел почитать, но уже вижу что в эту сторону стоит покопать.
По поводу разрядностей и величин, всё очень просто, я сделал библиотеку для работы с дробями (из спортивного интереса) и, естественно в любых вычислениях без квадратного корня - никуда. Но оказалось, что дроби настолько быстро растут, что 64 битные значения перекрываются на раз.
Перекрывается не просто дробь, а в момент сложения там получается числитель*знаменатель + числитель*знаменатель и результат очень большой и никуда уже не лезет. При этом, метод Ньютона может отталкиваться от любых значений и будет двигаться в правильном направлении, но очень трудно бороться с переполнениями.

Например, корень из 99999:
1250049999/50000 = 25000,99998
646907007/51742 = 12502,5512543002
902980466/144355 = 6255,27668594784--где-то тут уже начались приближённые дроби
1181194331/376700 = 3135,63666312716
2133521117/1347120 = 1583,76471064196
1783350728/2165699 = 823,452718036994
311071000/658427 = 472,44569253691
16599542/48529 = 342,054070761813
1641681305/5175518 = 317,201351632822
1401161871/4430864 = 316,227686293238
316/1 = 316 -- Тут отдельне условие сработало, для точного извлечения целых корней.
199855/632 = 316,226265822785
998550270/3157709 = 316,226184870107
58698221/185621 = 316,226186692238
657173372/2078175 = 316,226194617874
156455779/494759 = 316,226241463015
778147583/2460731 = 316,226187665373
364559862/1152845 = 316,226259384393

Восемь девяток 99999999

1589457257/63 = 25229480,2698413
418287974/33 = 12675393,1515152
1738120497/274 = 6343505,46350365--Тут пошли приближения
333462641/105 = 3175834,67619048
1683287173/1060 = 1588006,76698113
1513894167/1906 = 794278,156873033
564460402/1421 = 397227,587614356
1452190873/7307 = 198739,684275352
700088857/7027 = 99628,4128362032
953794307/18956 = 50316,2221460224
1043806002/39913 = 26152,0307168091
1550758537/103467 = 14987,9530381668
1285396173/118688 = 10830,0432478431
723990051/72169 = 10031,8703459934
865304829/86530 = 10000,0558072345
1763116023/176311 = 10000,0341612265
1444717817/144471 = 10000,0541077448
647951621/64795 = 10000,0250173625
1722111243/172211 = 10000,0072178897
1478838442/147883 = 10000,0570856691
1810450224/181045 = 10000,0012372615
173690046/17369 = 10000,0026483966
327870773/32787 = 10000,0235764175
1518800379/151880 = 10000,0024953911
1697447567/169744 = 10000,0445788953
357791208/35779 = 10000,0337628218
2067026865/206702 = 10000,0332120637
1676812917/167681 = 10000,0173961272
193970116/19397 = 10000,0059803062
1288670094/128867 = 10000,0007294342
733212401/73321 = 10000,0327464164
731114490/73111 = 10000,0614134672
1665891734/166589 = 10000,0104088505
112930094/11293 = 10000,0083237404
1430869994/143087 = 9999,99995806747
9999/1 = 9999
10000/1 = 10000
199999999/20000 = 9999,99995
10000/1 = 10000
199999999/20000 = 9999,99995
10000/1 = 10000
--Тут метод зацикливается,потому что не может два раза подряд получить правильный корень 9999,99995

Корень из 2
1/1 = 1
3/2 = 1,5
17/12 = 1,41666666666667
577/408 = 1,41421568627451
665857/470832 = 1,41421356237469
941664/665857 = 1,4142135623715
941664/665857 = 1,4142135623715
Как видно мы даже не достигли точности виндового калькулятора.

А вот что будет, если не бороться с переполнением:
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 = 0,265130160286813--Это уже всё, того, дальше портянку не показываю

Видно, что уже третья итерация уходит в переполнение, а погрешности приведённых дробей столь высоки что не смотря на всю мощь сверхсходимого метода касательных, точность в дробной части вообще не растёт.
На всякий случай формула x = (x_old + x_start/x_old)/2

Цитата KIA @ 16.03.16, 13:22

Например, корень из 99999:
1250049999/50000 = 25000,99998
646907007/51742 = 12502,5512543002
902980466/144355 = 6255,27668594784--где-то тут уже начались приближённые дроби
1181194331/376700 = 3135,63666312716
2133521117/1347120 = 1583,76471064196
1783350728/2165699 = 823,452718036994
311071000/658427 = 472,44569253691
16599542/48529 = 342,054070761813
1641681305/5175518 = 317,201351632822
1401161871/4430864 = 316,227686293238
316/1 = 316 -- Тут отдельне условие сработало, для точного извлечения целых корней.
199855/632 = 316,226265822785
998550270/3157709 = 316,226184870107
58698221/185621 = 316,226186692238
657173372/2078175 = 316,226194617874
156455779/494759 = 316,226241463015
778147583/2460731 = 316,226187665373
364559862/1152845 = 316,226259384393

Виндовый калькулятор считает, что sqr(99999) = 316,22618487405498217065397744334.
Простейший код даёт 303068962 / 958393 = 316,22618487405479797953449159165 - т.е. различие в 13-м знаке после запятой. И это я работал в вульгарных Double и знаменатель не более 1 000 000.

Скрытый текст

Dim num As Double
Dim sqrt As Double
Dim i As Double
Dim j As Double
Dim delta As Double
Dim curdelta As Double
num = Val(Text1.Text) ' Число для извлечения кв. корня
sqrt = Math.sqr(num)
Text2.Text = sqrt ' Расчётный корень в точности Double
curdelta = 1000
For i = 2 To 1000000
    j = Math.Round(i * sqrt)
    delta = Math.Abs(sqrt - j / i)
    If delta < curdelta Then
        curdelta = delta
        Text4.Text = j ' Числитель
        Text5.Text = i ' Знаменатель
        Text3.Text = j / i ' Значение дроби
    End If
Next i

Если увеличить диапазон ещё на порядок, то результат 1714254875 / 5420977 = 316,22618487405499045651733995551 - т.е. различие в 14 знаке.

Добавлено 16.03.16, 14:19
Хотя я не понимаю, как извлечение корней соотносится с "псевдо-сокращением".

Сообщение отредактировано: Akina - 16.03.16, 14:19

Цитата Akina @ 16.03.16, 14:03

Простейший код даёт 303068962 / 958393 = 316,22618487405479797953449159165 - т.е. различие в 13-м знаке после запятой. И это я работал в вульгарных Double и знаменатель не более 1 000 000.

Но я-то ничего не выдумываю, вычисления по Ньютону дают именно такие большущие несократимые дроби и именно числа с плавающей точкой тут и планируется заменить. Можно на пальцах проверить на корне из двух (вот ссылка на описание, если кому-то мало формулы http://mech.math.msu.su/~shvetz/54/inf/per...ot_sIdeas.xhtml):

M

Ссылочку поправил

x_start = 2
x_old = 17/12

x = (17/12 + 2/17/12)/2=(17*17/12*17+24*12/17*12)/2=(289/204+288/204)/2=577/408 выше в выкладках именно такой результат.

давайте для x_old = 886731088897/627013566048

x = (886731088897/627013566048 + 2/886731088897/627013566048)/2=(786292024016459316676609/555992422174934068969056 + 786292024016459316676608/555992422174934068969056)/2=1572584048032918633353217/1 111 984 844 349 868 137 938 112 второе число уже в int64 не лезет, вручную сокращение делать не буду. = 1,4142135623730950488016887242097, что похоже на правду (инженерный калькулятор даёт в точности такое же значение, то есть метод Ньотона работает очень хорошо сам по себе).
Формула для вычисления корня тут фигурирует, на самом деле, только для иллюстрации. В формуле вычисления ничего сверхсложного нет, она - элементарна, но порождает очень большие числа в числителях и знаменателях. Если использовать дроби в практических целях, то это же будет на каждом шагу. Получается, что вести точные расчёты дробями (плавающая точка это всегда потеря точности), не получается.
Отсюда и возник вопрос - хорошо, не получается сохранить точность, двайте получим какое-нибудь приближение, причём такое, что бы ни числитель ни знаменатель не были больше чем сколько-то разрядов, что бы с этими дробями можно было произвести ещё какие-нибудь вычисления и результат бы поместился в int64 (9 223 372 036 854 775 807). Инт это 18-19 разрядов, у нас же уже на представленной итерации 25.
Ну а уже когда получим приближение, посмотреть насколько страдает точность и есть ли какие-нибудь хотя бы гипотетические преимущества перед плавающей точкой. При этом исследуя проблему, я наталкнулся на мнение, что такие большие несократимые дроби в вычислениях, вообще говоря - не характерны, а получаются именно при попытке приближения к иррациональным числам.

Сообщение отредактировано: JoeUser - 16.03.16, 23:50

Цитата KIA @ 16.03.16, 20:33

вести точные расчёты дробями (плавающая точка это всегда потеря точности), не получается.
Отсюда и возник вопрос - хорошо, не получается сохранить точность, двайте получим какое-нибудь приближение, причём такое, что бы ни числитель ни знаменатель не были больше чем сколько-то разрядов, что бы с этими дробями можно было произвести ещё какие-нибудь вычисления и результат бы поместился в int64

Ограничивая разрядность операнда, мы точно так же ограничиваем и точность. Так что если нужны точные расчёты, надо не в дроби лезть, а в "сверхдлинную" математику. Которая, кстати, в системе уже имеется - см. напр. Длинная арифметика от Microsoft.

Длинная арифметика никак не поможет описать бесконечные дроби, и (1/3)*3 не будет равно еденице. Собственно полно примеров подобных казусов на обычных числах с плавающей точкой, так же всевозможные итеративные функции накапливают ошибки вподь до того, что сходящийся ряд превращается в расходящийся, у дробей таких проблем нет, во многих случаях вычисления будут происходить абсолютно точно. Дроби это расширение чисел до рациональных, к сожалению ещё остаётся класс иррациональных чисел и их реализация на компьютере становится уж очень не удобной и медленной, из-за того, что там, фактически, придётся держать список многочленов, в дробях же всегда достаточно только числителя и знаменателя. Разрядность мы ограничиваем не конечной величины, а составных частей дроби и имея знаменатель в 18 разрядов, можно достичь точости в 18 знаков после запятой, как видно из примеров, проблема как раз в том, что в вычислениях очень резко растёт точность и получается, что после 13 знаков получаем 25, вот эти 25 можно огрубить до 18 и на этом остановиться.

Кстати, в вашем же примере: 303068962 / 958393, знаменатель всего 6 знаков а точность 13, так что хорошая технология для приведения дроби может дать весьма хороший результат.

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

Длинная математика поможет работать с дробями без ограничения значений числителя и знаменателя - т.е. с любой (в разумных пределах) требуемой точностью.

Цитата Pacific @ 16.03.16, 08:08

KIA
Цепные дроби решают твою задачу оптимальным образом:

Не так. При заданных ограничениях на числитель и знаменатель, довольно часто можно подобрать приближение лучше

Цитата KIA @ 17.03.16, 10:59

Кстати, в вашем же примере: 303068962 / 958393, знаменатель всего 6 знаков а точность 13, так что хорошая технология для приведения дроби может дать весьма хороший результат.

Akina прав.

Цитата Akina @ 17.03.16, 13:01

Длинная математика поможет работать с дробями без ограничения значений числителя и знаменателя - т.е. с любой (в разумных пределах) требуемой точностью.

При сознательном занижении точности - каждая последующая операция будет только "накапливать" неточность, причем накопление пойдет в сторону уменьшения количества правильных значащих цифр. ИМХО, это тупиковый вариант. Длинная математика это решит.

Как вариант, вижу - представление чисел в виде динамических битовых массивов и выполнение операций над ними. Для ускорения операций умножения/деления рекомендую прочесть дисциплину "Прикладная теория цифровых автоматов" (ссылка навскидку). Типа умножение на два разряда одновременно, матричное умножение ... В свое время изучал этот мозговынос, в диплом оценка не попала (сдал экзамен, но перевелся), однако содержание курса помню.

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

Пусть наша дробь x (неважно, чем она является дробью или вещественным числом) лежит в интервале между соседними целыми числами n1 и n2
d1 = d2 = 1.
Имеем n1/d1 < x < n2/d2

А далее в цикле
Формируем новое приближение (n1+n2)/(d1+d2) Это число удовлетворяет неравенству n1/d1 < (n1+n2)/(d1+d2) < n2/d2 и имеет наименьшие числитель и знаменатель среди всех рациональных чисел, лежащих в этом промежутке
Если эта дробь не удовлетворяет ограничениям, значит в качестве результата приближения выбираем ту границу, которая ближе к приближаемому числу.
Иначе сдвигаем одну из старых границ и формируем следующее приближение.

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

Это реально работает!
Согласно методу Ньютона или формуле Герона, мы как раз получаем приближение то с одной, то с другой стороны, поэтому можно взять любые два последовательно полученных числа. Ещё раз проиллюстрирую действия для корня из двух:
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

Цитата 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 или выделить целую и дробную части и для дробной воспользоваться вышеуказанным алгоритмом.

Цитата 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 битах ошибка уменьшается аж на два порядка