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

do góry

I jeszcze wersja iteracyjna algorytmu (z komentarzami)
i statystyka liczby iteracji.

PS. Nie irytujcie się, jeśli to nikomu nie potrzebne.
Tak mnie dzisiaj naszło na pisanie nawiasów :)

(defun cmp-rational2 (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. Wersja iteracyjna.

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

(do ((sign T) ; albo NIL - oznacza negację wyniku
c1 r1 c2 r2) ; miejsce na wyniki dzielenia i reszty
(NIL) ; pętla bez końca
;(print (list a b c d) nil) ; drukowanie parametrów pośrednich iteracji
(multiple-value-setq (c1 r1) (truncate a b)) ; dzielenie całkowite
z resztą
(multiple-value-setq (c2 r2) (truncate c d)) ; dzielenie całkowite
z resztą
(cond
; jeśli części całkowite się różnią, to można wyznaczyć znak
nierówności
((> c1 c2) (if sign
(return T)
(return NIL))
; zamiast (if...) można dać (return sign)
)
((< c1 c2) (if sign
(return NIL)
(return T))
; zamiast (if...) można dać (return (not sign))
)
; tu już wiemy, że w tej iteracji części całkowite były równe
; jeśli również reszty są zerowe to badane liczby są równe
((and (zerop r1) (zerop r2)) (return 'EQUAL))
; zmiana parametrów dla następnej iteracji
; a=b, b=reszta(a/b), c=d, d=reszta(c/d) i zmiana znaku
(T (progn (setq sign (not sign)
a b
b r1
c d
d r2))))))



Liczba iteracji (po lewej) i liczba wywołań wymagających tylu iteracji
(po prawej). Próba 100 000 000 losowo generowanych porównań.

(0 67751730)
(1 23792799)
(2 6988131)
(3 1159932)
(4 246927)
(5 48544)
(6 9536)
(7 1927)
(8 396)
(9 66)
(10 10)
(11 2)

do góry

Dnia 22-09-2010 o 22:04:18 nightwatch77 <r...@g...com>
napisał(a):

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

Ograniczenie obliczeń do zakresu long inta od początku było jedynym
wymaganiem. Po prostu stosowanie w takim przypadku long long inta jest
ominięciem a nie rozwiązaniem problemu (abstrahując od faktu, że być może
będę korzystał w moim programie właśnie z long long intów zamiast z long
intów, a long long long inta nie ma :) ).

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

Użytkownik "Spec" napisał:

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

Asembler? :) Patrząc na te wygibasy, których trzeba użyć do wykonania
operacji z zakresu 3 klasy podstawówki dochodzę do wniopsku, że HL-e są do
d... Zastanawiam się jakim cudem amerykańce na 386 liczyli i prowadzili loty
kosmiczne. A choćby kalkulator 4 działaniowy umożliwiający użycie dzielnika
większego od dworda?

Remek

do góry

Użytkownik "nightwatch77" napisał:

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

Czy jesteś w stanie nauczyć się prawidłowego cytowania?

Remek

do góry

W dniu 2010-09-23 13:21, Wojciech "Spook" Sura pisze:
> Po prostu stosowanie w takim przypadku long long inta jest
> ominięciem a nie rozwiązaniem problemu (abstrahując od faktu, że być może
> będę korzystał w moim programie właśnie z long long intów zamiast z long
> intów, a long long long inta nie ma :) ).

'long long long' is too long for gcc

--
MB

do góry

On 23 Wrz, 13:21, "Wojciech \"Spook\" Sura" <spook"mad@hatter"op.pl>
wrote:
> Dnia 22-09-2010 o 22:04:18 nightwatch77 <r...@g...com>  
> napisał(a):
>
>
>
> >> 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ń?
>
> Ograniczenie obliczeń do zakresu long inta od początku było jedynym  
> wymaganiem. Po prostu stosowanie w takim przypadku long long inta jest  
> ominięciem a nie rozwiązaniem problemu (abstrahując od faktu, że być może  

Ktoś pisał: zaimplementuj dowolna precyzje. Albo uzyj ulamkow
z GMP.

> będę korzystał w moim programie właśnie z long long intów zamiast z long  
> intów, a long long long inta nie ma :) ).

gcc ma na maszynach 64 bitowych typ __int128_t.

pozdrawiam
bartekltg

do góry

On 24 Wrz, 02:09, bartekltg <b...@g...com> wrote:
> On 23 Wrz, 13:21, "Wojciech \"Spook\" Sura" <spook"mad@hatter"op.pl>
> wrote:
>
>
>
> > Dnia 22-09-2010 o 22:04:18 nightwatch77 <r...@g...com>  
> > napisał(a):
>
> > >> 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ń?
>
> > Ograniczenie obliczeń do zakresu long inta od początku było jedynym  
> > wymaganiem. Po prostu stosowanie w takim przypadku long long inta jest  
> > ominięciem a nie rozwiązaniem problemu (abstrahując od faktu, że być może  
>
> Ktoś pisał: zaimplementuj dowolna precyzje. Albo uzyj ulamkow
> z GMP.
>
> > będę korzystał w moim programie właśnie z long long intów zamiast z long  
> > intów, a long long long inta nie ma :) ).
>
> gcc ma na maszynach 64 bitowych typ __int128_t.

Jeśli dobrze zrozumiałem, OP chodziło o to że program
może być napisany na dowolnym typie, np. na takim dużym od
którego już większego typu wbudowanego nie ma. Wtedy
pozostaje GMP, albo rozbicie jednej zmiennej na... chyba
aż na trzy trzeba.
Jeśli jest:
a*d - b*c == 0
to każdą zmienną można wyrazić jako:
x = jedna_trzecia_bitow
a = a_3*2^(x*2) + a_2*2^x + a_3

wtedy mnożymy w słupku:
a_3 a_2 a_1
x d_3 d_2 d_1
--------------------------
1x3 1x2 1x1
2x1 2x2 2x3
3x1 3x2 3x3

Obojętnie jakiego typu użyje to zadziała. Trzeba oczywiście
specjalnie obsłużyć bit znaku.

Pozdrawiam

do góry