Comments 12
Терминология у вас, похоже, своя, и запутывающая, и без предварительного знания предмета читать нереально тяжело.
Использование слова "разряд", мало того, что слабо пояснено, так и даёт постоянную путаницу с использованием "разряд" для одного бита, которая здесь типовая. В английском давно известно использование слова limb для данного назначения, см. например, библиотеку GMP.
Далее, откуда "половинчатое деление"? Я понимаю проблему подбора слова, но это как-то очень непонятно: вы в обоих случаях делите, например, 128-битное на 128-битное, но "половинчатое" намекает на половину результата.
Далее, я бы вспомнил архитектуры, где аппаратное деление "косое" (жаргон), как x86 и SystemZ, где может быть 128-битное делимое с 64-битными делителем, частным и остатком, и такие, где оно только равнодлинное (ARM, RISC-V и так далее), например, все по 64. Специфика второго варианта даёт, что фактически там для исходной задачи используется серия делений в "косом" стиле как 64/32. Так как новые архитектуры предпочитают этот вариант (и имеет смысл упомянуть, почему так), то алгоритм усложняется (как вы описывали про "четырёхразрядное" деление в ваших терминах). По современному, имело бы смысл привести готовый код на чём-то легкодоступном (типа Python).
Кнутовский TAoCP, конечно, фундаментален, но основа его книг не менялась как минимум с 1970-х и вряд ли уже поменяется, он давно потерял актуальность и имеет больше историческое значение. Если вы не используете для источников, кроме него, ничего, это в сильный минус.
Да, с терминами проблема, в том числе и потому что это не мой профиль по образованию. Больше любительское.
Разряд - имеется ввиду digit. N-разрядное число - думаю адекватный термин. А с "половинчатостью" полностью согласен. Мне тоже не нравятся эти термины, но лучшего - не знаю.
Код на python - добавлю.
Кнут потерял актуальность? Это тоже самое, что таблица умножения потеряла актуальность.
Если бы я занимался всем этим профессионально (архитектуры, низкоуровневые алгоритмы и пр.), то конечно статья была бы полнее и с большим количеством источников.
Кнут потерял актуальность? Это тоже самое, что таблица умножения потеряла актуальность.
Таблица умножения, конечно, потерять актуальность не может. А вот правила, как делать умножение, например, в записи римскими цифрами, с тонкими приёмами, как из IX * IX получить LXXXI, например, имея промежуточную форму XXCI - уже мало кому нужны, кроме особых историков.
Сравнение может показаться жестковатым, но по отношению к TAoCP это так и есть для, наверно, половины классического состава I-III томов. Например, сортировки - почти все 100500 вариантов "внешних" ушли в историю. Надежды на хитрые методы, как Шелла, не оправдались. Во 2-м томе: метод Шёнхаге-Штрассена, который сейчас основной для самых длинных чисел, не разобран подробно даже во 2-м издании (конец 1990-х). Нет Бурникеля-Циглера. Нет представления Монтгомери. Генераторы ППСЧ: нет Xorshift семейства. Нет основ работы с плавающей точкой в современном виде (я даже не призываю вспоминать IEEE754, но то, на чём он основан, должно было войти в описания). Тут можно ещё пару страниц накатать, чего не вошло в TAoCP и не войдёт уже, но присутствует в современных аналогах, но и так уже заметно, я надеюсь.
Да, так. Но практики видимо предпочитают просто реализовывать идеи, и никому не рассказывать подробностей, кроме своих коллег. По своему хорошо (на то они и практики), но обучаться на их исходниках не каждый сможет.
Практики – возможно (не все), но при чём тут практики, когда практически каждая тема, описанная у Кнута, кем-то позже переописана с новыми данными, подходами, алгоритмами? Например, по алгоритмам в целом и структурам данных есть Кормен, Скиена, Дасгупта. В темах появились чёрно-красные деревья, LSM tree, skiplists. По плавающей точке есть талмуды вроде Handbook of… от Мюллера с компанией. Огромная новая тема – параллельное и конкурентное программирование, вплоть до хитрых задач типа “византийских генералов”. И это только то, что из памяти за пять минут берётся. То же самое, например, с Ахо-Ульманом и “Книгой дракона”: даже издание 2008 года у них не включило PEG, на котором сейчас очень много чего делается, зато сохраняет множество рассуждений, которые имели смысл в лучшем случае для 1970-х. Прогресс тут идёт, и, отдавая свою дань старому, надо не забывать, насколько всё меняется… (да, комментарий через полгода, ну так получается)
Кнутовский алгоритм деления реализован в CPython для встроенной арифметики типа int. По крайней мере основа оттуда. Единственное, там один разряд имеет 30 битов на 64-битной архитектуре. Это программная настройка по причинам разного рода оптимизаций.
В CPython для int на больших длинах значений используется алгоритм Бурникеля-Циглера. Это разработка середины 1990-х (я аж удивился, почему так поздно), и имеет логарифмическую сложность (точнее, O(M(N)*log(N)), где M(N) - сложность применённого умножения; для Шёнхаге-Штрассена это O(N*log(N)*log(log(N))).
Кнут не смог выйти в своё время за пределы квадратичной сложности, но применил ряд приёмов, которые легли в основу метода Бурникеля-Циглера - нормализация и деление по сокращённой длине. (Потому и удивительно, что потребовалось 30 лет на завершить кусочек логики.)
Понятно. Посмотрел упоминание алгоритма Бурникеля-Циглера в Вики, D2n/1n, D3n/2n - намекает на деление двухразрядного числа на одноразрядное, и на деление 3-разрядного на 2-х )). Почему-то нет подробного описания, а отрывочное упоминание - на немецком и русском. Но это всё для специалистов, порог входа большой.
D2n/1n, D3n/2n - намекает на деление двухразрядного числа на одноразрядное, и на деление 3-разрядного на 2-х )).
Это не то n. Первое означает, например, деление числа в 20000 лимбов на число в 10000 лимбов (или бит, или байт, или слов, любой однородной единицы). Второе - аналогично, например, 90000 на 60000. Алгоритм применяется рекурсивно, пока длина участников не упадёт до уровня, когда выгоднее применять более простой метод.
https://github.com/python/cpython/blob/3.14/Lib/_pylong.py#L422
Почему-то нет подробного описания
В русской вики ссылка на оригинальную статью на английском, там, мне кажется, вы поймёте.
Объяснение алгоритма деления двухразрядных чисел по материалам Дональда Кнута