Я думал о твоей проблеме.У меня нет закодированного решения, но вот подход:
Прежде всего, давайте предположим, что без потери общности, у вас есть набор из 2 n битов.(Если у вас меньше 2 n битов, добавьте битовый массив начальными нулями, пока вы не сделаете это. Очевидно, что это никогда не удваивает размер массива.) В вашем случае вы говорите, что имеетемиллион уинт, так что это 2 25 бит.
Давайте также предположим, что каждая коллекция из 2 k + 1 битов может быть равномерно разделена на две коллекции битов,левый и правый наборы, каждый с 2 k битами.
Таким образом, каждый набор битов или подколлекция имеет «размер», который является точной степенью двойки.Наименьшая возможная коллекция содержит один бит и не может быть далее подразделена.
Во-вторых, давайте предположим, что у вас аналогично имеется неизменное представление числа в десятичной форме, и что опять же, без потери общности, есть 2 d десятичные цифры в строке.Если их меньше 2 d , снова вставьте начальные нули.Опять же, каждая десятичная коллекция размером больше единицы может быть разделена на две коллекции, каждая из которых имеет половину размера.
Теперь мы набросаем рекурсивный алгоритм:
DigitCollection Convert(BitCollection bits)
{
if (bits.Size == 1)
return bits[0] ? DigitCollection.SingleOne : DigitCollection.SingleZero;
DigitCollection left = Convert(bits.Left);
DigitCollection right = Convert(bits.Right);
DigitCollection power = MakePowerOfTwo(bits.Right.Size);
return Add(Multiply(left, power), right);
}
Теперь нам нужны методы Add,Умножьте и MakePowerOfTwo.Как мы увидим через некоторое время, нам также понадобятся Subtract и два оператора Shift для быстрого умножения на степени десяти.
Сложение и вычитание легко.Ясно, что если более длинная коллекция содержит n цифр, то методы сложения и вычитания могут быть реализованы, чтобы занять O (n) времени.
Операторы FullShift и HalfShift делают новые коллекции цифр из старых, чтобы ускорить умножение на степени десяти.Если коллекция цифр размером 2 d + 1 состоит из вложенных коллекций (X1, X2), каждая из которых имеет размер 2 d , тогда коллекция "сдвинутых наполовину" содержит 2 d + 2 элементов и состоит из ((2 d начальных нулей, X1), (X2, 2 d конечных нулей)).Полная смена состоит из ((X1, X2), (2 d + 1 конечных нулей)).
Их, очевидно, очень дешево построить.
Умножение - это то, где мы сталкиваемся с большими проблемами .Предположим без ограничения общности, что мы умножаем вместе две DigitCollections, каждая из которых содержит ровно 2 d цифр.Мы можем использовать алгоритм Карацубы:
DigitCollection Multiply(DigitCollection x, DigitCollection y)
{
// Assume x and y are the same digit size.
if (x and y are both single digits)
return the trivial solution;
// Assume that z2, z1 and z0 are all the same digit size as x and y.
DigitCollection z2 = Multiply(x.Left, y.Left);
DigitCollection z0 = Multiply(x.Right, y.Right);
DigitCollection z1 = Subtract(
Multiply(Add(x.Left, x.Right), Add(y.Left, y.Right)),
Add(z2, z0));
return Add(Add(FullShift(z2), HalfShift(z1)), z0);
}
Каков порядок этого алгоритма?Предположим, что есть n = 2 d цифр.Что такое O (Multiply (n))?Мы повторяем три раза, каждый с проблемой вдвое меньше цифр.Все остальные операции сложения, вычитания и сдвига не более O (n).Таким образом, у нас есть рецидив:
T(n) = 3 T(n/2) + O(n)
, который имеет простое решение с помощью основной теоремы: этот алгоритм O (n 1 / lg 3 ), что около O (n 1,58 ).
А как насчет MakePowerOfTwo?Это легко, учитывая то, что у нас уже есть.Мы используем идентификацию:
2 2n + 1 = 2 n x 2 n + 2 n x 2 n
и напишите алгоритм:
DigitCollection MakePowerOfTwo(int p)
{
if (p == 0) return DigitCollection.SingleOne;
DigitCollection power = MakePowerOfTwo(p / 2);
power = Multiply(power, power);
if (p % 2 != 0)
power = Add(power, power);
return power;
}
В нем преобладают вычисления умножения, равно как и O (n *)1085 * 1.58 ).
И теперь мы можем видеть, что при исходном вызове Convert также преобладает умножение.
Так что с этим алгоритмом, если у вас есть 2 d двоичные цифры для преобразования, вы можете ожидать, что для этого потребуется примерно O (2 1,58 d ) шагов.В вашем случае у вас есть 2 25 бит для преобразования, так что для этого потребуется около 777 миллиардов вычислений.
Ключевым фактом здесь является то, что в этом алгоритме доминирует стоимость умножения . Если вы можете уменьшить стоимость умножения до менее чем O (n 1.58 ), то вы получите огромных выигрышей. На вашем месте я бы изучал улучшения алгоритмов десятичного умножения над Карацубой.