二分探索を使用して、特定のYのXを見つけることができます。これは対数時間計算量であり、x値の範囲のサイズをエラー許容度で割ったものに比例します。
def solveForX(polyFunc, minX, maxX, y, epsilon):
midX = (minX + maxX) / 2.0
if abs(polyFunc(midX) - y) < epsilon:
return midX
if polyFunc(midX) > y:
return solveForX(polyFunc, minX, midX, y, epsilon)
else:
return solveForX(polyFunc, midX, maxX, y, epsilon)
print solveForX(lambda x: x*x, 0, 100, 2, 0.01)
出力:
1.416015625
編集:コメント内のアイデアを拡張するために、複数のX値を検索することがわかっている場合は、[minX、maxX]の検索範囲を絞り込むことができます。
def solveForManyXs(polyFunc, minX, maxX, ys, epsilon):
if len(ys) == 0:
return []
midIdx = len(ys) / 2
midY = ys[midIdx]
midX = solveForX(polyFunc, minX, maxX, midY, epsilon)
lowYs = ys[:midIdx]
highYs = ys[midIdx+1:]
return solveForManyXs(polyFunc, minX, midX, lowYs, epsilon) + \
[midX] + \
solveForManyXs(polyFunc, midX, maxX, highYs, epsilon)
ys = [1, 2, 3]
print solveForManyXs(lambda x: x*x, 0, 100, ys, 0.01)
出力:
[1.0000884532928467, 1.41448974609375, 1.7318960977718234]