Читал (давно), что БУЧ можно реализовать с помощью БПФ.
Вот, например, есть число а=456785, то что я должен подать на вход БПФ
(??? комплексный массив = ((4,0), (5,0), (6,0), (7,0), (8,0), (5,0) ???)

Здравствуйте, Ozone, Вы писали:

O>Читал (давно), что БУЧ можно реализовать с помощью БПФ.
O>Вот, например, есть число а=456785, то что я должен подать на вход БПФ
O>(??? комплексный массив = ((4,0), (5,0), (6,0), (7,0), (8,0), (5,0) ???)

Неужели никто не знает...

Здравствуйте, Ozone, Вы писали:

O>Здравствуйте, Ozone, Вы писали:

O>>Читал (давно), что БУЧ можно реализовать с помощью БПФ.
O>>Вот, например, есть число а=456785, то что я должен подать на вход БПФ
O>>(??? комплексный массив = ((4,0), (5,0), (6,0), (7,0), (8,0), (5,0) ???)

O>Неужели никто не знает...

Ищи описание алгоритма Шёнхаге-Штрассена для умножения целых чисел.
Там используется БПФ.
Его сложность O( n*log(n)*log( log(n) ));

Здравствуйте, korzhik, Вы писали:

K>Ищи описание алгоритма Шёнхаге-Штрассена для умножения целых чисел.
K>Там используется БПФ.
K>Его сложность O( n*log(n)*log( log(n) ));

Нигде найти не могу... (только ссылки на книги)

Алгоритм подобно рассмотрен во 2-м томе "Искусства программирования для
ЭВМ" Кнута. Если нет возможности найти книгу, см в библиотеке Мошкова
(http://lib.ru/CTOTOR/KNUT/). Там выложен русский перевод в формате TeX/

Ozone wrote:
>
> Нигде найти не могу... (только ссылки на книги)

Здравствуйте, thebeard, Вы писали:

T>Алгоритм подобно рассмотрен во 2-м томе "Искусства программирования для
T>ЭВМ" Кнута. Если нет возможности найти книгу, см в библиотеке Мошкова
T>(http://lib.ru/CTOTOR/KNUT/). Там выложен русский перевод в формате TeX/

Спасибо, но что-то не пойму как правильно читать этот формат (чем?)

Там же статья есть. "Как пропустить Кнута через Tex". Почитайте.

Ozone wrote:
>
> Спасибо, но что-то не пойму как правильно читать этот формат (чем?)

Вообще-то Гугль по запросу schonhage-strassen algorithm выдаёт кучу
ссылок. Не думаю, что всё это книги.

http://www.google.com/search?hl=en&ie=UTF-8&oe=UTF-8&q=schonhage-strassen+algorithm

Здравствуйте, thebeard, Вы писали:

T>Алгоритм подобно рассмотрен во 2-м томе "Искусства программирования для
T>ЭВМ" Кнута. Если нет возможности найти книгу, см в библиотеке Мошкова
T>(http://lib.ru/CTOTOR/KNUT/). Там выложен русский перевод в формате TeX/
К сожелению, как я понял, там выложено пока до 280 — ой страницы, а описание алгоритма начинается на 328.
Поэтому мучаться не стоит, а лучше всё таки купить.
Ещё описание этого алгоритма есть в А.АХО, ДЖ.Хопкрофт, Дж.Ульман "Построение и анализ вычислительных алгоритмов"
на 304 странице.

Здравствуйте, Ozone, Вы писали:

O>Читал (давно), что БУЧ можно реализовать с помощью БПФ.
O>Вот, например, есть число а=456785, то что я должен подать на вход БПФ
O>(??? комплексный массив = ((4,0), (5,0), (6,0), (7,0), (8,0), (5,0) ???)

Да, так и есть.

c = a*b;
a = 12345;
b = 67890;

A = { {1,0}, {2,0}, {3,0}, {4,0}, {5,0} }
B = { {6,0}, {7,0}, {8,0}, {9,0}, {0,0} }

c = IFFT( FFT(A) * FFT(B) ), т.е. {1,0}*{6,0}, {2,0}*{7,0} и т.д.

c = IFFT(C);

в рез-те IFFT(C) получается что-то такое:

{0,0}, {16,0}, {35,0} — все коэф. нужно привести к 10 — И БУДЕТ ТЕБЕ ЩАСТЬЕ

Могу выслать исходники (только вечером — дома лежат).
У меня на этом целый калькулятор работает: здесь

Еще библиотека GMP на этом построена — там вылизано все, но под vc не компилируется.

Здравствуйте, Kalinsky V., Вы писали:

KV>c = a*b;
KV>a = 12345;
KV>b = 67890;

KV>A = { {1,0}, {2,0}, {3,0}, {4,0}, {5,0} }
KV>B = { {6,0}, {7,0}, {8,0}, {9,0}, {0,0} }

KV>c = IFFT( FFT(A) * FFT(B) ), т.е. {1,0}*{6,0}, {2,0}*{7,0} и т.д.

KV>c = IFFT(C);

KV>в рез-те IFFT(C) получается что-то такое:

KV>{0,0}, {16,0}, {35,0} — все коэф. нужно привести к 10 — И БУДЕТ ТЕБЕ ЩАСТЬЕ

KV>Могу выслать исходники (только вечером — дома лежат).
KV>У меня на этом целый калькулятор работает: здесь

KV>Еще библиотека GMP на этом построена — там вылизано все, но под vc не компилируется.

Уже сам сделал, но все равно спасибо за отклик.

Здравствуйте, thebeard, Вы писали:

T>Алгоритм подобно рассмотрен во 2-м томе "Искусства программирования для
T>ЭВМ" Кнута. Если нет возможности найти книгу, см в библиотеке Мошкова
T>(http://lib.ru/CTOTOR/KNUT/). Там выложен русский перевод в формате TeX/

T>Ozone wrote:
>>
>> Нигде найти не могу... (только ссылки на книги)

Кстати, можешь порекомендовать какой-нибудь просмотрщик TeX под Windows разумных размеров?

Не могу, к сожалению. Windows я пользуюсь на работе, где нет надобности
в TeX, а дома у меня Linux и проблем не возникает В библиотеке
Мошкова, рядом с Кнутом, лежали какие-то статейки на эту тему.

>
> Кстати, можешь порекомендовать какой-нибудь просмотрщик TeX под Windows
> разумных размеров?

Здравствуйте, thebeard, Вы писали:

T>Не могу, к сожалению. Windows я пользуюсь на работе, где нет надобности
T>в TeX, а дома у меня Linux и проблем не возникает

Везет тебе...

T>В библиотеке
T>Мошкова, рядом с Кнутом, лежали какие-то статейки на эту тему.

Там есть ссылки на просмотрщики, да и в инете по поиску нашел, но либо под DOS, размером более 10М, либо под Windows, размером 25М и более.

>> Кстати, можешь порекомендовать какой-нибудь просмотрщик TeX под Windows
>> разумных размеров?

>
> Там есть ссылки на просмотрщики, да и в инете по поиску нашел, но либо
> под DOS, размером более 10М, либо под Windows, размером 25М и более.
>

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

Здравствуйте, Kalinsky V., Вы писали:

KV>Могу выслать исходники (только вечером — дома лежат).

И мне и мне. dimchansky собака mail точка ru

KV>Еще библиотека GMP на этом построена — там вылизано все, но под vc не компилируется.

А где на неё глянуть?

Здравствуйте, Kalinsky V., Вы писали:

KV>в рез-те IFFT(C) получается что-то такое:
KV>{0,0}, {16,0}, {35,0} — все коэф. нужно привести к 10 — И БУДЕТ ТЕБЕ ЩАСТЬЕ

Не совсем понял. Как это привести к 10?
На данном примере не подскажете, что получается?

Здравствуйте, Kalinsky V., Вы писали:

KV>Здравствуйте, Ozone, Вы писали:

O>>Читал (давно), что БУЧ можно реализовать с помощью БПФ.
O>>Вот, например, есть число а=456785, то что я должен подать на вход БПФ
O>>(??? комплексный массив = ((4,0), (5,0), (6,0), (7,0), (8,0), (5,0) ???)

KV>Да, так и есть.

KV>c = a*b;
KV>a = 12345;
KV>b = 67890;

KV>A = { {1,0}, {2,0}, {3,0}, {4,0}, {5,0} }
KV>B = { {6,0}, {7,0}, {8,0}, {9,0}, {0,0} }

KV>c = IFFT( FFT(A) * FFT(B) ), т.е. {1,0}*{6,0}, {2,0}*{7,0} и т.д.

KV>c = IFFT(C);

KV>в рез-те IFFT(C) получается что-то такое:

KV>{0,0}, {16,0}, {35,0} — все коэф. нужно привести к 10 — И БУДЕТ ТЕБЕ ЩАСТЬЕ

KV>Могу выслать исходники (только вечером — дома лежат).

И мне.

KV>У меня на этом целый калькулятор работает: здесь

KV>Еще библиотека GMP на этом построена — там вылизано все, но под vc не компилируется.

Сделаем.

Кстати, я где-то встречал, что есть функции, аналогичные БПФ, но без комплексных чисел, позволяющие делать свертку гораздо быстрей. Никто такие не встречал?

Здравствуйте, Socrat, Вы писали:

S>Кстати, я где-то встречал, что есть функции, аналогичные БПФ, но без комплексных чисел, позволяющие делать свертку гораздо быстрей. Никто такие не встречал?

Не о преобразовании Хартли идет речь?

Здравствуйте, MBo, Вы писали:

MBo>Здравствуйте, Socrat, Вы писали:

S>>Кстати, я где-то встречал, что есть функции, аналогичные БПФ, но без комплексных чисел, позволяющие делать свертку гораздо быстрей. Никто такие не встречал?

MBo>Не о преобразовании Хартли идет речь?

Не помню, может и о нем.