SoundGradientDescent.py

from math import *
import time

d = 0.0000001           #precision, used for derivatives
eps = .2                #coefficient for step size

x = 5                   #starting x and y
y = 5
tx= 0
ty = 0

avErr = 0               #used for accuracy analysis

px = 0                  #previous x and y
py = 0
da = 0                  #delay between stations a,b,c
db = 0
dc = 0

def f(x,y):             #our function function
  return greatest(sqrt((10-x)**2 + y*y)-da,sqrt(x*x+y*y)-db,sqrt(x*x+ (10-y)**2)-dc)

def dfx(x,y):           #derivative of f in the x direction
  return (f(x,y)-f(x-d,y))/d

def dfy(x,y):           #derivative of f in the y direction
    return (f(x,y)-f(x,y-d))/d

def newx(x,y):          #calculates new x position
    return px - dfx(px,py)*eps

def newy(x,y):          #calculates new y position
    return py - dfy(px,py)*eps

def receive(x=-1,y=-1): #gets and processes input coordinates - this will not be needed later
    global da,db,dc,tx,ty
    if x ==-1 and y==-1:        #if we receive no x or y value, ask for them
        x = float(input("X Value: "))
        y = float(input("Y Value: "))
    #======Accuracy Analysis=========
    tx = x              #target x and y values
    ty = y
    #=============End================
    da = sqrt((10-x)**2+y*y)      #calculate distance between point and station
    db = sqrt(x*x+y*y)
    dc = sqrt(x*x+(10-y)**2)
    if da<=db and da<=dc:         #subtract whichever is the smallest to simulate unknown delay
        #print("A is the smallest at ",da)
        dc = dc-da
        db = db-da
        da=0
    elif db<da and db<=dc:
        #print("B is the smallest at ",db)
        dc=dc-db
        da=da-db
        db=0
    elif dc<da and dc<db:
        #print("C is the smallest at ",dc)
        db-=dc
        da-=dc
        dc=0

def greatest(_a,_b,_c):           #a max operator for three vars
    if _a>=_b and _a>=_c:
        return _a
    elif _b>_a and _b >=_c:
        return _b
    elif _c>_b and _c>_a:
        return _c

def gradientDescent():            #the math part - the gradient descent algorithm
    global px,py,x,y
    x = 5
    y = 5
    pfxy = 0;
    pfxy2 = 0;
    cf = f(x,y);
    c=0
    while abs(cf-pfxy)>0.0001 and abs(cf-pfxy2)>0.0001:     #do until previous values are really close to current values
        px = x
        py = y
        pfxy2 = pfxy
        pfxy = cf
        x = newx(px,py)
        y = newy(px,py)
        cf = f(x,y)
        c+=1
        if c > 100:
            break

#start main program

t = time.time()
for g in range(10):             #this prints the accuracy of each integer point
    line = ""
    for h in range(10):
        receive(9-g,h)
        gradientDescent()
        avErr = avErr+sqrt((tx-x)**2+(ty-y)**2)
        line = line + str(int(sqrt((tx-x)**2+(ty-y)**2)*100)/100) + "\t"
    print(line)

print((time.time()-t)/100," seconds per point")
print("Average error of ", avErr/(100), " over ", 100, " runs")