Wojciech "Spook" Sura wrote:
> Witam!
>
> Zastanawiam się, w jaki sposób porównywać ułamki zwykłe?
>
> Przypuśćmy, że mam dane dwa ułamki, a/b i c/d. Chcę sprawdzić, czy są
> równe.
>
> 1. Metoda brutalna:
>
> float f1 = a/b;
> float f2 = c/d;
> return f1 == f2;
>
> f1 == f2 wygląda jak herezja, ale weźmy pod uwagę, że operacje
> zmiennoprzecinkowe są wykonywane deterministycznie i jeśli ułamki
> faktycznie są równe, warunek będzie spełniony. Niestety, nie mamy tu
> równoważności: być może bowiem uda się znaleźć inny ułamek zwykły, który
> da w wyniku taką samą liczbę zmiennoprzecinkową, ale wynikłą z
> niedoskonałości zapisu zmiennoprzecinkowego. Najwyraźniej więc metoda
> nie jest zbyt skuteczna.
>
> 2. Wspólny mianownik
>
> int tmpGCD = GCD(b, c);
>
> return (a * (d / tmpGCD)) == (c * (b / tmpGCD));
>
> Problem pojawi się wówczas, gdy złośliwie podrzucimy dwa ułamki o dużych
> mianownikach, których GCD wynosi 1, na przykład 1/2147483629 i
> 1/2147483647. Ich wspólnym mianownikiem jest 4611685977625198592, co
> oczywiście wykracza poza zakres long int. Co więcej, jedynym znanym mi
> sposobem na sprawdzenie, czy iloczyn dwóch liczb mieści się w zakresie
> inta jest przypisanie go do zmiennej typu double i porównanie z
> największym możliwym intem wyciągniętym z std::limits. Nie jest to zbyt
> wydajne rozwiązanie...
>
> Czy macie może jakiś lepszy pomysł?
>
> Pozdrawiam -- Spook.
>
Zakładam, że a,b,c,d są typu int,
oraz ułamek to uporządkowana para, czyli A = (a,b), B=(c,d),
czyli (w pseudokodzie)
struct fraction {int nominator, int denominator};

Wtedy:
a/b < c/d <=> a*d < c*b

W pseudokodzie funkcja, którą można użyć do sortowania będzie:

boolean compare(struct fraction A, struct fraction B) {
long left = (long)A.nominator * (long)B.denominator;
long right = (long)A.denominator * (long)B.nominator;
if(left<right) return -1;
if(left>right) return 1;
return 0;
}

Coś więcej potrzeba?

j..

do góry

Witam!

Zastanawiam się, w jaki sposób porównywać ułamki zwykłe?

Przypuśćmy, że mam dane dwa ułamki, a/b i c/d. Chcę sprawdzić, czy są
równe.

1. Metoda brutalna:

float f1 = a/b;
float f2 = c/d;
return f1 == f2;

f1 == f2 wygląda jak herezja, ale weźmy pod uwagę, że operacje
zmiennoprzecinkowe są wykonywane deterministycznie i jeśli ułamki
faktycznie są równe, warunek będzie spełniony. Niestety, nie mamy tu
równoważności: być może bowiem uda się znaleźć inny ułamek zwykły, który
da w wyniku taką samą liczbę zmiennoprzecinkową, ale wynikłą z
niedoskonałości zapisu zmiennoprzecinkowego. Najwyraźniej więc metoda nie
jest zbyt skuteczna.

2. Wspólny mianownik

int tmpGCD = GCD(b, c);

return (a * (d / tmpGCD)) == (c * (b / tmpGCD));

Problem pojawi się wówczas, gdy złośliwie podrzucimy dwa ułamki o dużych
mianownikach, których GCD wynosi 1, na przykład 1/2147483629 i
1/2147483647. Ich wspólnym mianownikiem jest 4611685977625198592, co
oczywiście wykracza poza zakres long int. Co więcej, jedynym znanym mi
sposobem na sprawdzenie, czy iloczyn dwóch liczb mieści się w zakresie
inta jest przypisanie go do zmiennej typu double i porównanie z
największym możliwym intem wyciągniętym z std::limits. Nie jest to zbyt
wydajne rozwiązanie...

Czy macie może jakiś lepszy pomysł?

Pozdrawiam -- Spook.

--
! ._______. Warning: Lucida Console sig! //) !
! || spk || www.spook.freshsite.pl / _ """*!
! ||_____|| spook at op.pl / ' | ""!
! | ___ | tlen: spoko_ws gg:1290136 /. __/"\ '!
! |_|[]_|_| May the SOURCE be with you! \/) \ !

do góry

Wojciech "Spook" Sura pisze:
> Witam!
>
> Zastanawiam się, w jaki sposób porównywać ułamki zwykłe?
>
> Przypuśćmy, że mam dane dwa ułamki, a/b i c/d. Chcę sprawdzić, czy są
> równe.
>
> 1. Metoda brutalna:
>
> float f1 = a/b;
> float f2 = c/d;
> return f1 == f2;
>
> f1 == f2 wygląda jak herezja, ale weźmy pod uwagę, że operacje
> zmiennoprzecinkowe są wykonywane deterministycznie i jeśli ułamki
> faktycznie są równe, warunek będzie spełniony. Niestety, nie mamy tu
> równoważności: być może bowiem uda się znaleźć inny ułamek zwykły, który
> da w wyniku taką samą liczbę zmiennoprzecinkową, ale wynikłą z
> niedoskonałości zapisu zmiennoprzecinkowego. Najwyraźniej więc metoda
> nie jest zbyt skuteczna.
>
> 2. Wspólny mianownik
>
> int tmpGCD = GCD(b, c);
>
> return (a * (d / tmpGCD)) == (c * (b / tmpGCD));
>
> Problem pojawi się wówczas, gdy złośliwie podrzucimy dwa ułamki o dużych
> mianownikach, których GCD wynosi 1, na przykład 1/2147483629 i
> 1/2147483647. Ich wspólnym mianownikiem jest 4611685977625198592, co
> oczywiście wykracza poza zakres long int. Co więcej, jedynym znanym mi
> sposobem na sprawdzenie, czy iloczyn dwóch liczb mieści się w zakresie
> inta jest przypisanie go do zmiennej typu double i porównanie z
> największym możliwym intem wyciągniętym z std::limits. Nie jest to zbyt
> wydajne rozwiązanie...
>
> Czy macie może jakiś lepszy pomysł?

Jesli sprawdzasz tylko równość, to w zasadzie szukając największych
wspólnych dzielników licznika i mianownika każdego z ułamków, powinieneś
obie liczby sprowadzić do tej samej postaci....



--
Kaczus
http://kaczus.republika.pl
http://kaczanowska.info

do góry

epsilon$ while read LINE; do echo \>"$LINE"; done < "Wojciech "Spook" Sura"
>Witam!
>
>Zastanawiam się, w jaki sposób porównywać ułamki zwykłe?
>
>Przypuśćmy, że mam dane dwa ułamki, a/b i c/d. Chcę sprawdzić, czy są
>równe.

Rozwiązanie pewne, acz niespecjalnie wydajne - skrócić oba.

--
Kruk@ -\ |
}-> epsilon.eu.org |
http:// -/ |
|

do góry

On 21 Wrz, 11:45, "Wojciech \"Spook\" Sura" <spook"mad@hatter"op.pl>
wrote:
> 1. Metoda brutalna:
>
> float f1 = a/b;
> float f2 = c/d;
> return f1 == f2;
>
> f1 == f2 wygląda jak herezja, ale weźmy pod uwagę, że operacje  

Z góry przepraszam że nie mam czasu głębiej się zastanowić, ale

Propozycja pierwsza:
epsilon = dobrać_doświadczalnie;
return fabs( (double)a/b - (double)c/d ) < epsilon ;

Propozycja druga:
a /= GCD(a,c);
c /= GCD(a,c);
a /= GCD(a,b);
b /= GCD(a,b);
c /= GCD(c,d);
d /= GCD(c,d);
b /= GCD(b,d);
d /= GCD(b,d);
return a*d == c*b;

Pozdrawiam

do góry

a nie wystarczy po prostu a*d == c*b?
R

On 21 Wrz, 12:20, Mariusz Marszałkowski <m...@g...com> wrote:
> On 21 Wrz, 11:45, "Wojciech \"Spook\" Sura" <spook"mad@hatter"op.pl>
> wrote:
>
> > 1. Metoda brutalna:
>
> > float f1 = a/b;
> > float f2 = c/d;
> > return f1 == f2;
>
> > f1 == f2 wygląda jak herezja, ale weźmy pod uwagę, że operacje  
>
> Z góry przepraszam że nie mam czasu głębiej się zastanowić, ale
>
> Propozycja pierwsza:
> epsilon = dobrać_doświadczalnie;
> return fabs( (double)a/b - (double)c/d ) < epsilon ;
>
> Propozycja druga:
> a /= GCD(a,c);
> c /= GCD(a,c);
> a /= GCD(a,b);
> b /= GCD(a,b);
> c /= GCD(c,d);
> d /= GCD(c,d);
> b /= GCD(b,d);
> d /= GCD(b,d);
> return a*d == c*b;
>
> Pozdrawiam

do góry

Dnia 21-09-2010 o 11:56:54 Tomasz Kaczanowski
<kaczus@dowyciecia_poczta.onet.pl> napisał(a):

>> dużych mianownikach, których GCD wynosi 1, na przykład 1/2147483629 i
>> 1/2147483647. Ich wspólnym mianownikiem jest 4611685977625198592, co

> Jesli sprawdzasz tylko równość, to w zasadzie szukając największych
> wspólnych dzielników licznika i mianownika każdego z ułamków, powinieneś
> obie liczby sprowadzić do tej samej postaci....

Nie jestem pewien, czy zawsze jest to możliwe. Perfidny przykład - wstaw
odpowiedni znak pomiędzy ułamki 11/2147483629 i 17/2147483647. Wszystkie
NWD są równe 1, bo złośliwie dobrałem same liczby pierwsze. NWW
mianowników to - jak wspomniałem - 4611685977625198592, co przekracza
zakres long int.

Pozdrawiam -- Spook.

--
! ._______. Warning: Lucida Console sig! //) !
! || spk || www.spook.freshsite.pl / _ """*!
! ||_____|| spook at op.pl / ' | ""!
! | ___ | tlen: spoko_ws gg:1290136 /. __/"\ '!
! |_|[]_|_| May the SOURCE be with you! \/) \ !

do góry

Dnia 21-09-2010 o 12:15:09 Mariusz Kruk <M...@e...eu.org>
napisał(a):

> epsilon$ while read LINE; do echo \>"$LINE"; done < "Wojciech "Spook"
> Sura"
>> Witam!
>>
>> Zastanawiam się, w jaki sposób porównywać ułamki zwykłe?
>>
>> Przypuśćmy, że mam dane dwa ułamki, a/b i c/d. Chcę sprawdzić, czy są
>> równe.
>
> Rozwiązanie pewne, acz niespecjalnie wydajne - skrócić oba.

Czytaj proszę post do końca. Podałem bardzo prosty przykład, gdzie oba
ułamki są w najkrótszej postaci i perfidnie dobrane, bo mianowniki są
liczbami pierwszymi.

Pozdrawiam -- Spook.

--
! ._______. Warning: Lucida Console sig! //) !
! || spk || www.spook.freshsite.pl / _ """*!
! ||_____|| spook at op.pl / ' | ""!
! | ___ | tlen: spoko_ws gg:1290136 /. __/"\ '!
! |_|[]_|_| May the SOURCE be with you! \/) \ !

do góry

Dnia 21-09-2010 o 12:20:47 Mariusz Marszałkowski <m...@g...com>
napisał(a):
> Propozycja pierwsza:
> epsilon = dobrać_doświadczalnie;
> return fabs( (double)a/b - (double)c/d ) < epsilon ;

W taki właśnie sposób porównuję ułamki zmiennoprzecinkowe. Jednak trochę
martwi mnie sytuacja, w której mogę otrzymać informację, że dwa ułamki są
równe, gdy w rzeczywistości będą różniły się o mniej niż epsilon (a
wszystkie składowe ułamków są intami, co - przynajmniej teoretycznie -
umożliwia deterministyczne porównania).

> Propozycja druga:
> a /= GCD(a,c);
> c /= GCD(a,c);
> a /= GCD(a,b);
> b /= GCD(a,b);
> c /= GCD(c,d);
> d /= GCD(c,d);
> b /= GCD(b,d);
> d /= GCD(b,d);
> return a*d == c*b;

Złośliwy przykład:

11/2147483629 i 17/2147483647.

Zarówno końcowe a*d jak i c*b przekroczy zakres long inta.

> Pozdrawiam

Pozdrawiam -- Spook.

--
! ._______. Warning: Lucida Console sig! //) !
! || spk || www.spook.freshsite.pl / _ """*!
! ||_____|| spook at op.pl / ' | ""!
! | ___ | tlen: spoko_ws gg:1290136 /. __/"\ '!
! |_|[]_|_| May the SOURCE be with you! \/) \ !

do góry

Wojciech "Spook" Sura pisze:
> Dnia 21-09-2010 o 11:56:54 Tomasz Kaczanowski
> <kaczus@dowyciecia_poczta.onet.pl> napisał(a):
>
>>> dużych mianownikach, których GCD wynosi 1, na przykład 1/2147483629 i
>>> 1/2147483647. Ich wspólnym mianownikiem jest 4611685977625198592, co
>
>> *Jesli sprawdzasz tylko równość*, to w zasadzie szukając największych
>> wspólnych dzielników licznika i mianownika każdego z ułamków,
>> powinieneś obie liczby sprowadzić do tej samej postaci....
>
> Nie jestem pewien, czy zawsze jest to możliwe. Perfidny przykład - wstaw
> odpowiedni znak pomiędzy ułamki 11/2147483629 i 17/2147483647. Wszystkie
> NWD są równe 1, bo złośliwie dobrałem same liczby pierwsze. NWW
> mianowników to - jak wspomniałem - 4611685977625198592, co przekracza
> zakres long int.

A one są równe?


--
Kaczus
http://kaczus.republika.pl

do góry