Какая база подойдет для моей библиотеки BigInteger?

Question

Я разработал свою собственную библиотеку BigInteger на C ++ для дидактических целей, изначально я использовал базу 10, и она отлично работает для сложения, вычитания и умножения, но для некоторых алгоритмов, таких как возведение в степень, модульное возведение в степень и деление, кажется более целесообразно использовать базу 2.

Я думаю перезапустить свой проект с нуля, и я бы знал, какая база, по вашему мнению, более адекватна и почему ?. Заранее спасибо!

Answer 1

Если вы посмотрите на большинство библиотек типов BigNum, то увидите, что они построены поверх существующих типов данных "SmallNum". Эти типы данных "SmallNum" (short, int, long, float, double, ...) находятся в двоичном формате по слишком многим причинам для подсчета. Вместо вектора из 10 основных цифр ваш код будет намного быстрее (намного, намного, намного быстрее!), Если работать с вектором (например) unsigned int s.

Это одно из тех мест, где производительность имеет значение. Предположим, вы используете пакет BigNum для решения проблемы, которая может быть решена без обращения к BigNum. Даже лучшая библиотека BigNum будет намного медленнее (намного, намного медленнее), чем упрощенный, не BigNum подход. Если вы попытаетесь решить проблему, выходящую за рамки стандартных представлений, снижение производительности приведет к еще большему ухудшению.

Лучший способ преодолеть это врожденное наказание - использовать как можно больше преимуществ встроенных типов.

Answer 2

Представление base 10 имеет смысл для типа BigDecimal, где вам необходимо точно представлять десятичные дроби (для финансовых расчетов и т. П.).

Я не вижу большой пользы от использования базового 10 представления для BigInteger. Это делает преобразование строк действительно простым, но за счет выполнения математических операций намного более сложным. В большинстве случаев это не кажется хорошим компромиссом.

Answer 3

База, такая же, как размер слова на вашей целевой машине, где у вас есть слово x word = doubleword в качестве примитива.Примитивные операции работают аккуратно с точки зрения машинных инструкций.