Какой самый простой способ реализации bigint в C? - PullRequest
Новая
       12

Какой самый простой способ реализации bigint в C?

19 голосов
/ 27 июля 2010

Я пытаюсь вычислить 100!

Я ищу самый простой способ сделать это с помощью C. Я прочитал, но не нашел конкретного ответа.

Если вы должны знать, я программирую на Xcode в Mac OS X.

Спасибо!

Ответы [ 4 ]

23 голосов
/ 27 июля 2010

Если вы ищете простую библиотеку, возможно, вам нужен libtommath (из libtomcrypt).

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

Поскольку вы можете ограничить размер результата на основе n, просто предварительно выделите массив uint32_t необходимого размера для хранения результата. Я предполагаю, что вы захотите напечатать результат, поэтому имеет смысл использовать основание, которое имеет степень 10 (т. Е. Основание 1000000000), а не степень 2. То есть каждый элемент вашего массива может содержать значение от 0 до 999999999.

Чтобы умножить это число на (нормальное, не большое) целое число n, сделайте что-то вроде: 

uint32_t carry=0;
for(i=0; i<len; i++) {
    uint64_t tmp = n*(uint64_t)big[i] + carry;
    big[i] = tmp % 1000000000;
    carry = tmp / 1000000000;
}
if (carry) big[len++] = carry;

Если вы знаете, что n никогда не будет больше 100 (или другого небольшого числа) и хотите избежать перехода в 64-битный диапазон (или если вы используете 64-битную платформу и хотите использовать uint64_t для вашего массива bigint), затем уменьшите основание до 10, чтобы результат умножения всегда соответствовал типу.

Теперь печать результата выглядит примерно так: 

printf("%lu", (long)big[len-1]);
for(i=len-1; i; i--) printf("%.9lu", (long)big[i-1]);
putchar('\n');

Если вы хотите использовать степень 2 в качестве базы, а не степень 10, умножение становится намного быстрее: 

uint32_t carry=0;
for(i=0; i<len; i++) {
    uint64_t tmp = n*(uint64_t)big[i] + carry;
    big[i] = tmp;
    carry = tmp >> 32;
}
if (carry) big[len++] = carry;

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

printf("%lx", (long)big[len-1]);
for(i=len-1; i; i--) printf("%.8lx", (long)big[i-1]);
putchar('\n');

Надеюсь, это поможет! Я оставлю реализацию других вещей (например, сложение, умножение двух больших чисел и т. Д.) В качестве упражнения для вас. Просто вспомните, как вы научились делать сложение, умножение, деление и т. Д. В начальной школе в 10-м классе, и научите компьютер, как это делать (но вместо этого - в базовом-10 ^ 9 или базовом-2 ^ 32), и вам следует нет проблем.

6 голосов
/ 27 июля 2010

Если вы хотите использовать библиотечную реализацию, стандартная версия выглядит так: GMP 

mpz_t out;
mpz_init(out);
mpz_fac_ui(out,100);
mpz_out_str(stdout,10,out);

должно вычислять 100!смотреть на документы.

2 голосов
/ 27 июля 2010

Вы также можете использовать OpenSSL bn ; он уже установлен в Mac OS X.

1 голос
/ 27 июля 2010

Вы попросили самый простой способ сделать это. Итак, поехали: 

#include <gmp.h>
#include <stdio.h>

int main(int argc, char** argv) {
    mpz_t mynum;
    mpz_init(mynum);
    mpz_add_ui(mynum, 100);
    int i;
    for (i = 99; i > 1; i--) {
        mpz_mul_si(mynum, mynum, (long)i);
    }
    mpz_out_str(stdout, 10, mynum);
    return 0;
}

Я проверил этот код, и он дает правильный ответ.

...