Блог пользователя Logarithmic

Автор Logarithmic, история, 8 лет назад, По-английски

Given a range (l, r) where 0.0 <= l,r <= 1.0 we want to find a fraction x/y which satisfies following condition: l <= x/y < r and y should be as small as possible. l and r might have at most 9 digits after floating point.

  • Проголосовать: нравится
  • +18
  • Проголосовать: не нравится

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Just print ((int) (l * 1000000000)) / 1000000000. If you want more precision just add zeroes.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I dont really get why this gives us a fraction with smallest denumerator. Could you please explain it more?

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится -10 Проголосовать: не нравится

      Oops, I misread. I think this algorithm will give you smallest denominator:

      Binary search on the denominator (it should never be the case that a smaller denominator works while a larger one does not, if so please tell). For every denominator, also binary search on the numerator, to try to get num/denom within [l, r). Then you can find the smallest denominator.

      EDIT: Just kidding, it doesn't work

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I was thinking of binary search, but is there any proof that if lets say for d1 > d2 such that for denumerator d1 is not possible, but for d2 is possible? if there is a proof, then binary search is correct. Could you please devise a proof, if you have in mind?

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        That is not correct. Think for example in range [0.4, 0.6]. In this case, denominator 2 works, while denominator 3 doesn't.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    lets say, l = 0.115 and r = 0.125,

    so we want to find a fraction which has smallest denumerator, and for this range it is 2/17. How to find 2/17 with your approach?

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Is y — must smallest as possible???

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Yes, in which it satisfies the condition.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          // l <= x/ y < r --> so l * y <= x < r * y for( long long y = 1; true; ++y) { double x_l = l * y ; double x_r = r * y ; long long x = static_cast<long long>( x_l ); if ( x < x_l - 1.0E-12 ) // if x strong less than x_l, increase it. x++; // now x >= x_l // check x < x_r if ( x < x_r - 1.0E-12) { printf("%d / %d\n", x,y); return 0; } }

          see code

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            for for some y, it could take much more, since it is multiple test case problem.

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              y*r > 0 --> y*r >= 1 --> y >= 1.0 / r

              long long y_min = static_cast< long long>( 1.0 / r );
              for(long long y = y_min; true; ++y){ ...}
              
            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Note tha, binary search does not applicable there.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yes seems same problem. but constraints here are small. What is the solution for this problem?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Logarithmic (previous revision, new revision, compare).

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Ok, I'm not completely sure about this approach, but here it goes. Take u = 1 / l and v = 1 / r. This are numbers bigger than one. Then, the inequality that must be satisfied is . Then,iterate through x's. Binary search for each x the value of y, and for the minimum x such that y exists, that y is your answer. According to my intuition, (sorry, I cannot offer more than that), for most cases this approach will require not more than 106 iterations or so.

UPD: Sorry, it doesn't work.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you explain how it's only 106? Wouldn't you need to iterate over a lot more x-values, in case like [0.573529588, 0.573529590)?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    But if there are somecases in which it takes about 10^8, then it will definitely fail, since it is multiple test case.

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

It seems like you could use the Stern–Brocot tree.

Start at the root. At each node, you either find the solution or have to recurse into one of the children.

If this is too slow you might be able to binary-search how far you walk down left/right before chaning to right/left to get O(log(109)2) time complexity, as the denominator grows at least as fast as the fibonacci series when alternating left/right.

Edit: One might get O(log(109)) complexity by using exponential-search instead of binary-search.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How to apply binary search here? Binary search on y seems not working :( Could you please explain it more detailed?

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you possibly explain your binary search approach. I didn't get your idea.

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 10   Проголосовать: нравится 0 Проголосовать: не нравится

        I'll first explain the basic algorithm on the Stern-Brocot tree similar to here.

        We start with xl = 0, yl = 1, xr = 1, yr = 1. Throughout the algorithm we keep .

        To traverse the tree we look at the middle fraction . If , then is the solution (Correctness follows from the properties of the Stern-Brocot tree).

        If , set xl = xm, yl = ym (This is a move to the right).

        If , set xr = xm, xr = ym (This is a move to the left).

        The above algorithm takes a long time if we keep moving the same direction over and over.

        What we can do, is move k times to the left by setting and similarily for moving to the right.

        The faster algorithm now works as follows: When moving into a certain direction, binary-search for the value of k — how far the slow algorithm would move into that direction before changing directions. Then move k steps into that direction.

        Edit: Fixed some small things.

        Edit2:

        (Messy) Code
»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

For a given ymax, let's ask how many valid fractions with y ≤ ymax there are. For chosen y, the number of valid x's is ry⌋ - ⌊ ly. So the total number of valid fractions is:

Now, note that we can express l as a fraction , where L is an integer. Same with r. It's possible to calculate the sum quickly using this algorithm. Once we can find it, we can do a binary search on that value, and the result will be the smallest ymax that produces a non-zero result.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks for the solution. One more point, it should be strictly less than r. how to exclude that? is the only way just to replace r with some r-eps?

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

      I would subtract the number of x = ry from the result (and add the number of x = ly because the other inequality is  ≤ ). If where p,q are coprime, then a valid (x, y) pair is in the form (kp, kq) with k integer, so there are such points.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Let me show a test which your formula gives wrong answer:

    l = 0.125 and r = 0.130 your formula gives 4 / 31 , but correct answer is 1/8.

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

      Without the clarification I made in my other comment above it is indeed incorrect. You need to add , where qr and ql are denominators of and respectively, after simplifying the fractions (qr = 100 and ql = 8 in your case).

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Thx, now understand.

        your link not worked for me, can share another link ?

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится +13 Проголосовать: не нравится

          Did you try adding www or http to the beginning of the address? The outline of the idea is:

          Let's take a sum with p and q coprime. If n ≥ q or p > q, they can be reduced to n mod q (since ) and p mod q (since ) by adding a constant. Now, let . After a few transformations we can get . Since p < q, we can again reduce q to q mod p and so on. The reductions structure will be the same as gcd calculation, and a single step will take constant time, giving overall O(log(p)+log(q)) complexity.

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            The last formula only holds when xq/p is never an integer for x from 1 to m. I think this can happen from time to time.

            • »
              »
              »
              »
              »
              »
              »
              6 лет назад, # ^ |
                Проголосовать: нравится +10 Проголосовать: не нравится

              After the first two steps, we have that n < q, p ≤ q. Hence m < p. As p and q are coprime, p divides xq if and only if p divides x. But 0 < x ≤ m < p contradiction. Hence is never an integer.

              (And the post you replied to was 2 years old.)

              • »
                »
                »
                »
                »
                »
                »
                »
                6 лет назад, # ^ |
                Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                Yes, you are right. I was think of the situation when n is greater than q.

                (aren't you curious why you get 10 thumbs up under a blog that is 2 years old?)

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Logarithmic (previous revision, new revision, compare).