алгоритм шёнхаге-штрассена

[Nerazumovskiy]

Я сразу выложу ссылки на материалы которые я нашол :
http://www.emerecu.ukma.kiev.ua/books/Aho&/glava07/par7.5.pdf
http://www.csin.ru/courses/effektivnye-algoritmy - тут он тоже "описан" но я буду полагаться на первый источник
У меня возникли коекакие проблемы с реализацией, в основном из за непонимания, прошу помоч.

Вот к примеру, в начале алгоритма нам дано $ n = 2^k$, и мы вычисляем для себя $b = 2^{\frac{k}{2}}$ и
$l = \frac{n}{b}$, и говорим что наши числа можна представить в виде $\sum\limits_{i=0}^{b-1}u_i2^{li}$,
откуда,я так полагаю ,следует что $lb = k$, но ведь это не так?

-- Вт ноя 10, 2009 19:23:07 --

ах да, если укогото есть более понятное описание то я буду очень рад.

[Maslov]

С первой ссылкой проблема какая-то. На какую книгу Вы ссылаетесь?

-- Вт ноя 10, 2009 20:37:11 --

Понял на какую - на эту:
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.

[Nerazumovskiy]

Maslov в сообщении #260617 писал(а):

С первой ссылкой проблема какая-то...

Просто невсякий браузер хочет сходу открывать .pdf файлы, проблема в Хроме решаеться обновлением страницы.

[Maslov]

Nerazumovskiy в сообщении #260611 писал(а):

Вот к примеру, в начале алгоритма нам дано $ n = 2^k$, и мы вычисляем для себя $b = 2^{\frac{k}{2}}$ и
$l = \frac{n}{b}$, и говорим что наши числа можна представить в виде $\sum\limits_{i=0}^{b-1}u_i2^{li}$,
откуда,я так полагаю ,следует что $lb = k$

С чего бы это?
Вы попробуйте на каком-нибудь примере расписать.
Например, $ n = 64 = 2 ^ 6, k = 6, b = 2^{k/2} = 8, l = n/b = 8$
Т.е., исходные числа бьются на 8 блоков по 8 битов: $u=\sum\limits_{i=0}^{7}u_i2^{8i}$

[Nerazumovskiy]

смотрите я вот беру число $ n=3 000 000 000$, $k=32 ,b = 2^{16}, l = \frac{3 000 000 000}{65 536} =45 776$ , возвожу $2^l $, и получаю страницу циферок.

[Xaositect]

Так.
В алгоритме Ш-Ш перемножаются 2 числа, причем длина произведения не превосходит $N=2^k$.
Эти числа представляются в $2^L$-ичной системе $a = \sum\limits_{i=0}^{M-1} a_i 2^{Li}$, где $L = 2^{\lfloor \frac{k}{2}\rfloor}$, $M = 2^{\lceil \frac{k}{2}\rceil}$, т.е. $N = LM$. Каждое $a_i$ - это $L$-битное число.
Что из этого у Вас $b$, что $l$ - не знаю.

[Maslov]

Nerazumovskiy в сообщении #260630 писал(а):

смотрите я вот беру число $ n=3 000 000 000$

Попробуйте для начала взять что-нибудь поменьше, чем $2^{3000000000}$.

[Nerazumovskiy]

Xaositect в сообщении #260637 писал(а):

Так.
В алгоритме Ш-Ш перемножаются 2 числа, причем длина произведения не превосходит $N=2^k$.
Эти числа представляются в $2^L$-ичной системе $a = \sum\limits_{i=0}^{M-1} a_i 2^{Li}$, где $L = 2^{\lfloor \frac{k}{2}\rfloor}$, $M = 2^{\lceil \frac{k}{2}\rceil}$, т.е. $N = LM$. Каждое $a_i$ - это $L$-битное число.
Что из этого у Вас $b$, что $l$ - не знаю.

, я неспроста дал ссылку, чтобы говорить на одном языке.

$M =b$, $l = L$ , но ваш метод разве коректен, ведь $k$ может быть и нечетным.

[Xaositect]

Nerazumovskiy в сообщении #260644 писал(а):

ведь может быть и непарным.

Непарным - в смысле нечетным?
Там в одном месте округление вверх, а в другом вниз, так что все хорошо.

[Nerazumovskiy]

Возём число $10000$ и розложим, тогда $n = 8, k=3;b =2; l =4;$
$ тогда система исчисления будет 2^4 = 16$ и поидеи наше число записывается двумя цифрами числами в системе $16$, но ведь это несовсем так .

[Xaositect]

Для числа $10000$ нужно $n = 16$, потому что оно записывается 14ю двоичными разрядами.

[Nerazumovskiy]

И вправду, а дальше в алгоритме обязательно работать с двоичними числами? Пахнет весьма **моройно.

[Xaositect]

Nerazumovskiy в сообщении #260653 писал(а):

И вправду, а дальше в алгоритме обязательно работать с двоичними числами? Пахнет весьма **моройно.

Ну там, насколько я помню, существенно, что умножение на $2^i$ выполняется быстро по модулю $2^p+1$.
А вам зачем вообще Ш-Ш нужен?

[Nerazumovskiy]

Я плавно перехожу к вопросу вычисления $W[i]'$ в обозначениях из ссылки, там надо взять остаток от моего толькошто полученого массива по модулю $b$, и сформировать новый $u1$повставляв по $3logb$нулей.
Там логарифм берётся двоичный я так понял.
Так вот мне надо значимую часть массива $u1$ заполнять в двоичном формате, а потом это чудо множить карацубой?

-- Вт ноя 10, 2009 21:10:56 --

Xaositect в сообщении #260657 писал(а):

Nerazumovskiy в сообщении #260653 писал(а):

И вправду, а дальше в алгоритме обязательно работать с двоичними числами? Пахнет весьма **моройно.

Ну там, насколько я помню, существенно, что умножение на $2^i$ выполняется быстро по модулю $2^p+1$.
А вам зачем вообще Ш-Ш нужен?

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

[Xaositect]

Nerazumovskiy в сообщении #260659 писал(а):

Так вот мне надо значимую часть массива заполнять в двоичном формате, а потом это чудо множить карацубой?

Ну да.