Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум   
blank
Авторизация

       
blank
Поиск по указателям

blank
blank
blank
Красота
blank
Sorenson J. — An Analysis of Lehmer's Euclidian GCD algorithm
Sorenson J. — An Analysis of Lehmer's Euclidian GCD algorithm



Обсудите книгу на научном форуме



Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter


Название: An Analysis of Lehmer's Euclidian GCD algorithm

Автор: Sorenson J.

Аннотация:

Let u and v be positive integers. We show that a slightly modified version of D. H. Lehmer’s greatest common divisor algorithm will compute gcd(u, v) (with u > v) using at most 0{(log u log v)/k + k log v + log u +k2} bit operations and 0(log и + k22k) space, where к is the number of bits in the multiprecision base of the algorithm. This is faster than Euclid’s algorithm by a factor that is roughly proportional to k.
Letting n be the number of bits in и and v, and setting к = [(log n)/4], we obtain a subquadratic running time of 0(n2/log n) in linear space.


Язык: en

Рубрика: Computer science/

Тип: Статья

Статус предметного указателя: Неизвестно

ed2k: ed2k stats

Количество страниц: 5

Добавлена в каталог: 18.10.2012

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2021
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте