циклическая свертка над полем 2^m - Программирование

Naked · 14.03.2006, 13:37

Народ, может у кого есть, или есть ссылки, статьи, короче любая документация по ВООБЩЕ циклическим сверткам + по циклической свертке Винограда и гнездовым алгоритмом (последнее очень нужно).
Всем спасибо

Spacoom · 14.03.2006, 22:53

http://home.uic.tula.ru/~ia241153/KOI/staty.html - можно связаться с автором у него много грамотных статей.

http://dcn.infos.ru/~petert/DiscrAlg.pdf (база)

Вот тут есть хорошая книжка : http://www.bibel.hut1.ru/ ("Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов")

Вот тут : http://vadkudr.boom.ru/Collection/va...ction_eng.html (Гагарин Ю.И. Псевдогнездовые алгоритмы двумерных преобразований цифровых сигналов. Радиоэлектроника, 1991, N3)

Удачи.

Naked · 02.04.2006, 10:29

Цитата:

Spacoom:
Вот тут есть хорошая книжка : http://www.bibel.hut1.ru/ ("Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов")

хех, книжка может и хорошая, там есть все, только вот, чтобы разобраться в этом всем нужно приложить немалые усилия

Я по ней БПФ писал, так дня три только вникал в то, что написано...

а это

Цитата:

Spacoom:
http://dcn.infos.ru/~petert/DiscrAlg.pdf (база)

писал препод, который и задал мне курсовик делать

вот так вот

но, вроде разбираюсь потихоньку...спасибо, если еще что-нибудь найдете - пишите, особенно по Агравалу Кули (вроде), что-то я по Блейхуту не очень понял этот алгоритм...

Kvarx · 17.04.2006, 17:35

Народ, мне нужны алгоритмы линейной короткой свертки по Винограду. В Блейхуте написано для циклической до 13-точечной свертки, а мне нужна линейная.

Препод сказал, что можно на Maple процедурку написать, которая будет матрицы генерить. Вот только не представляю, как это сделать.

Spacoom · 17.04.2006, 19:07

http://is.ifmo.ru/vis/vinograd/doc.pdf

На сайте "САНКТ-ПЕТЕРБУРГСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ" : Построение Визуализатора алгорима Винограда вычисления коротких свёрток.

Включая описание алгоритма. Только зря это, учиться нужно

Naked · 17.04.2006, 19:15

Цитата:

Spacoom:
Только зря это, учиться нужно

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

Цитата:

Spacoom:
Включая описание алгоритма.

еще бы такое по Агравалу Кули, было бы просто супер, именно хорошее описание алгоритма...

Kvarx · 17.04.2006, 21:09

Цитата:

Сообщение от Spacoom

Включая описание алгоритма. Только зря это, учиться нужно

Мне нужна схема алгоритма, а не описание алгоритма и не код, в этом то и проблема, причем для GF(2^m)
Схема записывается так: c=B[(Cg)*(Ad)],
где Cg и Ad - векторы одинаковой длины, (Cg)*(Ad) - их покомпонентное произведение - взято из Блейхута.

Kvarx · 09.05.2006, 22:25

Вот для Агарвала-Кули алгоритма понадобился быстрый алгоритм разложения числа на два взаимнопростых сомножителя.

Можно, конечно, перебирать два множителя, а потом алгоритмом Евклида проверять простые или нет. Только видимо перебирать надо, как по-хитрому

Kvarx · 24.05.2006, 12:25

Посоветуйте, плиз!

Мне нужен простый и эффективный способ хранения чисел от 1 до 1000, и их простых делителей(это все будет забито ручками или программно, но главное, что один раз). Чтобы программа получая на входе число N, обращаясь к этой структуре получала бы его простые делители.

И еще: кто-нибудь знает, как можно ценить максимальное количество простых делителей у числа?

14.03.2006, 13:37	# 1
Naked ::VIP:: Регистрация: 15.05.2005 Адрес: Питер Сообщения: 1 194	циклическая свертка над полем 2^m Народ, может у кого есть, или есть ссылки, статьи, короче любая документация по ВООБЩЕ циклическим сверткам + по циклической свертке Винограда и гнездовым алгоритмом (последнее очень нужно). Всем спасибо __________________ Чтобы воля стала действующим началом, тело должно быть совершенным.

17.04.2006, 19:07	# 5
Spacoom (Злопидор) Banned Регистрация: 02.02.2006 Сообщения: 347	http://is.ifmo.ru/vis/vinograd/doc.pdf На сайте "САНКТ-ПЕТЕРБУРГСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ" : Построение Визуализатора алгорима Винограда вычисления коротких свёрток. Включая описание алгоритма. Только зря это, учиться нужно Последний раз редактировалось Spacoom; 17.04.2006 в 21:54.

14.03.2006, 22:53	# 2
Spacoom (Злопидор) Banned Регистрация: 02.02.2006 Сообщения: 347	http://home.uic.tula.ru/~ia241153/KOI/staty.html - можно связаться с автором у него много грамотных статей. http://dcn.infos.ru/~petert/DiscrAlg.pdf (база) Вот тут есть хорошая книжка : http://www.bibel.hut1.ru/ ("Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов") Вот тут : http://vadkudr.boom.ru/Collection/va...ction_eng.html (Гагарин Ю.И. Псевдогнездовые алгоритмы двумерных преобразований цифровых сигналов. Радиоэлектроника, 1991, N3) Удачи.

17.04.2006, 17:35	# 4
Kvarx Member Регистрация: 26.09.2005 Адрес: Питер Сообщения: 336	Народ, мне нужны алгоритмы линейной короткой свертки по Винограду. В Блейхуте написано для циклической до 13-точечной свертки, а мне нужна линейная. Препод сказал, что можно на Maple процедурку написать, которая будет матрицы генерить. Вот только не представляю, как это сделать.

09.05.2006, 22:25	# 8
Kvarx Member Регистрация: 26.09.2005 Адрес: Питер Сообщения: 336	Вот для Агарвала-Кули алгоритма понадобился быстрый алгоритм разложения числа на два взаимнопростых сомножителя. Можно, конечно, перебирать два множителя, а потом алгоритмом Евклида проверять простые или нет. Только видимо перебирать надо, как по-хитрому

24.05.2006, 12:25	# 9
Kvarx Member Регистрация: 26.09.2005 Адрес: Питер Сообщения: 336	Посоветуйте, плиз! Мне нужен простый и эффективный способ хранения чисел от 1 до 1000, и их простых делителей(это все будет забито ручками или программно, но главное, что один раз). Чтобы программа получая на входе число N, обращаясь к этой структуре получала бы его простые делители. И еще: кто-нибудь знает, как можно ценить максимальное количество простых делителей у числа?