2014 dxdy logo

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

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




 
 какой способ деления уголком лучше?
Сообщение11.01.2015, 01:10 
в школе было только деление уголком, все его знают
но англоязычный интернет выдает "long devision" и "basic devision", которые выглядят каким-то повёрнутым уголком
есть ли у них преимущества, и в чём различия?

-- Вс янв 11, 2015 01:15:34 --

вот например:
https://www.mathsisfun.com/numbers/long-division-animation.html

 
 
 
 Re: какой способ деления уголком лучше?
Сообщение11.01.2015, 01:42 
Basic division - это примеры типа $63:9= ?$ или с остатком $9:2=?$.
Long division - такое же деление уголком, как и в нашей школе. Только результат пишется наверху, а делитель слева.
Там представлен еще один способ Long Division - выписываются результаты умножения делителя на все числа от 0 до 9, а затем в ответ вписывается нужное.

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

 
 
 
 Re: какой способ деления уголком лучше?
Сообщение11.01.2015, 12:45 
Пусть $x,y$ имеют длину $n$.
Тогда обычное деление уголком работает за $O(n^2)$.
Ясно, что $\frac{x}{y}=x\cdot y^{-1}$. Вычисление $y^{-1}$ через ряд Маклорена делается за $O(n\ln n)$ операций (? выделяем порядок+1 в системе счисления, выносим, дальше используем ряд). Умножение же делается за $O(n\ln n)$ операций с помощью быстрого преобразования Фурье.
В итоге получаем, что деление через преобразование Фурье асимптотически оптимальнее.

 
 
 
 Re: какой способ деления уголком лучше?
Сообщение11.01.2015, 14:55 
Это какая-то программистская оценка сложности вычислений? Она напрямую с ЭВМ на людей переносится??

Можно пример через Ферье?

 
 
 
 Re: какой способ деления уголком лучше?
Сообщение11.01.2015, 18:02 
Начать знакомиться можно с Вики:
https://ru.wikipedia.org/wiki/%D0%91%D1 ... 0%B8%D0%B5

bigarcus в сообщении #959990 писал(а):
Она напрямую с ЭВМ на людей переносится??
естественно

(Оффтоп)

bigarcus в сообщении #959990 писал(а):
Ферье
не, не слышал


Кстати, насчет $y^{-1}$ мог наврать

 
 
 
 Re: какой способ деления уголком лучше?
Сообщение14.01.2015, 01:50 
ознакомился, ок!)

 
 
 [ Сообщений: 6 ] 


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