W dniu 2010-09-21 18:27, Piotr Chamera pisze:
> W dniu 2010-09-21 16:22, Wojciech "Spook" Sura pisze:
>> 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...

Z ciekawości, czy nie napisałem głupot spróbowałem
zaimplementować tę procedurę. Oto co mi wyszło (CommonLisp):

(defun cmp-rational (a b c d)
"Porównanie liczb a/b i c/d przy założeniu, że
a, b, c, d dodatnie oraz b i d różne od 0.
Liczby w obliczeniach pośrednich nigdy nie
są większe od wejściowych.

Zwracane wartości:
a/b > c/d => T
a/b < c/d => NIL
a/b = c/d => EQUAL"

(multiple-value-bind (c1 r1) (truncate a b)
(multiple-value-bind (c2 r2) (truncate c d)
(cond ((> c1 c2) T)
((< c1 c2) NIL)
; już wiadomo że cz. całkowite są równe, sprawdzamy reszty
((and (zerop r1) (zerop r2)) 'EQUAL)
(T (let ((r (cmp-rational b r1 d r2)))
(if (eq r 'EQUAL)
'EQUAL
(not r))))))))

Działa to całkiem sprawnie, dla miliona losowych par liczb,
gdzie licznik i mianownik są z zakresu liczb 32-bitowych
max głębokość rekursji wyniosła 9. Często jest jednak w zakresie
1-2. Powinno to być też proste do przepisania na iteracje.
Oto kilka przykładów:

,,trudny" przypadek z postów wyżej
CL-USER> (cmp-rational 11 2147483629 17 2147483647)

0: (CMP-RATIONAL 11 2147483629 17 2147483647)
1: (CMP-RATIONAL 2147483629 11 2147483647 17)
1: CMP-RATIONAL returned T
0: CMP-RATIONAL returned NIL
NIL

równość
CL-USER> (cmp-rational 11 2048 11 2048)

0: (CMP-RATIONAL 11 2048 11 2048)
1: (CMP-RATIONAL 2048 11 2048 11)
2: (CMP-RATIONAL 11 2 11 2)
3: (CMP-RATIONAL 2 1 2 1)
3: CMP-RATIONAL returned EQUAL
2: CMP-RATIONAL returned EQUAL
1: CMP-RATIONAL returned EQUAL
0: CMP-RATIONAL returned EQUAL
EQUAL

CL-USER> (cmp-rational 1 16 1 16)

0: (CMP-RATIONAL 1 16 1 16)
1: (CMP-RATIONAL 16 1 16 1)
1: CMP-RATIONAL returned EQUAL
0: CMP-RATIONAL returned EQUAL
EQUAL

,,duże" liczby
CL-USER> (cmp-rational 1 42536847596214256328 1 1248534474348433455)

0: (CMP-RATIONAL 1 42536847596214256328 1 1248534474348433455)
1: (CMP-RATIONAL 42536847596214256328 1 1248534474348433455 1)
1: CMP-RATIONAL returned T
0: CMP-RATIONAL returned NIL
NIL
CL-USER> (cmp-rational 11 2000000000000000000000 11 2000000000000000000000)

0: (CMP-RATIONAL 11 2000000000000000000000 11 2000000000000000000000)
1: (CMP-RATIONAL 2000000000000000000000 11 2000000000000000000000 11)
2: (CMP-RATIONAL 11 9 11 9)
3: (CMP-RATIONAL 9 2 9 2)
4: (CMP-RATIONAL 2 1 2 1)
4: CMP-RATIONAL returned EQUAL
3: CMP-RATIONAL returned EQUAL
2: CMP-RATIONAL returned EQUAL
1: CMP-RATIONAL returned EQUAL
0: CMP-RATIONAL returned EQUAL
EQUAL
CL-USER> (cmp-rational 11 2000000000000000000000 11 2000000000000000000001)

0: (CMP-RATIONAL 11 2000000000000000000000 11 2000000000000000000001)
1: (CMP-RATIONAL 2000000000000000000000 11 2000000000000000000001 11)
2: (CMP-RATIONAL 11 9 11 10)
3: (CMP-RATIONAL 9 2 10 1)
3: CMP-RATIONAL returned NIL
2: CMP-RATIONAL returned T
1: CMP-RATIONAL returned NIL
0: CMP-RATIONAL returned T
T
CL-USER> (cmp-rational 11 2000000000000000000002 11 2000000000000000000001)

0: (CMP-RATIONAL 11 2000000000000000000002 11 2000000000000000000001)
1: (CMP-RATIONAL 2000000000000000000002 11 2000000000000000000001 11)
1: CMP-RATIONAL returned T
0: CMP-RATIONAL returned NIL
NIL