какой способ деления уголком лучше?

[bigarcus]

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

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

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

[Otta]

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

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

[Sonic86]

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

[bigarcus]

Это какая-то программистская оценка сложности вычислений? Она напрямую с ЭВМ на людей переносится??

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

[Sonic86]

Начать знакомиться можно с Вики:
https://ru.wikipedia.org/wiki/%D0%91%D1 ... 0%B8%D0%B5

bigarcus в сообщении #959990 писал(а):

Она напрямую с ЭВМ на людей переносится??

естественно

(Оффтоп)

bigarcus в сообщении #959990 писал(а):

Ферье

не, не слышал

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

[bigarcus]

ознакомился, ок!)