Как лучше всего реализовать BCD в качестве упражнения?

Question

Я начинающий (самообучающийся) программист, изучающий C ++, и недавно я решил реализовать двоично-десятичный (BCD) класс в качестве упражнения, и поэтому я мог обрабатывать очень большие числа в Project Euler . Я хотел бы сделать это как можно более подробно, начиная с нуля.

Я начал с массива целых чисел, где каждая цифра входного числа была сохранена как отдельный int. Я знаю, что каждая цифра BCD может быть закодирована только 4 битами, поэтому я подумал, что использование целого int для этого было бы немного излишним. Я сейчас использую массив bitset <4>.

1. Используете ли вы такой же класс библиотеки, как этот перебор?
2. Считаете ли вы это обманом?
3. Есть ли лучший способ сделать это?

РЕДАКТИРОВАТЬ: Основная причина этого в качестве упражнения - я не хотел бы использовать библиотеку, как GMP, потому что весь смысл в создании класса сам. Есть ли способ убедиться, что я использую только 4 бита для каждой десятичной цифры?

Answer 1

Всего одна нота, для использования массива bitset<4> потребуется столько же места, сколько для массива long. набор битов обычно реализуется с помощью массива целочисленных слов, являющегося резервным хранилищем для битов, так что побитовые операции могут использовать побитовые операции со словами, а не байтовые, так что больше делается за раз.

Кроме того, я ставлю под сомнение вашу мотивацию. BCD обычно используется в качестве упакованного представления строки цифр при отправке их между системами. Обычно нет ничего общего с арифметикой. Что вам действительно нужно, так это целочисленная арифметическая библиотека произвольного размера, такая как GMP .

Answer 2

1. Используете ли вы такой же класс библиотеки, как этот перебор?
2. Считаете ли вы это обманом?
3. Есть ли лучший способ сделать это?

1 & 2: не совсем

3: каждый байт имеет 8 битов, вы можете хранить 2 BCD в каждом неподписанном символе.

Answer 3

Как сказал Грег Роджерс, использование набора битов, вероятно, не сэкономит пространство над целочисленными значениями и не даст никаких других преимуществ. Я бы, вероятно, использовал вместо этого вектор. Это вдвое больше, чем нужно, но вы получаете более простую и быструю индексацию для каждой цифры.

Если вы хотите использовать упакованный BCD, вы можете написать пользовательскую функцию индексации и сохранить две цифры в каждом байте.

Answer 4

Используете ли вы такой же класс библиотеки, как этот перебор?

Я бы сравнил его с массивом целых, чтобы увидеть, какой из них работает лучше. Если массив bitset <4> быстрее, то нет, это не перебор. Немного помогает при некоторых проблемах PE

Считаете ли вы это обманом?

Нет, совсем нет.

Есть ли лучший способ сделать это?

Как предположил Грег Роджерс, библиотека произвольной точности, вероятно, является лучшим выбором, если вы просто не хотите учиться на собственных. Есть чему поучиться у обоих методов (использование библиотеки или написание библиотеки). Я ленивый, поэтому я обычно использую Python.

Answer 5

Вы пытаетесь получить представление base-10 (то есть десятичную цифру в каждой ячейке массива). Таким образом, пространство (одно целое на цифру) или время (4 бита на цифру, но накладные расходы на упаковку / распаковку) тратится впустую.

Почему бы не попробовать, например, с base-256, и использовать массив байтов? Или даже база-2 ^ 32 с массивом целых? Операции реализованы так же, как и в Base-10. Единственное, что будет отличаться - это преобразовать число в удобочитаемую строку.

Может работать так: Предполагая base-256, каждая «цифра» имеет 256 возможных значений, поэтому числа 0–255 - это однозначные значения. Чем 256 пишется как 1: 0 (я буду использовать двоеточие для разделения «цифр», мы не можем использовать буквы, как в base-16), аналог в base-10, как после 9, есть 10. Аналогично 1030 (база-10) = 4 * 256 + 6 = 4: 6 (база-256). Также 1020 (база-10) = 3 * 256 + 252 = 3: 252 (база-256) - двузначное число в базе-256.

Теперь давайте предположим, что мы помещаем цифры в массив байтов с наименьшей значащей цифрой первой:

unsigned short digits1[] = { 212, 121 }; // 121 * 256 + 212 = 31188
int len1 = 2;
unsigned short digits2[] = { 202, 20  }; // 20 * 256 + 202 = 5322
int len2 = 2;

Тогда добавление будет происходить так (предупреждение: код блокнота впереди, возможно, не работает):

unsigned short resultdigits[enough length] = { 0 };
int len = len1 > len2 ? len1 : len2; // max of the lengths
int carry = 0;
int i;
for (i = 0; i < len; i++) {
    int leftdigit = i < len1 ? digits1[i] : 0;
    int rightdigit = i < len2 ? digits2[i] : 0;
    int sum = leftdigit + rightdigit + carry;
    if (sum > 255) {
        carry = 1;
        sum -= 256;
    } else {
        carry = 0;
    }
    resultdigits[i] = sum;
}
if (carry > 0) {
    resultdigits[i] = carry;
}

На первой итерации она должна выглядеть следующим образом:

1. сумма = 212 + 202 + 0 = 414
2. 414> 256, поэтому нести = 1 и сумма = 414 - 256 = 158
3. resultdigits [0] = 158

На второй итерации:

1. сумма = 121 + 20 + 1 = 142
2. 142 <256, поэтому нести = 0 </li>
3. resultdigits [1] = 142

Итак, в конце resultdigits [] = {158, 142}, то есть 142: 158 (base-256) = 142 * 256 + 158 = 36510 (base-10), что в точности равно 31188 + 5322

Обратите внимание, что преобразование этого числа в / из понятной человеку формы ни в коем случае не является тривиальной задачей - оно требует умножения и деления на 10 или 256, и я не могу представить код в качестве образца без надлежащего исследования. Преимущество состоит в том, что операции «сложение», «вычитание» и «умножение» могут быть действительно эффективными, а интенсивное преобразование в / из базы-10 выполняется только один раз в начале и один раз после окончания вычисления.

Сказав все это лично, я бы использовал базу 10 в массиве байтов и не заботился о потере памяти. Это потребует корректировки констант 255 и 256 выше до 9 и 10 соответственно.

Answer 6

Как правило, битовые операции применяются в контексте целого числа, поэтому с точки зрения производительности нет реальной причины переходить к битам.

Если вы хотите использовать битовый подход для получения опыта, то это может помочь

#include <stdio.h>
int main
(
    void
)
{
    typedef struct
    {
        unsigned int value:4;

    } Nibble;

    Nibble nibble;

    for (nibble.value = 0; nibble.value < 20; nibble.value++)
    {
        printf("nibble.value is %d\n", nibble.value);
    }

    return 0;
}

Суть в том, что внутри этой struct вы создаете короткое целое число, шириной 4 бита. Под капотом это действительно целое число, но для вашего предполагаемого использования оно выглядит и действует как 4-битное целое.

Это ясно видно по циклу для , который на самом деле представляет собой бесконечный цикл . Когда значение nibble достигает 16, значение действительно равно нулю, поскольку есть только 4 бита для работы. В результате nibble.value <20 </strong> никогда не становится истинным.

Если вы посмотрите в Белую книгу K & R, одним из примечаний является тот факт, что подобные битовые операции не переносимы , поэтому, если вы хотите перенести вашу программу на другую платформу, она может или может не работать.

Веселитесь.