Porównywanie liczb wymiernych

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

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

Moje pytania to:

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

1. 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$
2. Czy istnieje szybsza metoda porównywania liczb wymiernych niż pomnożenie mianowników.

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$

$$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:

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

Kolejna zasada:

$$(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.

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

$$\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:

$$\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:

$$\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:

$$\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:

$$ad \overset ? = bc$$

A jednak słabszy:

$$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 .a d ? = b c a d ? < b c b c ? < a d a d ≠ b $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.n × $\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 .o d ? = c a d ? < c $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?a b = $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

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.a d > b c a , b , c , d R 4 B a d = b c ( a , b , c , d ) q : | q - a | = k 1$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

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.

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
}