Операции над битами при выполнении двоичного длинного деления
Это из главы теории чисел в CLRS.
Нас просят доказать, что двоичное "бумага и карандаш" длинное деление a/b с результатом q и напоминание r делает O((1+lgq)lgb) операции над битами.
То, как я вижу это, мы делаем 1 вычитание b за каждый бит в q, Итак, предполагая, что вычитание b делает lgb операции (по одному на каждый бит в b), тогда мы имеем в общей сложности O(lgblgq) операции, что не то, что запрашивается.
Если принять во внимание, что первая операция вычитания, которую вы выполняете, может привести к 0 битам (например, деление 100b на 11b), тогда, ОК, вы можете добавить 1 к lgq чтобы компенсировать это вычитание. Но... то же самое можно сказать и о самом вычитании - это может занять lgb операции или это может занять lg(b)+1 операции в зависимости от чисел (в примере 100b и 11b второе вычитание будет 100b-11b, для выполнения которого требуется 3 операции).
Так что если мы учитываем эти случаи, то количество операций должно быть O((1+lgb)(1+lgq)),
Итак, вопрос в том, как вы можете показать, что O((1+lgq)lgb) операции?
1 ответ
Когда вы вычитаете 100b-11bвы можете фактически игнорировать начальный бит в первом числе, потому что вы уже знаете, что соответствующий бит в результате будет равен 0. Если бы это был 1, вы бы сделали вычитание вместо сдвига на предыдущем шаге. Таким образом, вычитание всегда учитывает точно lg b биты.