####ID 49-find-the-root
####
####  Άσκηση: 
####
#### Σε αυτή την άσκηση θα πρέπει να γράψετε μια συνάρτηση
####
####   root(f, a, b, eps)
####
#### η οποία θα βρίσκει τη ρίζα της συνάρτησης f στο διάστημα [a,b] με ακρίβεια το πολύ eps.
####
#### Η συνάρτηση f υποθέτουμε ότι είναι μια γνησίως αύξουσα και συνεχής συνάρτηση στο διάστημα [a,b] με αρνητική τιμή στο a
#### και θετική τιμή στο b, άρα έχει ακριβώς μια ρίζα, έστω r, στο διάστημα αυτό. Η συνάρτησή σας θα πρέπει να επιστρέφει
#### ένα αριθμό στο [a,b] του οποίου η απόσταση από τη ρίζα r να είναι το πολύ eps (ένας μικρός θετικός αριθμός).
####
#### Το πρόγραμμά σας θα πρέπει να δουλεύει για κάθε συνάρτηση f που ικανοποιεί τις παραπάνω προϋποθέσεις.
####
#### Θα πρέπει επίσης να μην υπολογίζει τη συνάρτηση f περισσότερες φορές απ' όσο χρειάζεται. Γι' αυτό η συνάρτηση f
#### είναι γραμμένη με τέτοιο τρόπο ώστε αν την καλέσετε περισσότερες φορές απ' ό,τι έχετε δικαίωμα τότε να σταματάει
#### να δουλεύει (επιστρέφει πάντα 0 από τότε και πέρα).
####
#### Αν L=b-a είναι το μήκος του διαστήματος τότε έχετε δικαίωμα να καλέσετε τη συνάρτηση f το πολύ
####
####  log_2(L/eps)+2
####
#### φορές (log_2 σημαίνει λογάριθμο με βάση το 2). Αν π.χ. a=0, b=1 και eps=1e-4 τότε ο αριθμός αυτός είναι 16.
####
#### Προσπαθείτε να υποδιπλασιάζετε κάθε φορά το μήκος του διαστήματος στο οποίο είστε σίγουροι ότι είναι εγκλωβισμένη
#### η ρίζα.
####
#### *** Γενικές Οδηγίες: ***
####
#### Γράφετε τον κώδικά σας αποκλειστικά ανάμεσα στις γραμμές START και STOP παρακάτω.
#### Δεν πρέπει να πειράξετε καθόλου τις υπόλοιπες γραμμές
####
#### Για να τρέξετε το πρόγραμμά σας (αποθηκευμένο στο αρχείο user.py) δίνετε την εντολή
####
####    python3 user.py
####
#### ενώ για να το ελέγξετε με τον tester δίνετε την εντολή
####
####    python3 tester.py
####
#### φροντίζοντας τα αρχεία user.py και tester.py να είναι στον ίδιο κατάλογο (directory)
####
#### ****ΠΡΟΣΟΧΗ*****ΠΡΟΣΟΧΗ*****ΠΡΟΣΟΧΗ*****ΠΡΟΣΟΧΗ*****ΠΡΟΣΟΧΗ*****ΠΡΟΣΟΧΗ****
#### Μη γράψετε καμιά εντολή εισόδου (input) ή εξόδου (print)
#### στον κώδικα που θα βάλετε ανάμεσα στα START και STOP. Αυτά είναι ήδη γραμμένα.
#### Αν βάλετε και σεις το πρόγραμμά σας βγαίνει λάθος.
####


import math	####

def fnc(x):	####
    """ Αυτή είναι η συνάρτηση της οποίας τη ρίζα ψάχνουμε. Ο τύπος της φαίνεται στο πρώτο return παρακάτω. """	####
    global a, b, eps	####
    if not hasattr(fnc, "counter"):	####
        fnc.counter = 0	####
        fnc.maxtimes = (int)(0.1+math.ceil(math.log((b-a)/eps, 2.0)+2))	####
    if fnc.counter<fnc.maxtimes:	####
        fnc.counter += 1	####
        return x*x*x-x-0.1 # Αν θέλετε να αλλάξετε τη συνάρτηση αλλάξτε μόνο αυτή τη γραμμή αλλά και τα a, b παρακάτω	####
                           # αλλά θα πρέπει όποια συνάρτηση βάλετε να είναι γνησίως αύξουσα και συνεχής στο [a,b]	####
                           # Θα πρέπει επίσης να αλλάξετε την τιμή trueroot παρακάτω και στη θέση της να βάλετε την	####
                           # ακριβή τιμή της ρίζας της συνάρτησής σας.	####
    else:	####
        return 0.0	####

# Για να δοκιμάσετε το πρόγραμμά σας μπορείτε να αλλάξετε τις παρακάτω τρεις παραμέτρους και	####
# να τροποιήσετε τη συνάρτηση fnc που είναι γραμμένη πιο πάνω	####
a=-1.0	####
b=-0.8	####
eps=1e-8	####


####
#### Υποθέσεις:
####
####  Στο σημείο αυτό έχει καθοριστεί η συνάρτηση f το διάστημα a, b και η ακρίβεια eps
#### 
#### Απαιτήσεις:
####
####  Στο τέλος του προγράμματός σας θα πρέπει
####
####    η συνάρτηση root
####
#### να υπολογίζει αυτό που περιγράφεται στην εκφώνηση.
####
####START Από δω και κάτω γράφετε το πρόγραμμά σας.----------------------------------------------------------------

#### Γράφετε τη συνάρτησή σας εδώ. Για να υπολογίσετε τη συνάρτηση f (της οποίας τη ρίζα ψάχνετε) σε ένα σημείο x
#### μπορείτε απλά να γράφετε f(x) μέσα στη συνάρτησή σας, σαν η συνάρτηση f να ήταν ορισμένη με def παραπάνω
####
def root(f, a, b, eps): ####


####STOP Μην αλλάξετε ό,τι είναι από τη γραμμή αυτή και κάτω--------------------------------------------------------
r = root(fnc, a, b, eps)	####
trueroot = -0.94564927392359 # Αυτή είναι η σωστή τιμή της ρίζας για τη συνάρτηση fnc που είναι γραμμένη παραπάνω	####
print("Root found is",r,". True root is",trueroot)	####
if abs(r-trueroot)<eps:	####
    print("OK, close enough")	####
else:	####
    print("Not OK. Too far.")	####
print("The function was evaluated {n} times ({m} was maximum).".format(n=fnc.counter, m=fnc.maxtimes))	####