CODEWITHSUNDEEP
pythonfunctionloopsfor-loop
Hamse Ibrahim
Hamse Ibrahim

Reputation: 11

function for finding the nearest number of a given value

I was practicing with function and I encountered this problem. I would be grateful if someone gave me pointers on how to solve it.

Python function given below in a monotonically increasing function in N. Find the N value that makes G(N) as close 124599 as possible. You may use trial and error or you may use a for loop

def G(N):
  a, b = 7, 9
  while N > 2:
    N = N - 1
    a = b
    b = int(0.83*a + 0.83*b)
  return b

I have tried to use for in range loop but the numbers I get are too small compare to the given number.

Upvotes: 0

Views: 96

Answers (2)

user4442671
user4442671

Reputation:

The key point here is that the function is monotonically increasing. That means that in between two points, the function can only go up.

So if G(A) < target and G(B) > target then, and only then, the answer we seek will be between A and B, and it will be there only once.

Knowing this, all we need to do is evaluate G() at the midpoint between A and B, and compare that result to the target to narrow down the range until we stop making progress. aka: a binary search.

Here's a rather verbose (for clarity) way to do that:

def monotonic_closest(Func, target, integral):
  # First, find points below and above the target
  bottom = -1
  while G(bottom) > target:
    bottom *= 2

  top = 1
  while G(top) < target:
    top *= 2

  # Now narrow down the range until we stall.
  while True:
    # Get a halfway point
    if integral:
      mid = (top + bottom) // 2
    else:
      mid = (top + bottom) / 2
    
    if G(mid) > target:
      # We are stalling, stop
      if top == mid:
        return mid
      
      # narrow the range
      top = mid
    else:
      # We are stalling, stop
      if bottom == mid:
        return mid
    
      # narrow the range
      bottom = mid




result = monotonic_closest(G, 124599, integral=True)

Depending on the shape of the function, there are other methods that can converge faster, but the simply binary search has the advantage of being consistent, no matter what the function is.

Upvotes: 1

Acccumulation
Acccumulation

Reputation: 3591

One of the first things that comes to mind when dealing with this sort of problem is a binary search. At the moment, there is no upper limit to the search space, so the first step would be to find one. Going by powers of ten, that would be:

guess = 1
target = 124599
while G(guess) < target:
    guess = 10*guess

From there, you can set your upper limit to guess and do a binary search:

lower = 0
upper = guess
while True:
    difference = upper - lower
    if difference < 2:
        break
    midpoint = lower + difference//2
    if G(midpoint) > target:
        upper = midpoint
    if G(midpoint) < target:
        lower = midpoint

However, you can also use math to solve it. Just before the line b = int(0.83*a + 0.83*b), a has been set to b. So this is just b = int(0.83*b + 0.83*b), which is equivalent to b = int(1.66*b). If it weren't for the int part, this would be just be multiplying b by 1.66 over and over again, so we would get b*1.66^k. If we take the initial value of 9, we get 9*1.66^k = 12599, or 1.66^k = 1399.888888888889. Next, we can take the log of both sides. This gets us k log(1.66) = log( 1399.888888888889), or k = log(1399.888888888889)/log(1.66) = 14.29.

With the first method, I got 21. The second number is off because G(N) doesn't get started until N is greater than 2, and it grows slower than 1.66x at the beginning because of the rounding of int. If you were to start later in the series, such as at 10, you'd get

G(10) = 473
G(k) = 124599
G(k)/G(10) = 263.4
log(263.4)/log(1.66) = 10.997

Rounding to the nearest integer, this would tell you that the number you're looking for is 11 greater than 10, or 21.

Upvotes: 0

Related Questions