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 » 23 wrz 2010, o 09:05

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
piotrchamera
 
Posty: 86
Dołączył(a): 14 cze 2012, o 08:58

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

Postprzez piotrchamera » 23 wrz 2010, o 11:21

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)
piotrchamera
 
Posty: 86
Dołączył(a): 14 cze 2012, o 08:58

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

Postprzez wojciechspooksura » 23 wrz 2010, o 11:21

Dnia 22-09-2010 o 22:04:18 nightwatch77 <rafal.gwizdala@gmail.com>=

napisał(a):

>
Dodam jeszcze, że nie satysfakcjonuje mnie wykorzystanie typu o =


>większej precyzji, np. long long int. Równie dobrze możemy przy=

jąć, ż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ż kon=

iec
wymagań?


Ograniczenie obliczeń do zakresu long inta od początku było jedyny=
m =

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

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

Postprzez remek » 23 wrz 2010, o 19:30

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
remek
 
Posty: 438
Dołączył(a): 14 cze 2012, o 08:42

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

Postprzez remek » 23 wrz 2010, o 19:32

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
remek
 
Posty: 438
Dołączył(a): 14 cze 2012, o 08:42

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

Postprzez marcinbiegan » 23 wrz 2010, o 22:49

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
marcinbiegan
 
Posty: 52
Dołączył(a): 14 cze 2012, o 11:34

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

Postprzez bartekltg » 24 wrz 2010, o 00:09

On 23 Wrz, 13:21, "Wojciech \"Spook\" Sura" <spook"mad@hatter"op.pl>
wrote:
Dnia 22-09-2010 o 22:04:18 nightwatch77 <rafal.gwizd...@gmail.com>=A0
napisał(a):



>Dodam jeszcze, że nie satysfakcjonuje mnie wykorzystanie typu o =A0
większej precyzji, np. long long int. Równie dobrze możemy przyj=

ąć, że =A0
>>licznik i =A0mianownik są typu long long int i że mianowniki są =

z górnej =A0
>>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ż koni=

ec
>wymagań?

Ograniczenie obliczeń do zakresu long inta od początku było jedynym=

=A0
wymaganiem. Po prostu stosowanie w takim przypadku long long inta jest =

=A0
ominięciem a nie rozwiązaniem problemu (abstrahując od faktu, że =

być może =A0

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

będę korzystał w moim programie właśnie z long long intów zam=

iast z long =A0
intów, a long long long inta nie ma :) ).


gcc ma na maszynach 64 bitowych typ __int128_t.

pozdrawiam
bartekltg
bartekltg
 
Posty: 262
Dołączył(a): 14 cze 2012, o 11:34

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

Postprzez mariuszmarszakowski » 24 wrz 2010, o 02:15

On 24 Wrz, 02:09, bartekltg <bartek...@gmail.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 <rafal.gwizd...@gmail.com>=A0
napisał(a):


>>Dodam jeszcze, że nie satysfakcjonuje mnie wykorzystanie typu o =

=A0
>>>większej precyzji, np. long long int. Równie dobrze możemy prz=

yjąć, że =A0
>>>licznik i =A0mianownik są typu long long int i że mianowniki s=

ą z górnej =A0
>>>granicy tego zakresu.

>a jak ktoś wymysli rozwiązanie to wtedy dodasz jeszcze że chodz=

i o
>>takie które używa tylko bitowego przesuwania w lewo, czy już ko=

niec
>>wymagań?

Ograniczenie obliczeń do zakresu long inta od początku było jedyn=

ym =A0
>wymaganiem. Po prostu stosowanie w takim przypadku long long inta jest =

=A0
>ominięciem a nie rozwiązaniem problemu (abstrahując od faktu, ż=

e być może =A0
Ktoś pisał: zaimplementuj dowolna precyzje. Albo uzyj ulamkow
z GMP.

będę korzystał w moim programie właśnie z long long intów z=

amiast z long =A0
>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 =3D=3D 0
to każdą zmienną można wyrazić jako:
x =3D jedna_trzecia_bitow
a =3D 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
mariuszmarszakowski
 
Posty: 390
Dołączył(a): 14 cze 2012, o 11:34

Poprzednia strona

Powrót do Programowanie

Kto przegląda forum

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

cron