Complexity of approximating functions on real-life computers

Результат исследования: Научные публикации в периодических изданияхстатья

Аннотация

We address the problem of estimating the computation time necessary to approximate a function on a real computer. Our approach gives a possibility to estimate the minimal time needed to compute a function up to the specified level of error. This can be explained by the following example. Consider the space of functions defined on [0,1] whose absolute value and the first derivative are bounded by C. In a certain sense, for almost every such function, approximating it on its domain using an Intel x86 computer, with an error not greater than ε, takes at least k(C, ε) seconds. Here we show how to find k(C, ε).

Язык оригиналаанглийский
Страницы (с-по)153-157
Число страниц5
ЖурналInternational Journal of Foundations of Computer Science
Том26
Номер выпуска1
DOI
СостояниеОпубликовано - 25 янв 2015
Опубликовано для внешнего пользованияДа

Fingerprint Подробные сведения о темах исследования «Complexity of approximating functions on real-life computers». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать