Как эффективно реализовать свой BigInteger?
Захотелось реализовать свой BigInteger, но хочется сделать его максимально эффективным и быстрым. В первую очередь меня интересует как эффективно реализовать представление числа. Несомненно первая идея - представлять каждую цифру в 10-ричной системе счисления в отдельном массиве или строке. Но я не раз видел советы о том, что представление чисел в 2^n-ричной системе счисления является наиболее лучшим решением. Вопрос почему? Как реализовывать в такой системе счисления побитовые сдвиги? Как будут вообще работать все операции? Умножение? Деление? Также Harry упомянул 10^9-ричную систему счисления (в конце свеого ответа). Почему это также будет лучшим решением, чем просто десятиричная? Меньше создавать "блоков" для каждого числа? И из этого большая скорость работы?
- Как лучше представлять числа?
- Как лучше их хранить? строкой? динамическим массивом?
- Как реализовывать операции в таких "представлениях"?
Ответы (1 шт):
Давайте просто прикинем, сколько операций сложения нужно, чтобы сложить два, скажем, 99-значных числа вашим способом. Минимально - 99 сложений + 99 сложений с переносом + 99 делений и получений остатка. У вас еще и преобразований в символы...
Если работать с ограничением в миллиард - уже в 9 раз меньше.
Рассмотрим умножение - тут получаются числа порядка n*n, т.е. здесь применение миллиарда вместо символа ускорит операции как минимум в 81 раз :)
Ну, а почему 2n - да просто чтоб использовать память экономнее. Полный диапазон. Да и сами операции зачастую выполняются быстрее - особенно с остатком и делением - можно просто битовыми операциями.
Проблема только в том, что умножение и сложение пишутся очень просто, а вот деление... А без деления как выводить в десятеричном виде?
Вот потому я и упомянул миллиард - если деление не нужно (а в олимпиадных задачах это распространенное явление), а в каждом элементе - 9 разрядов длинного числа - то его очень легко вывести: просто выводить как есть, разве что добивая нулями слева при необходимости каждый разряд...
Вот, посмотрите тут - это одна из таких задачек, где нужно только суммировать/умножать. Интереса ради замените
static const unsigned int magic = 1000000000, digs = 9;
на
static const unsigned int magic = 100, digs = 2;
и сравните время работы для реально больших чисел...