Porównywanie ułamków zwykłych

Forum poświęcone programowaniu, bazom danych i pokrewnych.

Re: Porównywanie ułamków zwykłych

Postprzez piotrchamera » 21 wrz 2010, o 16:27

W dniu 2010-09-21 16:22, Wojciech "Spook" Sura pisze:
Dnia 21-09-2010 o 14:14:14 Marcin 'Qrczak' Kowalczyk <qrczak@knm.org.pl>
napisał(a):

On Sep 21, 11:45 am, "Wojciech \"Spook\" Sura"
<spook"mad@hatter"op.pl>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.


Najlepiej zawsze trzymać je znormalizowane (inaczej w obliczeniach
niepotrzebnie będą się przewalały duże liczby). Wtedy a == c && b == d.


Tak też je przechowuję. Faktycznie, sprawdzenie, czy są równe jest
proste; co jednak wówczas, gdy chciałbym je porównać?


może tak:
gdy a >b i c >d to porównanie sprowadza się do porównania odwrotności
ułamków b/a i d/c, wydzielenia ich części całkowitych (dzielenie
całkowite d/c) - jeśli są różne, to już wiemy która liczba większa),
porównania pozostałych ułamków, co powinno być prostsze (mniejsze
liczby) i tak rekursywnie.
piotrchamera
 
Posty: 86
Dołączył(a): 14 cze 2012, o 08:58

Re: Porównywanie ułamków zwykłych

Postprzez nightwatch77 » 21 wrz 2010, o 18:09

On 20 Wrz, 05:37, "jan...@fajny.adres.to"
<wnahfm.yrcvb...@cbpmgn.barg.cy>wrote:
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 =3D a/b;
float f2 =3D c/d;
return f1 =3D=3D f2;


f1 =3D=3D f2 wygląda jak herezja, ale weźmy pod uwagę, że opera=

cje
>zmiennoprzecinkowe są wykonywane deterministycznie i jeśli ułamki
faktycznie są równe, warunek będzie spełniony. Niestety, nie ma=

my 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 =3D GCD(b, c);


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


Problem pojawi się wówczas, gdy złośliwie podrzucimy dwa ułam=

ki 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 zak=

resie
>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 =3D (a,b), B=3D(c,d),
czyli (w pseudokodzie)
struct fraction {int nominator, int denominator};

Wtedy:
a/b < c/d =A0<=3D>=A0a*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 =3D (long)A.nominator * (long)B.denominator;
long right =3D (long)A.denominator * (long)B.nominator;
if(left<right) return -1;
if(left>right) return 1;
return 0;

}

Coś więcej potrzeba?

j..


Nie, ale nie o to chodziło żeby króliczka złapać. Zepsułeś ca=
łą zabawę.
nightwatch77
 
Posty: 7
Dołączył(a): 14 cze 2012, o 11:34

Re: Porównywanie ułamków zwykłych

Postprzez marcinqrczakkowalczyk » 21 wrz 2010, o 20:14

On Sep 21, 4:22=A0pm, "Wojciech \"Spook\" Sura" <spook"mad@hatter"op.pl>
wrote:

Tak też je przechowuję. Faktycznie, sprawdzenie, czy są równe jes=

t proste; =A0
co jednak wówczas, gdy chciałbym je porównać?


Ponieważ liczenie na ułamkach zwykłych bez liczb całkowitych dowoln=
ej
precyzji jest mało praktyczne (licznik i mianownik mogą spuchnąć na=
wet
kiedy liczba wcale nie jest szczególnie duża), to a*d <=3D>c*b w
arytmetyce dowolnej precyzji powinno wystarczyć.
marcinqrczakkowalczyk
 
Posty: 37
Dołączył(a): 14 cze 2012, o 11:34

Re: Porównywanie ułamków zwykłych

Postprzez wojciechspooksura » 21 wrz 2010, o 21:14

Dnia 20-09-2010 o 05:37:26 janusz@fajny.adres.to =

<wnahfm.yrcvbaxb@cbpmgn.barg.cy>napisał(a):
Zakładam, że a,b,c,d są typu int,
oraz ułamek to uporządkowana para, czyli A =3D (a,b), B=3D(c,d),
czyli (w pseudokodzie)
struct fraction {int nominator, int denominator};

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

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

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

Coś więcej potrzeba?


Obawiam się, że tak :). Algorytm ma działać dla dowolnych ułam=
ków, których =

liczniki i mianowniki mieszczą się w zakresie long int. Na przykła=
d =

11/2147483629 i 17/2147483647 (nie ukrywam, że dobrałem złośliwi=
e :) ).

Dodam jeszcze, że nie satysfakcjonuje mnie wykorzystanie typu o więk=
szej =

precyzji, np. long long int. Równie dobrze możemy przyjąć, że =
licznik i =

mianownik są typu long long int i że mianowniki są z górnej gran=
icy tego =

zakresu.

j..


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! \/) \ !
wojciechspooksura
 
Posty: 439
Dołączył(a): 14 cze 2012, o 11:34

Re: Porównywanie ułamków zwykłych

Postprzez michoo » 21 wrz 2010, o 22:44

W dniu 21.09.2010 11:45, Wojciech "Spook" Sura pisze:
Witam!

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

A potrzebujesz jakiejś super-hiper-turbo wydajności?
Imo dobrym rozwiązaniem zazwyczaj gdy potrzeba "niestandardowych"
zakresów jest użycie GMP (http://gmplib.org/) a ewentualnie gdy okazuje
się, że brakuje wydajności to dopiero roztwarzanie czegoś innego.
Pozdrawiam
Michoo
michoo
 
Posty: 581
Dołączył(a): 14 cze 2012, o 11:34

Re: Porównywanie ułamków zwykłych

Postprzez spec_b » 22 wrz 2010, o 07:40

On 21 Wrz, 23:14, "Wojciech \"Spook\" Sura" <spook"mad@hatter"op.pl>
wrote:
>Coś więcej potrzeba?

Obawiam się, że tak :). Algorytm ma działać dla dowolnych ułamk=

ów, których =A0
liczniki i mianowniki mieszczą się w zakresie long int. Na przykład=

=A0
11/2147483629 i 17/2147483647 (nie ukrywam, że dobrałem złośliwie=

:) ).

Może czas zmienić język na mniej ograniczający?

CL-USER>(>11/2147483629 17/2147483647)
NIL
CL-USER>(< 11/2147483629 17/2147483647)
T

W Lispie, bez pisania dodatkowych funkcji ;)
spec_b
 
Posty: 1
Dołączył(a): 14 cze 2012, o 11:34

Re: Porównywanie ułamków zwykłych

Postprzez qwak_5 » 22 wrz 2010, o 08:16

W dniu 21.09.2010 11:45, Wojciech "Spook" Sura pisze:
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.


Korzystamy z:
a/b == c/d<=>a*d == b*c

Pozostaje kwestia przekraczania zakresów przy mnożeniu. I tu 2 rozwiązania:

- skorzystać z biblioteki, np. GMP

- samemu zaimplementować mnożenie:

Jeśli a, b, c i d masz w N bitowych zmiennych to możesz potraktować je
jako 2-cyfrowe liczby N/2 bitowe (tj w systemie o podstawie: 2^(N/2)).
Takie liczby możesz przemnożyć stosując "algorytm szkolny" ("mnożenie
pisemne", oczywiście w systemie o podstawie 2^(N/2), a nie 10), przy
czym wynik mnożenia dwóch N/2 bitowych cyfr mieści się na N bitach (więc
stosujesz N-bitowy typ do obliczeń).
Całość wymaga 4 mnożeń, kilku dodawań, operacji bitowych...
Wynik będzie liczbą składającą się z co najwyżej 4ech N/2 bitowych cyfr.
Takie liczby łatwo porównasz cyfra po cyfrze.

Jest jeszcze kwestia znaków (liczb ujemnych), tych zgodność możesz
jednak sprawdzić przed powyższymi obliczeniami. W przypadku zgodności
możesz liczyć na wartościach bezwzględnych używając N-bitowego typu bez
znaku.
Piotr Beling - http://qwak.w8.pl http://warcaby.w8.pl http://bcalc.w8.pl
qwak_5
 
Posty: 1
Dołączył(a): 14 cze 2012, o 11:34

Re: Porównywanie ułamków zwykłych

Postprzez mateuszludwin » 22 wrz 2010, o 09:37

Wojciech "Spook" Sura wrote:

Dodam jeszcze, że nie satysfakcjonuje mnie wykorzystanie typu o większej
precyzji, np. long long int. Równie dobrze możemy przyjąć, że licznik i
mianownik są typu long long int i że mianowniki są z górnej granicy tego
zakresu.


No więc powtarzam, jeżeli chcesz liczyć symbolicznie, to licz symbolicznie...
Nawet jeśli znajdziesz jakieś obejście na ułamki i uda się to zrobić na typie
wbudowanym, to dojdziesz do ściany w jakimś kolejnym zagadnieniu. Interpretery
pisze się na własnych typach danych.
Mateusz Ludwin mateuszl [at] gmail [dot] com
mateuszludwin
 
Posty: 24
Dołączył(a): 14 cze 2012, o 11:34

Re: Porównywanie ułamków zwykłych

Postprzez nightwatch77 » 22 wrz 2010, o 20:04

Dodam jeszcze, że nie satysfakcjonuje mnie wykorzystanie typu o więks=

zej =A0
precyzji, np. long long int. Równie dobrze możemy przyjąć, że l=

icznik i =A0
mianownik są typu long long int i że mianowniki są z górnej grani=

cy tego =A0
zakresu.


a jak ktoś wymysli rozwiązanie to wtedy dodasz jeszcze że chodzi o
takie które używa tylko bitowego przesuwania w lewo, czy już koniec
wymagań?
nightwatch77
 
Posty: 7
Dołączył(a): 14 cze 2012, o 11:34

Re: Porównywanie ułamków zwykłych

Postprzez mariuszmarszakowski » 23 wrz 2010, o 01:21

On 21 Wrz, 23:14, "Wojciech \"Spook\" Sura" <spook"mad@hatter"op.pl>
wrote:

Dodam jeszcze, że nie satysfakcjonuje mnie wykorzystanie typu o więks=

zej =A0
precyzji, np. long long int. Równie dobrze możemy przyjąć, że l=

icznik i =A0
mianownik są typu long long int i że mianowniki są z górnej grani=

cy tego =A0
zakresu.


Hmmm...
Mamy sprawdzić czy a/b - c/d =3D=3D 0.
A jakby rozbić?
x =3D polowa_bitow

a1 =3D a & ((1<<x)-1)
a2 =3D a >>x;
itd...

wtedy mamy coś w rodzaju
( a1 + (a2<<x) ) * ( d1 + (d2<<x) ) - ( b1 + (b2<<x) ) * ( c1 +
(c2<<x) ) =3D=3D 0

po lewej stronie różnicy masz cztery iloczyny które na
pewno nie przekroczą zakresu i po prawej cztery iloczyny
które nie przekroczą zakresu.

wystarczy dopracować szczegóły, tzn umiejętnie porównać te
cztery iloczyny i powinno działać poprawnie na każdym typie.


Pozdrawiam
mariuszmarszakowski
 
Posty: 390
Dołączył(a): 14 cze 2012, o 11:34

Poprzednia stronaNastępna strona

Powrót do Programowanie

Kto przegląda forum

Użytkownicy przeglądający ten dział: Brak zidentyfikowanych użytkowników i 1 gość

cron