witam,

jak sprawdzic czy dla integerow a,b,c,d zachodzi

a*b == c*d

--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

W dniu 2011-05-24 20:28, t...@g...SKASUJ-TO.pl pisze:
> witam,
>
> jak sprawdzic czy dla integerow a,b,c,d zachodzi
>
> a*b == c*d
>

Trywialna odpowiedź brzmi:

if(a*b == c*d)
{
// a*b == c*d zachodzi
}
else
{
// nie a*b == c*d zachodzi
}

Pewnie chodzi Ci o jakieś dodatkowe warunki (np. a*b > MAX_INT), ale
wypadałoby to napisać wyraźne 8-)

Dla takich przypadków strzelam - podział na czynniki i porównanie
zsumowanych dla a i b oraz c i d (multi)zbiorów tych czynników.
Jeśli tożsame, to iloczyny równe.

--
Paweł Kierski
n...@p...net

do góry

Paweł Kierski <n...@p...net> napisał(a):

> Pewnie chodzi Ci o jakieś dodatkowe warunki (np. a*b > MAX_INT), ale
> wypadałoby to napisać wyraźne 8-)

w jakim celu?
co najwyzej mozna dodac informacje ze a*b moze (ale musi) > MAX_INT
ale to nic nie wnosi :)

> Dla takich przypadków strzelam - podział na czynniki i porównanie
> zsumowanych dla a i b oraz c i d (multi)zbiorów tych czynników.
> Jeśli tożsame, to iloczyny równe.

to strasznie wolne.
Chodzi raczej o to, czy ktos zna zestaw warunkow typu mnozenie, dodawanie
modulo, lub czy mnozenie jako double moze prowadzic do blednych wynikow.

--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

<t...@W...gazeta.pl> napisał(a):

> Paweł Kierski <n...@p...net> napisał(a):
>
> > Pewnie chodzi Ci o jakieś dodatkowe warunki (np. a*b > MAX_INT), ale
> > wypadałoby to napisać wyraźne 8-)
>
> w jakim celu?
> co najwyzej mozna dodac informacje ze a*b moze (ale musi) > MAX_INT
> ale to nic nie wnosi :)
>
> > Dla takich przypadków strzelam - podział na czynniki i porównanie
> > zsumowanych dla a i b oraz c i d (multi)zbiorów tych czynników.
> > Jeśli tożsame, to iloczyny równe.
>
> to strasznie wolne.
> Chodzi raczej o to, czy ktos zna zestaw warunkow typu mnozenie, dodawanie
> modulo, lub czy mnozenie jako double moze prowadzic do blednych wynikow.
>

nawet 32 bitowe x86 obsluguja mnozenie 32 bity * 32 bity (wynik jest
ponoc w EDX:EAX ) tak ze nie wiem czy kompilator by tu cos chrzanil

jest tez przeciez obsluga 64 bitowych liczb ew emulowna softowo
(nie wiem jak dokladnie z tym jest)

co do prownan nie wiem czy nie ma jakichs sztuczek z matematyki - nie
zajmowalem sie

mozna tez oczywiscie sprobowac dawac jakies przedwarunki np
jesli max(a,b)<min(c,d) to wiadomo ze a*b<c*d itp

mozna tez ew probowac cos ze sprawdzaniem najwyzszych bitow
w x86 jest o ile pamietam instrukcja ktora podaje poz pierwszego
zapalonego bitu od lewej - i zastanowic sie kiedy mozna orzec
nierownosc

teraz mnozenia sa ponoc szybkie tak ze najprosciej pewnie
pomnozyc - doczytac o tym ew softowym typie 64 bit, nie wiem

1)

czy kompilator schrazni porownanie a*b==c*d (?) czy z zasad jezyka wynika
ze musi skladniki (jesli sa typu int64 przed porownaniem konwertowac do
int32?)

2) czy cos takiego nie da sie zrobic

int64 x= a*b;
int64 y= c*d;
if(x==y)....

3) vel

int64 x= a*b;
int64 y= c*d;
if((x.lo==y.lo) && (x.hi==y.hi))....




--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

> w jakim celu?
> co najwyzej mozna dodac informacje ze a*b moze (ale musi) > MAX_INT
> ale to nic nie wnosi :)


to nam psuje warunek, przykładowo GCC 4.6.0 przy takim czymś

cout << boolalpha << (4*1073741826 == 4*2);

sypie warningiem podczas kompilacji, i niestety, wyświetla true.



--
Azarien

do góry

W dniu 2011-05-25 00:19, t...@W...gazeta.pl pisze:
> Paweł Kierski<n...@p...net> napisał(a):
>
>> Pewnie chodzi Ci o jakieś dodatkowe warunki (np. a*b> MAX_INT), ale
>> wypadałoby to napisać wyraźne 8-)
>
> w jakim celu?
> co najwyzej mozna dodac informacje ze a*b moze (ale musi)> MAX_INT
> ale to nic nie wnosi :)

C++, 32 bitowy int z arytmetyką U2 + implementacja nie sprawdzająca
przekroczenia zakresu, ale "zawijająca":

int a = 1000000000;
int b = 2000000000;

int c = 131072;
int d = 10084;

if(a*b == c*d)
{
std::cout << "Suprise!\n";
}

>> Dla takich przypadków strzelam - podział na czynniki i porównanie
>> zsumowanych dla a i b oraz c i d (multi)zbiorów tych czynników.
>> Jeśli tożsame, to iloczyny równe.
>
> to strasznie wolne.

Być może jest szybsza metoda - to mi przyszło do głowy w kilkanaście
sekund.

> Chodzi raczej o to, czy ktos zna zestaw warunkow typu mnozenie, dodawanie
> modulo, lub czy mnozenie jako double moze prowadzic do blednych wynikow.

Zaraz, zaraz - double? Chcesz porównywać na równość? Z góry skazane na
niepowodzenie...

--
Paweł Kierski
n...@p...net

do góry

Paweł Kierski <n...@p...net> napisał(a):

> > Chodzi raczej o to, czy ktos zna zestaw warunkow typu mnozenie, dodawanie
> > modulo, lub czy mnozenie jako double moze prowadzic do blednych wynikow.
>
> Zaraz, zaraz - double? Chcesz porównywać na równość? Z góry skazane na
> niepowodzenie...

dla intow 32 bit prawdopodobienstwo niepowodzenia jest bardzo niskie.
Mnozenie takich intow jako doubli ma relatywna dokladnosc rzedu 1e15, kiedy
potrzebna jest rzedu 1e19.

Brakuje wiec tylko metody sprawdzajacej najmniej znaczace cyfry mnozenia.
Czyli test
1. (a*b == c*d)? dla a,b,c,d jako int32
2. (a*b == c*d)? dla a,b,c,d jako double
chyba powinien wyeliminowac mozliwosc kolizji.

Dla intow 64 bitowych jest troche trudniej. double nie reprezentuja
dokladnie wszystkich int64. Brakuje wiec testu na rownosc srodkowych cyfr
znaczacych.

--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

W dniu 2011-05-24 20:28, t...@g...SKASUJ-TO.pl pisze:
> witam,
>
> jak sprawdzic czy dla integerow a,b,c,d zachodzi
>
> a*b == c*d

Jak a i b są 32 bitowe, to piszemy ((long long)a)*b i porównujemy.
Jak 64, a maszyna x64, to VS i gcc mają jakieś typy 128bitowe
i podobnie. W strasznym języku ja J mamy duże liczby;)


> Chodzi raczej o to, czy ktos zna zestaw warunkow
> typu mnozenie, dodawanie
> modulo,


Ok, a jak podam rozwiązanie, to co dostane?

Masz porównać ab == cd

porównaj ab == cd (mod p_i)

dla kilku liczb pierwszych, w miarę dużych i takich,
by p^2 mieściło się w zakresie.
Z górką wystarczy 5 takich liczb*)

Jeśli m==n (mod p_i), dla i=1..k
to m==n jeżeli tylko m i n < p_1*p_2*...*p_k

Nazywa się toto Chińskie twierdzenie o resztach.
p_i nie muszą być nawet pierwsze, wystarczy, że są względnie pierwsze.


*)P< sqrt(MAXINT), ale możemy dobrać niewiele mniejsze.
p_1*..*p^5 wyniesie ponad MAXINT^2




Mnożenia a*b wykonujesz mod p: ((a%p)*(b%p))%p
więc nigdy nie wyskoczysz poza zakres.

Wydaje się, że więcej pracy niż przy ((long long)a)*b==((long long)c)*d,
ale za to ładnie skaluje się, liniowo ze względu na ilość czynników
w iloczynie (czego nie można powiedzieć o mnożeniu dużych liczb).

No i jest niezależne od języka, maszynerii i tego, czym tak naprawdę
są te inty.


Ktoś podesłał pomysł rozkładu na czynniki pierwsze. Można pociągnąć
ten pomysł. Policzymy NWD (najwiekszy wspolny dzielnik)
dla wszytkich możliwytch par i będziemy skracać.

x=NWD(a,c);
a=a/x; c=c/x;

i podobnie dla par a:d, b:c, b:d (najpierw skracamy, pozniej
liczymy kolejne NWD)

Po wszystkich skróceniach, jeśli iloczyny były równe, otrzymamy
cztery jedynki.

Algorytm liczący NWD znajdziesz bez problemu, jest prosty i szybki,
a imię jego Euklides.


Chyba trudniej byłoby ze stwierdzeniem, która liczba jest większa.


pozdrawiam
bartekltg

do góry

W dniu 2011-05-25 20:39, bartekltg pisze:
[...]
> Ktoś podesłał pomysł rozkładu na czynniki pierwsze. Można pociągnąć
> ten pomysł. Policzymy NWD (najwiekszy wspolny dzielnik)
> dla wszytkich możliwytch par i będziemy skracać.
>
> x=NWD(a,c);
> a=a/x; c=c/x;
>
> i podobnie dla par a:d, b:c, b:d (najpierw skracamy, pozniej
> liczymy kolejne NWD)
>
> Po wszystkich skróceniach, jeśli iloczyny były równe, otrzymamy
> cztery jedynki.

Drobna poprawka - nie dla wszystkich możliwych par: nie skracamy a:b
i c:d 8-)

> Algorytm liczący NWD znajdziesz bez problemu, jest prosty i szybki,
> a imię jego Euklides.

--
Paweł Kierski
n...@p...net

do góry

Dnia 24-05-2011 o 20:28:27 <t...@g...skasuj-to.pl> napisał(a):

> witam,
>
> jak sprawdzic czy dla integerow a,b,c,d zachodzi
>
> a*b == c*d

Rozłóż obie strony na czynniki pierwsze i porównaj (zakładam, że a*b i c*d
mogą przekroczyć zakres testowanego typu).

Pozdrawiam -- Spook.

--
Używam klienta poczty Opera Mail: http://www.opera.com/mail/

do góry