Каков самый простой способ реализовать bigint в C?
Я пытаюсь вычислить 100!
Я ищу самый простой способ выполнить это использование C. Я читал вокруг, но не нашел конкретный ответ.
Если необходимо знать, я программирую в XCode в Mac OS X.
Спасибо!
4 ответа
Если вы ищете простую библиотеку, возможно, вам подойдет 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), и вам следует нет проблем.
Если вы хотите использовать библиотечную реализацию, стандартная, кажется, GMP
mpz_t out;
mpz_init(out);
mpz_fac_ui(out,100);
mpz_out_str(stdout,10,out);
должна вычислить 100! глядя на документы.
Вы также можете использовать OpenSSL bn ; он уже установлен в Mac OS X.
Вы просили простейший способ сделать это. Итак, готово:
#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;
}
Я тестировал этот код, и он дает правильный ответ.