bignum test, C (vc)

bignum test

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

#define MAXDIGITS   100  /* comprimento máximo do bignum */
#define PLUS          1  /* bit de sinal positivo */
#define MINUS        -1  /* bit de sinal negativo */

typedef struct {
	char digits[MAXDIGITS]; /* representa o número */
	int signbit;            /* 1 se positivo, -1 se negativo */
	int lastdigit;          /* índice do dígito mais significativo */
} bignum;

print_bignum(bignum *n)
{
	int i;

if (n->signbit == MINUS) printf("- ");
	for (i = n->lastdigit; i >= 0; i--)
		printf("%c", '0' + n->digits[i]);

printf("\n");
}

int_to_bignum(int s, bignum *n)
{
	int i;              /* contador */
	int t;              /* int a ser trabalhado */

if (s >= 0) n->signbit = PLUS;
	else n->signbit = MINUS;

for (i = 0; i<MAXDIGITS; i++) n->digits[i] = (char)0;

n->lastdigit = -1;

t = abs(s);

while (t > 0) {
		n->lastdigit++;
		n->digits[n->lastdigit] = (t % 10);
		t = t / 10;
	}

if (s == 0) n->lastdigit = 0;
}

initialize_bignum(bignum *n)
{
	int_to_bignum(0, n);
}

/*  c = a +-/* b;   */

subtract_bignum(bignum *a, bignum *b, bignum *c)
{
	int borrow;         /* algo a ser emprestado? */
	int v;              /* dígito placeholder (apenas para preenchimento do comprimento) */
	int i;              /* contador */

initialize_bignum(c);

if ((a->signbit == MINUS) || (b->signbit == MINUS)) {
		b->signbit = -1 * b->signbit;
		add_bignum(a, b, c);
		b->signbit = -1 * b->signbit;
		return;
	}

if (compare_bignum(a, b) == PLUS) {
		subtract_bignum(b, a, c);
		c->signbit = MINUS;
		return;
	}

c->lastdigit = max(a->lastdigit, b->lastdigit);
	borrow = 0;

for (i = 0; i <= (c->lastdigit); i++) {
		v = (a->digits[i] - borrow - b->digits[i]);
		if (a->digits[i] > 0)
			borrow = 0;
		if (v < 0) {
			v = v + 10;
			borrow = 1;
		}

c->digits[i] = (char)v % 10;
	}

zero_justify(c);
}

add_bignum(bignum *a, bignum *b, bignum *c)
{
	int carry;          /* dígito de transporte */
	int i;              /* contador */

initialize_bignum(c);

if (a->signbit == b->signbit) c->signbit = a->signbit;
	else {
		if (a->signbit == MINUS) {
			a->signbit = PLUS;
			subtract_bignum(b, a, c);
			a->signbit = MINUS;
		}
		else {
			b->signbit = PLUS;
			subtract_bignum(a, b, c);
			b->signbit = MINUS;
		}
		return;
	}

c->lastdigit = max(a->lastdigit, b->lastdigit) + 1;
	carry = 0;

for (i = 0; i <= (c->lastdigit); i++) {
		c->digits[i] = (char)(carry + a->digits[i] + b->digits[i]) % 10;
		carry = (carry + a->digits[i] + b->digits[i]) / 10;
	}

zero_justify(c);
}

compare_bignum(bignum *a, bignum *b)
{
	int i;              /* contador */

if ((a->signbit == MINUS) && (b->signbit == PLUS)) return(PLUS);
	if ((a->signbit == PLUS) && (b->signbit == MINUS)) return(MINUS);

if (b->lastdigit > a->lastdigit) return (PLUS * a->signbit);
	if (a->lastdigit > b->lastdigit) return (MINUS * a->signbit);

for (i = a->lastdigit; i >= 0; i--) {
		if (a->digits[i] > b->digits[i]) return(MINUS * a->signbit);
		if (b->digits[i] > a->digits[i]) return(PLUS * a->signbit);
	}

return(0);
}

zero_justify(bignum *n)
{
	while ((n->lastdigit > 0) && (n->digits[n->lastdigit] == 0))
		n->lastdigit--;

if ((n->lastdigit == 0) && (n->digits[0] == 0))
		n->signbit = PLUS;          /* hack para evitar -0 */
}

digit_shift(bignum *n, int d)       /* multiplica n por 10^d */
{
	int i;                          /* contador */

if ((n->lastdigit == 0) && (n->digits[0] == 0)) return;

for (i = n->lastdigit; i >= 0; i--)
		n->digits[i + d] = n->digits[i];

for (i = 0; i<d; i++) n->digits[i] = 0;

n->lastdigit = n->lastdigit + d;
}

multiply_bignum(bignum *a, bignum *b, bignum *c)
{
	bignum row;         /* representa a linha "shiftada" */
	bignum tmp;         /* bignum placeholder (apenas para preencher o comprimento) */
	int i, j;            /* contadores */

initialize_bignum(c);

row = *a;

for (i = 0; i <= b->lastdigit; i++) {
		for (j = 1; j <= b->digits[i]; j++) {
			add_bignum(c, &row, &tmp);
			*c = tmp;
		}
		digit_shift(&row, 1);
	}

c->signbit = a->signbit * b->signbit;

zero_justify(c);
}

divide_bignum(bignum *a, bignum *b, bignum *c)
{
	bignum row;                     /* representa a linha "shiftada" */
	bignum tmp;                     /* bignum placeholder (apenas para preencher o comprimento) */
	int asign, bsign;               /* sinais temporários */
	int i, j;                        /* contadores */

initialize_bignum(c);

c->signbit = a->signbit * b->signbit;

asign = a->signbit;
	bsign = b->signbit;

a->signbit = PLUS;
	b->signbit = PLUS;

initialize_bignum(&row);
	initialize_bignum(&tmp);

c->lastdigit = a->lastdigit;

for (i = a->lastdigit; i >= 0; i--) {
		digit_shift(&row, 1);
		row.digits[0] = a->digits[i];
		c->digits[i] = 0;
		while (compare_bignum(&row, b) != PLUS) {
			c->digits[i] ++;
			subtract_bignum(&row, b, &tmp);
			row = tmp;
		}
	}

zero_justify(c);

a->signbit = asign;
	b->signbit = bsign;
}

void main()
{
	unsigned int i, num, r;

bignum v[100], a, b;

printf("Progressão geométrica\n\n");
	printf("Informe um numero: ");
	num = 2;

printf("Informe a razão: ");
	r = 2;

int_to_bignum(num, &v[0]);
	int_to_bignum(r, &b);

for (i = 1; i < 100; ++i)
		multiply_bignum(&v[i - 1], &b, &v[i]);

for (i = 0; i < 100; ++i)
	{
		printf("Valor do %uº elemento da PA: ", i);
		print_bignum(&v[i]);
		puts("\n");
	}
}


run \| edit \| history \| help	2

λ

                                      .NET NoSQL database for rapid development