Porównywanie liczb wymiernych

12

Biorąc pod uwagę $a,b,c,d \in \mathbb N$ i , $b,d \notin \{0\}$

\begin{array}{rcl} \frac{za}{b} < \frac{do}{re} & ⟺ & za re < do b \end{array}

$\begin{eqnarray*} \frac a b < \frac c d &\iff& ad < cb \end{eqnarray*}$

Moje pytania to:

Biorąc pod uwagę $a,b,c,d$

Zakładając, że możemy zdecydować in , czy istnieje jakikolwiek sposób decydowania o bez konieczności wstępnego mnożenia (lub dzielenia), i . Czy jest jakiś dowód, że nie ma mowy. $x < y \in \mathbb Z$ $\mathcal{O}(|x| +|y|)$ $ad<cb$ $a\cdot d$ $c \cdot b$
Czy istnieje szybsza metoda porównywania liczb wymiernych niż pomnożenie mianowników.

algorithms integers Realz Slaw
źródło

1

@PKG, ale mnożenie zajmie więcej niż czas liniowy. Myślę, że chcemy czegoś szybciej na to pytanie.

Joe

1

Trudny przypadek ma miejsce, gdy jeden przedział zawiera inny, np. .

[a, d] \subset [b, c]

$[a,d] \subset [b,c]$

PKG

1

Niejawnie zakładamy, że i mają ten sam znak. W przeciwnym razie zmienia się kierunek nierówności.

b

$b$

d

$d$

Ran G.

1

(1) Mnożenie jest prawie liniowe (poszukiwanie algorytmu Fürera). (2) „Racjonalna liczba całkowita”, przynajmniej w kontekście algebraicznej teorii liczb, w rzeczywistości oznacza po prostu liczbę całkowitą. Chcesz powiedzieć „liczba wymierna” lub „liczba wymierna”.

Yuval Filmus

1

patrz także pozorny duplikat Jak porównać liczby wymierne?

vzn

5

Moje obecne badania:

Wstępna próba ogólnych zasad

Można spróbować ustalić kilka ogólnych zasad rozwiązywania racjonalnego porównania:

Zakładając wszystkie pozytywne : $a,b,c,d$

za < b \land do \geq re ⟹ \frac{za}{b} < \frac{do}{re}

$a < b \wedge c \ge d \Longrightarrow \frac a b < \frac c d\\$ Zasadniczo oznacza to, że jeśli lewa strona jest mniejsza niż jedna, a prawa strona jest co najmniej jedna, lewa strona jest mniejsza niż prawa strona. W tej samej żyle:

za \geq b \land do \leq re ⟹ \frac{za}{b} ≮ \frac{do}{re}

$a \ge b \wedge c \le d \Longrightarrow \frac a b \not\lt \frac c d\\$

Kolejna zasada:

(b > re) \land (za \leq do) \Rightarrow [\frac{za}{b} < \frac{do}{re}]

$(b > d) \wedge (a \le c) \Rightarrow \left[\frac a b < \frac c d\right]$ Uważam tę zasadę za logiczną, ponieważ im większy mianownik, tym mniejsza liczba, tym większa licznik, tym większa liczba. Dlatego jeśli lewa strona ma większy mianownik i mniejszy licznik, lewa strona będzie mniejsza.

Odtąd założymy, że , ponieważ w przeciwnym razie możemy albo rozwiązać powyższe reguły, albo odwrócić pytanie do , i tak i tak kończy się ten warunek. $a<c \wedge b < d$ $\frac c d \overset ? < \frac a b$

Reguły : To Reguła zasadniczo stwierdza, że zawsze można odjąć liczniki od mianowników i ustawić wyniki jako liczniki, aby uzyskać równoważny problem. Pominę dowód.

{\frac{(b - a)}{b} < \frac{(d - c)}{d} ⟺ [\frac{a}{b} < \frac{c}{d}] |}_{a < c, b < re}

$\left. \\ \frac {(b-a)} b < \frac {(d-c)} d \iff \left[\frac a b < \frac c d\right] \right|_{a<c,b<d} \\$

{\frac{a}{b} < \frac{c - a}{d - b} ⟺ [\frac{a}{b} < \frac{c}{d}] |}_{a < c, b < re}

$\left. \\ \frac {a} b < \frac {c-a} {d-b} \iff \left[\frac a b < \frac c d\right] \right|_{a<c,b<d} \\$

Ta reguła pozwala odjąć lewy licznik i mianownik od prawego licznika i mianownika dla równoważnego problemu.

I oczywiście jest skalowanie:

{\frac{a k}{b k} < \frac{c}{d} ⟺ [\frac{za}{b} < \frac{do}{re}] |}_{za < do, b < re}

$\left. \\ \frac {ak} {bk} < \frac {c} {d} \iff \left[\frac a b < \frac c d\right] \right|_{a<c,b<d} \\$ You może użyć skalowania, aby zwiększyć znaczenie reguł odejmowania powyżej.

Korzystając z tych zasad, możesz bawić się rzeczami, stosować je wielokrotnie, w inteligentnych kombinacjach, ale zdarzają się przypadki, gdy liczby są bliskie i patologiczne.

Stosując poprzednie reguły, możesz zredukować wszystkie te problemy do:

{\frac{za}{b} < \frac{za p + q}{b p^{'} + q^{'}} ⟺ \frac{za}{b} < \frac{q}{q^{'}} |}_{za > q, b > q^{'}}

$\left. \frac a b < \frac {ap+q} {bp'+q'} \iff \frac a b < \frac {q} {q'} \right|_{a>q,b>q'}$

Czasami możesz rozwiązać to teraz, a czasem nie. Przypadki patologiczne są zwykle w postaci:

{\frac{za}{b} < \frac{do}{re} |}_{za > do, b > re, do \in O (za), re \in O (b)}

$\left. \frac a b < \frac {c} {d} \right|_{a>c,b>d,c\in \mathcal O(a), d \in \mathcal O(b)}$

Potem odwracasz i dajesz to samo, tylko z odrobiną mniej. Każde zastosowanie reguł + flip zmniejsza to o cyfrę / bit. AFAICT, nie możesz go szybko rozwiązać, chyba że zastosujesz reguły razy (raz dla każdej cyfry / bitu) w przypadku patologicznym, negując ich pozorną przewagę. $\mathcal O(n)$

Otwarty problem?

Uświadomiłem sobie, że ten problem wydaje się trudniejszy niż niektóre obecne otwarte problemy.

Jeszcze słabszym problemem jest określenie:

a d \overset{?}{=} b c

$ad \overset ? = bc$

A jednak słabszy:

a d \overset{?}{=} c

$ad \overset ? = c$

Jest to otwarty problem weryfikacji mnożenia . Jest słabszy, ponieważ gdybyś miał sposób ustalić, czy , to możesz łatwo ustalić, czy , testując przy użyciu algorytmu dwa razy, , . Iff jest prawdą, wiesz, że . $ad \overset ? < bc$ $ad \overset ? = bc$ $ad \overset ? < bc$ $bc \overset ? < ad$ $ad \ne bc$

Teraz był otwartym problemem, przynajmniej w 1986 roku: $ad \overset ? = c$

Złożoność mnożenia i dzielenia. Zacznijmy od bardzo prostego równania ax = b. W przypadku liczb całkowitych sprawdzenie ich możliwości rozwiązania i znalezienie rozwiązania x jest możliwe poprzez dzielenie liczb całkowitych z resztą zera. Do sprawdzenia danego rozwiązania x wystarczy mnożenie liczb całkowitych, ale interesujący jest otwarty problem, czy istnieją szybsze metody weryfikacji.

- ARNOLD SCHÖNHAGE w rozwiązywaniu równań pod względem złożoności obliczeniowej

Co ciekawe, wspomniał także o kwestii weryfikacji mnożenia macierzy :

Ciekawe jest również pytanie, czy weryfikacja mnożenia macierzy, tj. Sprawdzenie, czy AB = G dla danego C, mogłaby być wykonana szybciej.

- ARNOLD SCHÖNHAGE w rozwiązywaniu równań pod względem złożoności obliczeniowej

Zostało to już rozwiązane i rzeczywiście można zweryfikować w czasie za pomocą algorytmu losowego (gdzie jest rozmiarem macierzy wejściowych, więc jest to zasadniczo czas liniowy w rozmiar wejścia). Zastanawiam się, czy jest możliwe zmniejszenie mnożenia liczb całkowitych do mnożenia macierzy, szczególnie z ich podobieństwami, biorąc pod uwagę podobieństwa mnożenia liczb całkowitych Karatsuba do algorytmów mnożenia macierzy, które następnie. Być może w jakiś sposób możemy wykorzystać algorytm weryfikacji macierzy do mnożenia liczb całkowitych. $\mathcal O(n^2)$ $n\times n$

W każdym razie, skoro jest to, według mojej wiedzy, problem otwarty, silniejszy problem pewnością jest otwarty. Jestem ciekawy, czy rozwiązanie problemu weryfikacji równości miałoby jakiś wpływ na problem weryfikacji nierówności porównania. $ad \overset ? < cd$

Niewielka odmiana naszego problemu byłaby, gdyby zagwarantowano, że ułamki zostaną zredukowane do najniższych wartości; w takim przypadku łatwo jest stwierdzić, czy . Czy może to mieć wpływ na weryfikację porównania dla ułamków zredukowanych? $\frac a b \overset ? = \frac c d$

Jeszcze subtelniejsze pytanie, co by było, gdybyśmy mieli sposób przetestować , czy obejmowałoby to testowanie ? Nie rozumiem, jak możesz użyć tego „w obie strony”, tak jak to zrobiliśmy w przypadku . $ad \overset ? < c$ $ad \overset ? = c$ $ad \overset ? < cd$

Związane z:

Przybliżone rozpoznawanie języków nieregularnych przez skończone automaty

Pracują nad przybliżonym pomnożeniem i losową weryfikacją, czego nie do końca rozumiem.
math.SE: Jak porównać dwa mnożenia bez mnożenia?
Załóżmy, że wolno nam wstępnie przetworzyć tak długo, jak chcieliśmy w czasie wielomianowym, czy możemy rozwiązać w czasie liniowym? $c$ $ab=c$
Czy istnieje niedeterministyczny algorytm mnożenia liczb całkowitych w czasie liniowym? Zobacz http://compgroups.net/comp.theory/nondeterministic-linear-time-multiplication/1129399

Istnieją dobrze znane algorytmy mnożenia liczb n-bitowych przez coś takiego jak złożoność O (n log (n) log (log (n))). Nie możemy zrobić nic lepszego niż O (n), ponieważ przynajmniej musimy spojrzeć na całe dane wejściowe. Moje pytanie brzmi: czy rzeczywiście możemy osiągnąć O (n) dla odpowiedniej klasy algorytmów „niedeterministycznych”?

Mówiąc dokładniej, czy istnieje algorytm, który może zaakceptować dwie n-bitowe liczby binarne „a” i „b” oraz 2n-bitową liczbę „c” i powiedzieć w czasie O (n), czy „a * b = c”? Jeśli nie, to czy istnieje jakaś inna forma certyfikatu C (a, b, c), która może być wykorzystana przez algorytm do testowania produktu w czasie liniowym? Jeśli nie czas liniowy, to czy problem testowania produktu jest co najmniej asymptotycznie łatwiejszy niż jego obliczenie? Wszelkie znane wyniki w tym zakresie byłyby mile widziane.

Jan.

―Johnh4717

Realz Slaw
źródło

1

Oto bardzo częściowa próba odrzucenia. Załóżmy, że możemy wykorzystać tylko (stałą liczbę) dodawania i odejmowania w naszym decydującym, a także stałą liczbę wrt predefiniowanych liczb. Innymi słowy, możemy wykonać stałą liczbę , itd. W naszym decydującym. Wtedy jedyne wielkości, które możemy obliczyć, mają postać gdzie są predefiniowanymi stałymi. Zauważ, że można obliczyć w czasie . ${mod}$ $mod\ 2$ $mod\ 3$ $q = k_1 a +k_2 b+k_3 c + k_4 d = \sum k_ia$ $k$ $q$ $O(\sum|a|)$

Edytowane Ten decydujący ma na celu określenie nieco iff . Rozważ przyjęcie jako punktów w . Bit decyduje jej położenia wrt powierzchni , które jest hiperboloidy w 4 wymiarach. Jeśli mamy punkt w przestrzeni wejściowej, decydujący powyżej może obliczyć punkty w ograniczonej odległości od tego punktu wejściowego, tj. Te punkty itd. Definiuje prostopadłościan w przestrzeni 4 d. $B:B=1$ $ad>bc$ $a,b,c,d$ $\mathbb{R}^4$ $B$ $ad = bc$ $(a,b,c,d)$ $q: |q-a| = k_1,$

(Jak uczynić to bardziej precyzyjnym?) Odległość od prostopadłościanu do powierzchni jest zasadniczo nieograniczona, a zatem decydujący nie może obliczyć powierzchni

PKG
źródło

Przepraszam, nie odpowiedziałem na to. Myślę, że może to po prostu przekraczać moje zrozumienie, a tymczasem sam byłem zajęty badaniem możliwych odpowiedzi.

Realz Sław

1

Dobre pytanie. Czy zaakceptowałbyś poziom pewności siebie?

Być może przybliżony podział. To znaczy

Aby obliczyć graniczne przybliżone ilorazy a / b, przesuń w prawo a o ceil (log_2 (b)), a także o floor (log_2 (b)). Wiemy, że dokładny iloraz jest między tymi dwiema wartościami.

Następnie, w zależności od względnych rozmiarów czterech liczb całkowitych, można wykluczyć pewne przypadki i uzyskać 100% pewności.

Można powtórzyć procedurę dla podstawnika innego niż 2, a po kolejnych takich operacjach zwiększyć poziom pewności, aż do momentu, gdy w jakiś sposób zauważy się zmianę znaku / rozstrzygnięcia?

To mój szkic metody z pierwszego szkicu.

Cris Stringfellow
źródło

O (n)

$\mathcal O(n)$

O (n \log n)

$\mathcal O(n \log n)$

a b = c

$ab=c$

1

czy istnieje jakikolwiek sposób decydowania o ad <cb bez konieczności wykonywania [drogich] mnożeń

Pewnie.

Pomysł: porównaj dziesiętne rozwinięcie po kawałku.

Jedyne nieprzyjemne jest to, że musimy najpierw wykluczyć równość, ponieważ w przeciwnym razie możemy nie zakończyć.
Warto najpierw porównać części całkowite, ponieważ jest to łatwe.

Rozważ to:

def less( (a,b), (c,d) ) = {
  // Compare integer parts first
  intA = a div b
  intC = c div d

  if intA < intB
    return True
  else if intA > intB
    return False
  else // intA == intB
    // Normalize to a number in [0,1]
    a = a mod b
    c = c mod d

    // Check for equality by reducing both
    // fractions to lowest terms
    (a,b) = lowestTerms(a,b)
    (c,d) = lowestTerms(c,d)

    if a == c and b == d
      return False
    else
      do
        // Compute next digits in decimal fraction 
        a = 10 * a
        c = 10 * c

        intA = a div b
        intC = c div d

        // Remove integer part again
        a = a mod b
        c = c mod d
      while intA == intC

      return intA < intC
    end
  end
}

Zauważ, że do-whilepętla musi się zakończyć, ponieważ liczby są nierówne. Nie wiemy jednak, jak długo to trwa; jeśli liczby są bardzo zbliżone, może to chwilę potrwać.

$10$ $ad$ $cb$

Czy to jest szybkie? Prawdopodobnie nie. Istnieje wiele liczb całkowitych, modułów i gdcs do obliczenia, i mamy pętlę, której liczba iteracji jest odwrotnie proporcjonalna do odległości między porównywanymi liczbami.

Metoda pomocnicza:

def lowestTerms(a,b) = {
  d = gcd(a,b)
  if d == 1
    return (a,b)
  else
    return lowestTerms(a div d, b div d)
  end
}

Raphael
źródło

a / b

$a/b$

c / d

$c/d$

a d

$ad$

b c

$bc$

a \cdot d

$a\cdot d$

c \cdot b

$c\cdot b$

@DavidRicherby Hm. Głównie myślałem o przepełnieniu - tutaj operacje rzadziej generują ogromne liczby.

Raphael

Porównywanie liczb wymiernych

Odpowiedzi:

Wstępna próba ogólnych zasad

Otwarty problem?