Дано описание программы (псевдокод):
ВХОД: ($%x,y$% - натуральные числа)
Пусть $%2^{d_x}$% - максимальная степень 2, делящая $%x$%, $%d_y$% - аналогично.
Положим $%a = x2^{-d_x}, b = y2^{-d_y}$%
Поменять местами $%b$% и $%a$%, если $%b < a$%
ПОКА $%b>1$% ВЫПОЛНИТЬ
Положим $%r$% равным тому из чисел $%a+b$%, $%a-b$%, которое делится на $%4$%.
Положим $%a = max(b, r2^{-d_r})$%, $%b = min(b, r2^{-d_r})$%, где $%2^{d_r}$% - максимальная степень 2, делящая $%r$%
КОНЕЦ ЦИКЛА ПОКА
ВЫХОД$%(a2^{min(d_x, d_y)})$%.
1) Программа, если в ней исправить неточности, вычисляет известную функцию. Что эта за функция?
2) Оценить трудоемкость (скорректированной) процедуры (число производимых битовых операций), если $%x,y$% - битовые числа.

задан 23 Фев '16 15:51

1

вычисляет оно НОД, только немного извратным аппаратно-заточенным способом (т.е. здесь аппаратные операции не прописаны, а если их прописать, алгоритм будет быстрее, чем стандартный Евклид)

асимптотическая оценка, есс-но, та же

(24 Фев '16 13:23) Trumba

@Trumba, спасибо!

(25 Фев '16 1:37) Uchenitsa
10|600 символов нужно символов осталось

Вопрос был закрыт. Причина - "Вопрос отвечен и ответ принят". Закрывший - Uchenitsa 25 Фев '16 1:37

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×505
×131
×86
×35

задан
23 Фев '16 15:51

показан
170 раз

обновлен
25 Фев '16 1:37

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru