2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Время умножения двух n-разраядных чисел
Сообщение21.05.2016, 18:28 


04/07/15
149
Здравствуйте. Углубляю свои знания в дискретной математике. В книге Окулова случился затык. Никак не получается с ним справиться.
Вот что он пишет:
Пусть a и b - n-разрядные двоичные числа и n является степенью двойки. Тогда $a\cdot b = x_1 \cdot y_1\cdot 2^{n} + (x_1\cdot y_2+x_2\cdot y_1)\cdot 2^{\frac{n}{2}}+x_2\cdot y_2$. Введём следующие обозначения: $t=(x_1+x_2)\cdot(y_1+y_2);\quad v=x_1\cdot y_2;\quad w=x_2\cdot y_2.$ Примет вид : $a\cdot b = v\cdot 2^{n} + (t-v-w)\cdot 2^{\frac{n}{2}}+w$. Следовательно, время умножения двух n-разрядных чисел можно выразить так:
$$\begin{cases}
k,&\text{при $n=1$;}\\
3T(n/2)+kn,&\text{при $n>1$,}\\
\end{cases}$$
где k - постоянное время выполнения операции сложения и сдвигов. Решение уравнения есть $T(n)=3kn^{\log{3}}-2kn$
Вопросы:
Как он получил оценку времени умножения и решение уравнения?

 Профиль  
                  
 
 Re: Время умножения двух n-разраядных чисел
Сообщение21.05.2016, 20:26 
Заслуженный участник


10/01/16
2315
Orkimed в сообщении #1124923 писал(а):
Как он получил оценку времени умножения

Не очень понятно, что есть $k$...
Было: три умножения маленьких чисе (нашли $t,v,w$). А также : 2 сдвига и несколько сложений-вычитаний (обозначим их кол-во через $K$. Пусть $T(n)$ - время вычисления призведения ( для суммы-сдвига-вычитания оно равно $c\cdot n$ ). Тогда : $T(n) = 3\cdot T(\frac{n}{2}) + K\cdot cn$
Это (почти) и есть Ваше уравнение.
Решается полученное уравнение - как дифуры: только сначала надо сделать подстановку $n=2^x$ и замену $T(2^x) =y(x)$. Получится линейное неоднородное уравнение на функцию $y(x)$:

$y(x) = 3\cdot y(x-1) + k\cdot 2^x$

Решаете однородное уравнение, а затем - методом вариации постоянной - неоднородное....

 Профиль  
                  
 
 Re: Время умножения двух n-разраядных чисел
Сообщение22.05.2016, 18:57 


04/07/15
149
DeBill
Большое спасибо за объяснение. Теперь всё стало понятно.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group