В настоящей работе доказывается следующий результат. Число шагов в алгоритме Евклида для двух натуральных аргументов, меньший из которых имеет v цифровых разрядов в десятичной системе счисления, не превосходит целой части от дроби (v+lg(5√/Φ))/lgΦ, где Φ=(1+5√)/2, причем эта оценка достигается при каждом натуральном v. Доказывается также, что для двух других известных верхних оценок длины алгоритма Евклида справедливы частичная или асимптотическая достижимости.
Идентификаторы и классификаторы
Если у вас возникли вопросы или появились предложения по содержанию статьи, пожалуйста, направляйте их в рамках данной темы.