W dniu 2010-09-21 16:22, Wojciech "Spook" Sura pisze:
> Dnia 21-09-2010 o 14:14:14 Marcin 'Qrczak' Kowalczyk <q...@k...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.

do góry

On 20 Wrz, 05:37, "j...@f...adres.to"
<w...@c...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 = 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..

Nie, ale nie o to chodziło żeby króliczka złapać. Zepsułeś całą zabawę.

do góry

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

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

Ponieważ liczenie na ułamkach zwykłych bez liczb całkowitych dowolnej
precyzji jest mało praktyczne (licznik i mianownik mogą spuchnąć nawet
kiedy liczba wcale nie jest szczególnie duża), to a*d <=> c*b w
arytmetyce dowolnej precyzji powinno wystarczyć.

do góry

Dnia 20-09-2010 o 05:37:26 j...@f...adres.to
<w...@c...barg.cy> napisał(a):
> 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?

Obawiam się, że tak :). Algorytm ma działać dla dowolnych ułamków, których
liczniki i mianowniki mieszczą się w zakresie long int. Na przykład
11/2147483629 i 17/2147483647 (nie ukrywam, że dobrałem złośliwie :) ).

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.

> 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! \/) \ !

do góry

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

do góry

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  
> liczniki i mianowniki mieszczą się w zakresie long int. Na przykład  
> 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 ;)

do góry

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

do góry

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

do góry

>
> 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.
>

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ń?

do góry

On 21 Wrz, 23:14, "Wojciech \"Spook\" Sura" <spook"mad@hatter"op.pl>
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.

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

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

wtedy mamy coś w rodzaju
( a1 + (a2<<x) ) * ( d1 + (d2<<x) ) - ( b1 + (b2<<x) ) * ( c1 +
(c2<<x) ) == 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

do góry