Целочисленная арифметика и арифметика многократной точности
Пусть M(n) – время выполнения программы P на входе размером n. В работе [BLR] были разработаны программные чекеры для функций, представленных в таблице 4.1. Там же приведены ресурсозатраты на выполнение самотестирующейся/ самокорректирующейся программной пары для указанных целочисленных (в том числе модулярных с операндами многократной точности) функций. Во второй колонке показано время выполнения самотестирующейся/ самокорректирующейся программной пары без учета времени вызова программы, реализующей функции, приведенные в первой колонке. В третьей колонке приведено общее время выполнения с учетом времени вызовов программы P. В это время не включается время выполнения программ реализации функций, зависящее от параметра безопасности k, который обычно составляет O(log(1/k)).
Таблица 4.1.
