Find the point where a monotonically increasing function becomes positive first time in Python

Hello Folks, In this tutorial, we are going to learn how to find the point where a monotonically increasing function becomes positive first time using Python.

Monotonically Increasing Function

A function is called increasing if it increases as the input x moves from left to right and if the slope of its tangent is positive.

In other words, it is increasing when the slope of the tangent is derivative which is positive.

Given a function, F(x) which takes non-negative integer ‘x’ as input and returns an integer as output.

Some examples:

1. Input : F(x) = (x ** 2 - 5 * x - 10)
   Output: The value n where function() becomes positive first is  7.5

2. Input : F(x) = (x ** 3 - 4 * x - 8)
   Output: The value n where function() becomes positive first is  3.0

3. Input : F(x) = (x ** 2 + 1)
   Output: The value n where function() becomes positive first is 0 

Code :

# Python3 program to find the point where a monotonically
# increasing function becomes positive first time.

def function(x):
    return (x ** 3  - 12 * x - 3)


def positive() :
    
    # If first value is positive
    if (function (0) > 0):
        return 0

    a = 1
    while (function(a) <= 0) :
        a = (a * 2)

    # return binary search
    return Binary(a/2, a)


def Binary(LOW, HIGH):
    
    if (LOW <= HIGH) :

        # Here, MID = (LOW + HIGH)/2
        MID = LOW + (HIGH - LOW)/2;

        if (function(MID) > 0 and (MID == LOW or function(MID-1) 
         <= 0)) :
            return MID

        elif (function(MID) <= 0) :
            return Binary((MID + 1), HIGH)
            
        else :
            return Binary(LOW, (MID - 1))

    # If no positive value is there in the given range,
    # Then return -1
    return -1;

# Implementation of function:
print ("The value of x where a monotonically increasing function" 
       + " becomes positive first time is ", positive());
Input : function(x) = (x * x * x - 12 * x - 3)
Output: The value n where function() becomes positive first is  4.0

Explanation :

1. def positive()

This function returns the value of 'x' where function(x) becomes a positive first time.
2.  a = 1  
    while (function(a) <= 0) : 
        a = (a * 2) 

Find 'HIGH' for binary search by repeated doubling.
3. def Binary(LOW, HIGH) 

This function searches the positive value of function(a) where LOW <= a <= HIGH
4. if (function(MID) > 0 and (MID == LOW or function(MID-1) <= 0)): 
       return MID 

If function(MID) is greater than 0 and one of the following conditions are true: 
(a) MID is equal to LOW 
(b) function(MID - 1) is negative.
5. elif (function(MID) <= 0) : 
       return Binary((MID + 1), HIGH)
 
If function(MID) is smaller than or equal to 0.
6. else : 
       return Binary(LOW, (MID - 1)) 

If function(MID) is greater than 0.
7. return (-1) 

If there is no positive value in the given range then it will return (-1).

If you have any doubts, feel free to ask in comment.

Thank You!

Also read: Print all the Longest Common Subsequences in Lexicographical order in Python

Leave a Reply

Your email address will not be published. Required fields are marked *