Умножьте массив цифр на int в C

Question

У меня очень большое число (> 100 цифр), поэтому его нельзя сохранить как int или даже unsigned long long (aka uint64_t). Массив выглядит так:
{5, 1, 2 ... 8, 6}
Массив должен содержать одну цифру int с.

---

Вопрос

Каким был бы простой и, что наиболее важно, эффективный способ умножения этого «числа» (сохраняя его в виде массива) на одну цифру?

Что я пробовал

Поскольку я довольно новичок в C, этот код не является шедевром. Это далеко не так.

struct returnpointer { int * pointer; int length; };

returnpointer mul_arrays(int * x, int y, int lengthof_x) {
    returnpointer result_end;
    int result[lengthof_x * 2 + 1];
    int final_result[lengthof_x * 2 + 1];
    int carry = 0;
    int j = 0;
    //multiply 'y' by all digits of x, which creates multidigit ints
    //and also reverses the direction of the array (to allow carrying)
    for (int i = lengthof_x; i >= 0; i--) {
        result[j] = x[i] * y;
        j++;
    }
    int i = 0;
    j = lengthof_x
    //this is the bit that doesn't work: it attempts to work out the carry
    //however after hours of debugging I can't get it to work.
    while (carry > 0 || i < lengthof_x + 1) {
        if (result[j] > 9) {
            carry = result[j] / 10;
            final_result[i] = result[j] % 10;
            final_result[i + 1] = carry;
        } else {
            final_result[i] = result[j];
            carry = 0;
        }
        i++;
        j--;
    }
    result_end.pointer = result;
    result_end.length  = i + 1;
    return result_end;
}

Этот код не работает должным образом. Это просто иллюстрация того, что я пробовал (если бы это сработало, я бы не стал это публиковать).

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

Заранее спасибо.

EDIT:

Мой компилятор - g ++.

Answer 1

В соответствии с запросом приведен пример кода, который умножает массив на одну цифру.Массив является прямым порядком байтов.В качестве простого примера я предположил, что массив имеет фиксированную длину, более сложный - выделять память массива и расширять ее, если массив становится слишком большим.

#include <stdio.h>

#define BIGLEN 20

typedef struct {
    int length;
    int array[BIGLEN];
} biggy_t;

void bigmul(biggy_t *big, int mul)
{
    int carry = 0, partial;
    for(int i = 0; i < big->length; i++) {
        partial = big->array[i] * mul + carry;
        big->array[i] = partial % 10;
        carry = partial / 10;
    }
    if(carry) {
        big->array[big->length] = carry;
        big->length++;
    }
}

void bigout(biggy_t *big)
{
    for(int i = big->length-1; i >= 0; i--) {
        printf("%d", big->array[i]);
    }
}

int main(int argc, char *argv[])
{
    biggy_t big = { 6, { 5, 1, 2, 3, 8, 6 }};   // reverse order
    bigout(&big);
    printf(" * 7 = ");

    bigmul(&big, 7);
    bigout(&big);
    printf("\n");
}

Вывод программы

683215 * 7 = 4782505

Я написал реализацию bignum, в которой я могу выбрать основание.10 или 100 для байтового хранилища, гораздо больше для 32-битного хранилища.Придерживаясь степени 10, преобразование в десятичный вывод легче, чем степень 2, с небольшим штрафом за неиспользование полной емкости типа хранилища.

Answer 2

В вашем коде несколько проблем.Не уверен, что я их всех заметил, но вот некоторые из них, с которых нужно начать.

Этот цикл:

for (int i = lengthof_x; i >= 0; i--) {
    result[j] = x[i] * y;
    j++;
}

выполняется "lengthof_x + 1" раз.Другими словами - слишком много!Вы хотите изменить его на:

for (int i = lengthof_x - 1; i >= 0; i--) {  // notice the "- 1"
    result[j] = x[i] * y;
    j++;
}

Далее у вас есть:

result_end.pointer = result;

, но, похоже, вы вычислили результат в переменной final_result, поэтому вы возвращаете неверный результатмассив.

Однако - в любом случае вам не разрешено вернуть указатель на локальный массив!Когда функция вернется, она выйдет из области видимости.Так что даже если вы сделаете:

result_end.pointer = final_result;

, это все равно неверный код.Вам понадобится malloc массив (и это снизит производительность).

Тогда вы получите:

result_end.length  = i + 1;

Таким образом, вы увеличиваете длину в all случаев.Это неверно.Вы должны увеличивать значение только тогда, когда у вас есть перенос.

Ниже я попытался исправить ваш код, то есть я попытался сохранить общую структуру вашего кода, чтобы вы могли видеть, где вы допустили ошибки.

#include <stdio.h>
#include <stdlib.h>

struct returnpointer { int * pointer; int length; };

void print_num(struct returnpointer * num)
{
        printf("len=%d\nvalue=", num->length);
    for(int i = 0; i <num->length; i++) {
        printf("%d", num->pointer[i]);
    }
}

struct returnpointer mul_arrays(int * x, int y, int lengthof_x) {
    struct returnpointer result_end;
    int result[lengthof_x + 1];

    // Multiply all element and revert array
    int j = 0;
    for (int i = lengthof_x-1; i >= 0; i--) {
        result[j] = x[i] * y;
        j++;
    }

    // Handle carry 
    int carry = 0;
    for (j = 0; j < lengthof_x; j++) {
        result[j] = result[j] + carry;
        carry = result[j] / 10;
        result[j] = result[j] % 10;
    }

    // Did length increase
    if (carry)
    {
        lengthof_x++;
        result[j] = carry;
    }

    // malloc result and revert back to desired format
    j = 0;
    int* final_result = malloc(lengthof_x * sizeof *final_result);
    for (int i = lengthof_x-1; i >= 0; i--) {
        final_result[j] = result[i];
        j++;
    }

    result_end.pointer = final_result;
    result_end.length  = lengthof_x;
    return result_end;
}


int main(int argc, char *argv[])
{
    int arr[] = { 5, 1, 2, 3, 8, 6}; 
    struct returnpointer num = mul_arrays(arr, 2, 6);  // 512386 * 2 -> 1024772
    print_num(&num);
}

Вывод:

len=7
value=1024772

Обратите внимание, что это не оптимальное решение ...

Answer 3

Итак, несколько замечаний:

1) Я не думаю, что нужно переворачивать массив. Просто обработайте его от наименее значимого до самого значащего разряда.

2) Нет причин хранить временные значения, превышающие допустимый диапазон цифр. Просто делайте переноску, как вы, как если бы вы делали это вручную:

carry = 0
for i in all_the_digits:
    product = x[i]*y + carry
    x[i] = product%10
    carry = product/10

3) вы можете хранить цифры как uint8_t, не опасаясь переполнения - это сделает ваш массив 1/4 текущего размера, что должно улучшить скорость из-за эффектов кэширования.