1 Тема от brainail

  • brainail
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-06-22
  • Сообщений: 165

Тема: преобразование Фурье для многочленов

Я написал длинное умножение за n log(n) самым быстрым способом используя complex
Я не уверен что оно будет давать точный результат , это надо уточнить у автора, какая гарантия правильности ответа smile))
И второе,я пишу на Microsoft Visual C++ 2009, и на моей машине работает около 9 секунд,на двух числах длиной 5*10^5
То есть долговато,может это Си++ такое,я думаю если я напишу её на паскале,а я это сделаю скоро,то она будет работать < 5 секунд я думаю big_smile Может я в чём нибудь некорректен,и плохо написал что то,но у меня получается так.

2 Ответ от e-maxx

  • e-maxx
  • admin
  • Неактивен
  • Откуда: Саратов
  • Зарегистрирован: 2009-06-10
  • Сообщений: 360

Re: преобразование Фурье для многочленов

Насчёт точности результатов это хороший вопрос smile Кажется, у Кнута есть глава, посвящённая этому, но я не осилил smile Ну делай в double, и, я думаю, можно верить, что погрешностей не будет.

По поводу скорости: от векторов пробовал отказаться?

Сайтe-maxx

3 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: преобразование Фурье для многочленов

brainail пишет:

Я написал длинное умножение за n log(n) самым быстрым способом используя complex
Я не уверен что оно будет давать точный результат , это надо уточнить у автора, какая гарантия правильности ответа smile))
И второе,я пишу на Microsoft Visual C++ 2009, и на моей машине работает около 9 секунд,на двух числах длиной 5*10^5
То есть долговато,может это Си++ такое,я думаю если я напишу её на паскале,а я это сделаю скоро,то она будет работать < 5 секунд я думаю big_smile Может я в чём нибудь некорректен,и плохо написал что то,но у меня получается так.

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

4 Ответ от 2rf

  • 2rf
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-08-14
  • Сообщений: 42

Re: преобразование Фурье для многочленов

Хм, я слышал, что можно использовать не 3-разрядную, а где-то 8-разрядную арифметику + 64-битные целые числа; они конечно работают медленнее, чем 32-битные, но при этом и длина числа сокращается почти в 3 раза, т.е. в результате может получиться побыстрее.

5 Ответ от brainail

  • brainail
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-06-22
  • Сообщений: 165

Re: преобразование Фурье для многочленов

разве тут прокатит разбиение на разряды ??? я попробывал, ответ стало неверный выдавать, наверно коряво написал, да и от векторов похоуд нуна отказаться smile

6 Ответ от KADR Отредактировано KADR (2009-09-08 16:42:39)

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: преобразование Фурье для многочленов

2rf пишет:

Хм, я слышал, что можно использовать не 3-разрядную, а где-то 8-разрядную арифметику + 64-битные целые числа; они конечно работают медленнее, чем 32-битные, но при этом и длина числа сокращается почти в 3 раза, т.е. в результате может получиться побыстрее.

С Фурье не получится 8 разрядную использовать, т.к. в промежуточных вычислениях будет переполнение. Там даже 4 разрядную вроде уже не выйдет. С 3 разрядной у меня работало правильно и быстро.

brainail пишет:

разве тут прокатит разбиение на разряды ??? я попробывал, ответ стало неверный выдавать, наверно коряво написал, да и от векторов похоуд нуна отказаться smile

Ну это то же самое, что ты возьмешь число не в системе счисления по основанию 10, а 100 или 1000. Суть от этого не поменяется, т.к. число все равно будет полиномом и к нему можно будет применить БПФ, просто у тебя цифр меньше выйдет.

7 Ответ от brainail

  • brainail
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-06-22
  • Сообщений: 165

Re: преобразование Фурье для многочленов

Нет ну я знаю что и как работает многоразрядная ) но просто коряво написалось . Понятно.;)