2014 dxdy logo

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

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




На страницу Пред.  1, 2
 
 Re: Деление длинных
Сообщение31.01.2011, 20:47 
Zealint в сообщении #407321 писал(а):
boomeer в сообщении #407206 писал(а):
Эм, что не так?

Да все "не так". Это не будет работать для тех ограничений, которые вы назвали вначале. Сами-то проверьте.
Я так понимаю, что это только схема решения. Сами вычисления выполняются с нужной точностью как в начале темы.

 
 
 
 Re: Деление длинных
Сообщение31.01.2011, 20:57 
Тогда надо было вместо int в этой строке
boomeer в сообщении #407195 писал(а):
Код:
int res = 1;
что-нибудь другое написать! :?

 
 
 
 Re: Деление длинных
Сообщение31.01.2011, 21:00 
Аватара пользователя
Вклинюсь в тему. Как известно умножать большие числа можно с использование БПФ. А делить числа с использование БПФ можно? И почему обычно делят в столбик?

 
 
 
 Re: Деление длинных
Сообщение31.01.2011, 21:04 
Pavia в сообщении #407338 писал(а):
Вклинюсь в тему. Как известно умножать большие числа можно с использование БПФ. А делить числа с использование БПФ можно?
Нельзя. Разве что используя умножение с БПФ.
Цитата:
И почему обычно делят в столбик?
В столбик делят только маленькие числа. Для больших есть специальные методы, например, методом Ньютона инвертировать делитель (при этом используется только умножение и сложение), а потом домножить на делимое.

 
 
 
 Re: Деление длинных
Сообщение31.01.2011, 21:29 
Аватара пользователя
venco
Спасибо. Но я бы хотел развернутый ответ. Почему нельзя?

 
 
 
 Re: Деление длинных
Сообщение31.01.2011, 21:40 
Pavia в сообщении #407357 писал(а):
venco
Спасибо. Но я бы хотел развернутый ответ. Почему нельзя?
Не придумали как.

 
 
 
 Re: Деление длинных
Сообщение31.01.2011, 21:57 
Аватара пользователя
venco
Это не ответ. Берем a/b=c
a=c*b перейдем к полиномам
a=c(*)b (*) - операция светки; применим БПФ
FFT(a)=FFT(c)*FFT(b) - тут *- по компонентное умножение. Я так понимаю нам ничего кроме точности не мешает взять обратную операцию .
FFT(a)/FFT(b)=FFT(c) / - по компонентное деление.
IFFT(FFT(a)/FFT(b))=c

 
 
 
 Re: Деление длинных
Сообщение31.01.2011, 22:31 
Pavia в сообщении #407380 писал(а):
venco
Это не ответ. Берем a/b=c
a=c*b перейдем к полиномам
a=c(*)b (*) - операция светки; применим БПФ
FFT(a)=FFT(c)*FFT(b) - тут *- по компонентное умножение. Я так понимаю нам ничего кроме точности не мешает взять обратную операцию .
FFT(a)/FFT(b)=FFT(c) / - по компонентное деление.
IFFT(FFT(a)/FFT(b))=c
Мешает потеря информации о переносе из разряда в разряд.

 
 
 
 Re: Деление длинных
Сообщение01.02.2011, 07:38 
Цитата:
venco
Это не ответ. Берем a/b=c

Если что-то непонятно, нужно взять пример и посмотреть что получается.

 
 
 
 Re: Деление длинных
Сообщение01.02.2011, 15:27 
Реализовал по такой схеме
Это сам план, добавил сюда длинку.

 
 
 [ Сообщений: 25 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group