Membandingkan bilangan rasional

Diberikan dan , b , d ∉ { 0 $a,b,c,d \in \mathbb N$$b,d \notin \{0\}$

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

Pertanyaan saya adalah:

Diberikan$a,b,c,d$

1. Dengan asumsi kita dapat memutuskan dalam , apakah ada cara untuk memutuskan tanpa harus terlebih dahulu membentuk multiplikasi (atau divisi), dan . Atau ada semacam bukti bahwa tidak mungkin.O ( | x | + | y | ) a d < c b a ⋅ d c ⋅ $x < y \in \mathbb Z$$\mathcal{O}(|x| +|y|)$$ad<cb$$a\cdot d$$c \cdot b$
2. Apakah ada metode yang lebih cepat untuk membandingkan bilangan rasional daripada mengalikan penyebutnya.

Penelitian saya saat ini:

Upaya awal pada beberapa aturan umum

Seseorang dapat mencoba membuat beberapa aturan umum untuk menyelesaikan perbandingan rasional:

Dengan asumsi semua positif :$a,b,c,d$

$$a < b \wedge c \ge d \Longrightarrow \frac a b < \frac c d\\ $$ Ini pada dasarnya berarti, jika sisi kiri kurang dari satu, dan sisi kanan setidaknya satu, sisi kiri kurang dari kanan sisi. Dalam nada yang sama:

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

Aturan lain:

$$(b > d) \wedge (a \le c) \Rightarrow \left[\frac a b < \frac c d\right]$$ Saya menganggap aturan ini logis, karena semakin besar penyebutnya, semakin kecil angkanya, sedangkan semakin besar pembilang, semakin besar angkanya. Karenanya jika sisi kiri memiliki penyebut yang lebih besar dan pembilang yang lebih kecil, maka yang kiri akan lebih kecil.

Mulai dari sini, kita akan menganggap bahwa , karena kalau tidak kita dapat menyelesaikannya dengan aturan di atas, atau membalikkan pertanyaan menjadi , dan bagaimanapun kita berakhir dengan kondisi ini.$a<c \wedge b < d$$\frac c d \overset ? < \frac a b$

Aturan : Ini Pada dasarnya aturan menyatakan bahwa Anda selalu dapat mengurangi pembilang dari penyebut, dan mengatur hasilnya sebagai pembilang, untuk mendapatkan masalah yang setara. Saya akan meninggalkan buktinya.

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

Aturan ini memungkinkan Anda untuk mengurangi pembilang dan penyebut kiri dari pembilang dan penyebut kanan untuk masalah yang setara.

Dan tentu saja ada scaling:

$$\left. \\ \frac {ak} {bk} < \frac {c} {d} \iff \left[\frac a b < \frac c d\right] \right|_{a<c,b<d} \\ $$ You dapat menggunakan penskalaan untuk membuat aturan pengurangan di atas lebih signifikan.

Menggunakan aturan-aturan ini Anda dapat bermain-main dengan hal-hal, menerapkannya berulang kali, dalam kombinasi cerdas, tetapi ada kasus di mana angka-angka dekat, dan patologis.

Dengan menerapkan aturan sebelumnya, Anda dapat mengurangi semua masalah ini ke:

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

Terkadang Anda bisa menyelesaikannya secara langsung sekarang, kadang tidak. Kasus patologis biasanya dalam bentuk:

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

Kemudian Anda membalikkannya, dan menghasilkan hal yang sama, hanya dengan sedikit kurang Setiap aplikasi aturan + flip menguranginya dengan digit / bit. AFAICT, Anda tidak dapat dengan cepat menyelesaikannya, kecuali jika Anda menerapkan aturan kali (satu kali untuk setiap digit / bit) dalam kasus patologis, meniadakan keuntungan yang tampak.$\mathcal O(n)$

Masalah terbuka ??

Saya menyadari bahwa masalah ini tampaknya lebih sulit daripada beberapa masalah terbuka saat ini.

Masalah yang bahkan lebih lemah adalah menentukan:

$$ad \overset ? = bc$$

Namun lebih lemah:

$$ad \overset ? = c$$

Ini adalah masalah terbuka untuk memverifikasi multiplikasi . Itu lebih lemah, karena jika Anda memiliki cara untuk menentukan , maka kamu dapat dengan mudah menentukan , dengan menguji menggunakan algoritma dua kali, , . Jika salah benar, Anda tahu itu .$ad \overset ? < bc$$ad \overset ? = bc$$ad \overset ? < bc$$bc \overset ? < ad$$ad \ne bc$

Sekarang, adalah masalah terbuka, setidaknya pada tahun 1986:$ad \overset ? = c$

Kompleksitas multiplikasi dan pembagian. Mari kita mulai dengan persamaan kapak yang sangat sederhana = b. Ketika dipertimbangkan atas bilangan bulat, menguji solvabilitasnya dan menemukan solusi x dimungkinkan oleh pembagian bilangan bulat dengan sisa nol. Untuk memeriksa solusi x yang diberikan, perkalian integer sudah cukup, tetapi merupakan masalah terbuka yang menarik apakah ada metode verifikasi yang lebih cepat.

- ARNOLD SCHÖNHAGE dalam Penyelesaian Persamaan dalam Hal Kompleksitas Komputasi

Sangat menarik, ia juga menyebutkan pertanyaan memverifikasi perkalian matriks :

Ini juga merupakan pertanyaan yang menarik apakah verifikasi perkalian matriks, yaitu, memeriksa apakah AB = G untuk C yang diberikan, mungkin dapat dilakukan lebih cepat.

- ARNOLD SCHÖNHAGE dalam Penyelesaian Persamaan dalam Hal Kompleksitas Komputasi

Ini telah dipecahkan, dan memang mungkin untuk memverifikasi dalam waktu dengan algoritma acak (dengan menjadi ukuran matriks input, jadi pada dasarnya waktu linear dalam ukuran input). Saya bertanya-tanya apakah mungkin untuk mengurangi perkalian bilangan bulat ke perkalian matriks, terutama dengan kesamaan mereka, mengingat kesamaan multiplikasi bilangan bulat Karatsuba dengan algoritma perkalian matriks yang diikuti. Maka mungkin dengan beberapa cara kita dapat memanfaatkan algoritma verifikasi perkalian matriks untuk perkalian integer.$\mathcal O(n^2)$$n\times n$

Lagi pula, karena ini masih, setahu saya, masalah terbuka, masalah yang lebih kuat dari pasti terbuka. Saya ingin tahu apakah menyelesaikan masalah verifikasi kesetaraan akan berpengaruh pada masalah verifikasi ketidaksetaraan perbandingan.$ad \overset ? < cd$

Sedikit variasi dari masalah kita adalah jika fraksi dijamin akan dikurangi ke tingkat terendah; dalam hal ini mudah untuk mengetahui apakah . Apakah ini ada kaitannya dengan verifikasi perbandingan untuk fraksi yang dikurangi?$\frac a b \overset ? = \frac c d$

Pertanyaan yang bahkan lebih halus, bagaimana jika kami memiliki cara untuk menguji , apakah ini akan mencakup pengujian ? Saya tidak mengerti bagaimana Anda dapat menggunakan "dua arah" ini seperti yang kami lakukan untuk .$ad \overset ? < c$$ad \overset ? = c$$ad \overset ? < cd$

Terkait:

• Perkiraan Pengakuan Bahasa Non-reguler oleh Finite Automata

  Mereka mengerjakan beberapa perkiraan perkalian, dan verifikasi acak, yang saya tidak sepenuhnya mengerti.

• math.SE: Bagaimana Membandingkan dua perkalian tanpa mengalikan?
• Misalkan kita diizinkan untuk preproses sebanyak yang kita inginkan dalam waktu polinomial, dapatkah kita menyelesaikan dalam waktu linier?$c$$ab=c$
• Apakah ada algoritma multiplikasi integer nondetermistic linear-time? Lihat http://compgroups.net/comp.theory/nondeterministic-linear-time-multiplication/1129399

  Ada algoritma terkenal untuk mengalikan angka n-bit dengan sesuatu seperti kompleksitas O (n log (n) log (log (n))). Dan kita tidak dapat melakukan lebih baik daripada O (n) karena setidaknya kita harus melihat seluruh input. Pertanyaan saya adalah: dapatkah kita benar-benar mencapai O (n) untuk kelas yang sesuai dari algoritma "nondeterministic"?

  Lebih tepatnya, apakah ada algoritma yang dapat menerima dua angka biner n-bit "a" dan "b" dan angka 2n-bit "c" dan memberi tahu Anda dalam waktu O (n) apakah "a * b = c"? Jika tidak, adakah bentuk lain dari sertifikat C (a, b, c) sehingga algoritma dapat menggunakannya untuk menguji produk dalam waktu linier? Jika bukan waktu linier, apakah masalah pengujian produk setidaknya secara asimptotik lebih mudah daripada menghitungnya? Setiap hasil yang diketahui di sepanjang garis ini akan diterima.

  John

  ―Johnh4717

Ini adalah upaya yang sangat parsial untuk menolak. Misalkan kita hanya dapat menggunakan penambahan (jumlah konstan) dan pengurangan pada penentu kita, serta jumlah konstan wrt angka yang telah ditentukan. Dengan kata lain, kita dapat melakukan jumlah konstan dari , , dll dalam penentuan kita. Maka jumlah yang dapat kita hitung adalah dalam bentuk mana adalah konstanta yang telah ditentukan sebelumnya. Perhatikan bahwa dapat dihitung dalam waktu .${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|)$

Diedit Penentu ini dimaksudkan untuk menentukan sedikit iff . Pertimbangkan mengambil sebagai poin dalam . Bit ditentukan oleh posisinya di permukaan yang merupakan hiperboloid dalam 4 dimensi. Jika kita memiliki titik di ruang input, penentu di atas dapat menghitung titik dalam jarak terbatas dari titik input ini, yaitu titik-titik dll. Ini mendefinisikan berbentuk kubus dalam ruang 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,$

(Bagaimana membuat ini lebih tepat?) Jarak dari kuboid ke permukaan secara umum tidak terbatas, dan karenanya permukaan tidak dapat dihitung oleh penentu.

Pertanyaan bagus. Apakah Anda akan menerima tingkat kepercayaan?

Mungkin melakukan perkiraan pembagian. Yaitu

Untuk menghitung perkiraan quotients terikat dari a / b, geser ke kanan dengan ceil (log_2 (b)) dan juga dengan floor (log_2 (b)). Maka kita tahu hasil bagi yang akurat adalah antara kedua nilai ini.

Kemudian, tergantung pada ukuran relatif dari empat bilangan bulat, seseorang mungkin dapat mengesampingkan kasus-kasus tertentu, dan mendapatkan kepercayaan 100%.

Seseorang dapat mengulangi prosedur untuk radix selain 2, dan dengan suksesi operasi semacam itu meningkatkan tingkat kepercayaan, sampai suatu perubahan tanda / tie-break teramati?

Itu adalah sketsa konsep metode pertama saya.

apakah ada cara untuk memutuskan iklan <cb tanpa harus melipatgandakan multiplikasi [mahal]

Tentu.

Ide: Bandingkan ekspansi desimal sedikit demi sedikit.

Satu-satunya hal yang buruk adalah bahwa kita harus mengecualikan kesetaraan terlebih dahulu karena kalau tidak kita tidak boleh mengakhiri.
Sangat berguna untuk pertama-tama membandingkan bagian integer karena itu mudah.

Pertimbangkan ini:

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
}

Perhatikan bahwa do-whileloop harus diakhiri karena angkanya tidak sama. Kami tidak tahu berapa lama itu berjalan; jika angkanya sangat dekat, bisa jadi sementara.

Jelas, tidak ada perkalian yang mahal; satu-satunya yang kita butuhkan adalah mengalikan nominator dengan . Secara khusus, kami menghindari penghitungan dan secara eksplisit.$10$$ad$$cb$

Apakah ini cepat? Mungkin tidak. Ada banyak divisi integer, modulos, dan gdcs untuk dihitung, dan kami memiliki loop yang jumlah iterasinya berbanding terbalik dengan jarak antara angka yang kami bandingkan.

---

Metode pembantu:

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