Доказать, что число шагов в алгоритме евклида

natalya1979

Помогите решить задачи, а то что то запутался.
Первая элементарная, но просто забыл.
1. Алгоритм Евклида
2^k<=a<2^(k+1 b<a. Доказать, что число шагов в алгоритме евклида <= 2k. Можно просто подсказать, а то я просто забыл.
2. Пусть M(n) - битовая сложность возведения в квадрат n-значного числа. Доказать, что M(n)<<n^(log3)
Зарание спасибо.

shpanenoc

действительно очевидно.
Лемма. На каждом шаге а.Е. бОльшее из чисел (в начале А) уменьшается как минимум вдвое.
Д-во.
Случай 1: B <= A/2, тогда A mod B <= B-1 < A/2
Случай 2: B > A/2, тогда A mod B = A - B < A - A/2 = A/2
Лемма доказана.
Дальше, думаю, понятно

natalya1979

спасибо
а второе сможеш обьяснить полностью?

lenmas

Посмотри в книжке Архипов, Садовничий, Чубариков "Лекции по математическому анализу" теорему Карацубы

natalya1979

помогите решить такую сумму, в частности нужна сумма по м, кажется ето будет геометрическая прогрессия, но что то невыходит желаемая оценка

lenmas

А какая оценка нужна

natalya1979

(p^2)*log(p)
впринципе это должно получится

_mrz

(p^2)*log(p)
впринципе это должно получится
если это типа оценка сверху модуля выражения, то не получится ибо неверно
поскольку о всяких параметрах (типа a) ничего не сказано, я считаю их произвольными, а значит возьмем например a=p^3 и получим все экспоненты равные 1, а всю сумму равную (p^3+3)/2, что выше указанной оценки.

lenmas

Или при a->0

Eugenie

там же первая сумма идет по а=1 до p^3, вот.

lenmas

Ясно, все думали, что во внешней сумме суммирование по Q (плохо прорисовано)

natalya1979

нет, нет там сумирование по а, просто так плохо получилось с рисунком.

lenmas

Все равно ничего не понимаю, у меня получается оценка O(ln p). Внутренняя сумма (по геометрической прогрессии) оценивается через 1/sin(\pi a/p^3) (одно слагаемое при a=p^3 не берем в счет, оно равно ограниченной величине Q и если оценить sin через его аргумент (разбив предварительно сумму на две половинки) по неравенству sin t>=2t/\pi, 0<t<\pi/2, то получается сумма с некоторым коэффициентом обратных величин к a от 1 до p^3/2, то-есть величина порядка 3 ln p+1 (ну и плюс Q). Или я где-то напартачил, или условие не такое

natalya1979

одним словом p^2 неможет появится ни откуда, я так понял. Или я тожу уже что то не понял?

lenmas

Да, если делить, как у тебя, на p^3. Наверняка, у задачи глубокий смысл, типа равномерной распределенности какой, или параметр Q как-то по-другому входит в сумму или оценку - например, если все слагаемые тупо позаменять на единички, то оценка вообще получится через Q. Тебе, скорее всего, нужна какая-то нетривиальная оценка суммы, ну типа Q в меньшей степени, или Q с таким маленьким-маленьким коэффициентом, зависящим от p, типа 1/ln p. Надо уточнять условие

natalya1979

пишу полный вариант задачи
Оставить комментарий
Имя или ник:
Комментарий: