Given two irreducible fractions def

Given two irreducible fractions defining an interval, we investigate the problem of finding the fraction of smallest
denominator in this interval. Keeping integers as small as possible can be crucial for exact arithmetic computations. Indeed,
even if exact arithmetic libraries [3] provide efficient tools to handle exact computations on arbitrarily large integers, dealing
with big integers remains computationally expensive. Thus, when a parameter value has to be chosen in a given interval,
it may be interesting to choose the value involving integers as small as possible to enable fast computations. This problem
also has a nice geometric interpretation and arises for instance in the computation of the integer hull of a polygon [5].
In this note, we consider two irreducible proper fractions f and g such that 0 ≤ f < g ≤ 1. We give a characterization of
the irreducible proper fraction h such that f < h < g and the denominator of h is as small as possible. Finally, we provide
an output-sensitive algorithm to compute h from the continued fraction decompositions of f and g.

ผลลัพธ์ (ไทย) 1:

เราได้รับสองเศษส่วนอย่างต่ำการกำหนดช่วงเวลา ตรวจสอบปัญหาการหาสัดส่วนของขนาดเล็กที่สุดส่วนในช่วงนี้ เก็บจำนวนเต็มเล็กที่สุดสามารถเป็นสิ่งสำคัญสำหรับการคำนวณทางคณิตศาสตร์ที่แน่นอน แน่นอนถ้าไลบรารีคณิตศาสตร์แน่นอน [3] มีเครื่องมือที่มีประสิทธิภาพการจัดการประมวลผลที่แน่นอนในจำนวนเต็มใหญ่อย่า แจกด้วยจำนวนเต็มใหญ่ยังคง computationally ราคาแพง ดังนั้น เมื่อค่าพารามิเตอร์มีให้เลือกในช่วงที่กำหนดคุณอาจสนใจที่จะเลือกค่าเกี่ยวข้องกับจำนวนเต็มเล็กที่สุดในการเปิดใช้งานการประมวลผลที่รวดเร็ว ปัญหานี้นอกจากนี้ยังมีการตีความทางเรขาคณิตดี และเกิดขึ้นเช่นในการคำนวณของตัวถังจำนวนเต็มของรูปหลายเหลี่ยม [5]ในหมายเหตุนี้ เราพิจารณาสองเศษส่วนอย่างต่ำที่เหมาะสม f และ g ดังกล่าวที่ f 0 ≤ < g ≤ 1 เราให้เป็นสมบัติของชั่วโมงเศษส่วนอย่างต่ำเช่น f ที่ < h < g และตัวส่วนของ h มีขนาดเล็กที่สุด ในที่สุด เราให้การอัลกอริธึมไวต่อผลลัพธ์การคำนวณ h จาก decompositions เศษส่วนต่อเนื่องของ f และ g

ผลลัพธ์ (ไทย) 2:

ได้รับสองเศษส่วนอย่างต่ำการกำหนดช่วงเวลาเราจะตรวจสอบปัญหาการหาส่วนของที่เล็กที่สุด
ส่วนในช่วงเวลานี้ การรักษาจำนวนเต็มขนาดเล็กที่สุดเท่าที่เป็นไปได้อาจจะเป็นสิ่งสำคัญสำหรับการคำนวณทางคณิตศาสตร์ที่แน่นอน อันที่จริง
แม้ว่าห้องสมุดทางคณิตศาสตร์ที่แน่นอน [3] มีเครื่องมือที่มีประสิทธิภาพในการจัดการกับการคำนวณที่ถูกต้องในจำนวนเต็มขนาดใหญ่โดยพลการจัดการ
กับจำนวนเต็มใหญ่ยังคงมีราคาแพงคอมพิวเตอร์ ดังนั้นเมื่อค่าพารามิเตอร์ที่จะต้องมีการแต่งตั้งในช่วงเวลาที่กำหนด
ก็อาจจะเป็นที่น่าสนใจให้เลือกค่าที่เกี่ยวข้องกับจำนวนเต็มขนาดเล็กเป็นไปได้ที่จะช่วยให้การคำนวณอย่างรวดเร็ว ปัญหานี้
นอกจากนี้ยังมีการตีความทางเรขาคณิตที่ดีและเกิดขึ้นเช่นในการคำนวณของฮัลล์จำนวนเต็มของรูปหลายเหลี่ยม [5].
ในบันทึกนี้เราพิจารณาสองเศษส่วนที่เหมาะสมลดลง F และ G ดังกล่าวที่ 0 ≤ F <กรัม≤ 1. เรา ให้ตัวละครของ
ลดลงส่วนเอชที่เหมาะสมดังกล่าวว่า F <H <กรัมและส่วนของ H เป็นขนาดเล็กที่สุดเท่าที่เป็นไปได้ สุดท้ายเราให้
อัลกอริทึมการส่งออกที่มีความไวในการคำนวณชั่วโมงจากการสลายตัวส่วนอย่างต่อเนื่องของ F และ G

ผลลัพธ์ (ไทย) 3:

ได้รับสองลดเศษส่วนกำหนดช่วงเวลาที่เราตรวจสอบปัญหาของการหาสัดส่วนเล็กหน่วยเงินในช่วงเวลานี้ เก็บจำนวนเต็มเล็กที่สุดสามารถที่สำคัญสำหรับการคำนวณเลขคณิตแน่นอน . แน่นอนแม้ว่าแน่นอนคณิตศาสตร์ห้องสมุด [ 3 ] ให้เครื่องมือที่มีประสิทธิภาพที่จะจัดการกับการคำนวณที่แน่นอนบนจำนวนเต็มขนาดใหญ่โดยพลการ จัดการกับจำนวนเต็มใหญ่ยังคง computationally แพง ดังนั้นเมื่อค่าพารามิเตอร์จะต้องมีการเลือกในช่วงเวลาที่กําหนดมันอาจจะน่าสนใจที่จะเลือกค่าที่เกี่ยวข้องกับจำนวนเต็มเล็กที่สุดเพื่อให้วิธีการที่รวดเร็ว ปัญหานี้นอกจากนี้ยังมีการตีความทางเรขาคณิตดีและมีตัวอย่างในการคำนวณจำนวนเต็มตัวเรือของรูปหลายเหลี่ยม [ 5 ]ในบันทึกนี้ เราพิจารณาสองลดเศษส่วนที่เหมาะสม F และ G ที่ 0 ≤ F < G ≤ 1 เราได้ให้ลักษณะเฉพาะของการลดสัดส่วนที่เหมาะสม ( เช่น F < h < G และตัวส่วนของ H เป็นขนาดเล็กที่สุด ในที่สุด , เราให้ออกไวขั้นตอนวิธีคำนวณ H จากเศษส่วนต่อเนื่อง decompositions ของ F G