Biblioteka za velike brojeve
Napraviti malu C biblioteku za celobrojne brojeve proizvoljne dužine. Broj se čuva kao znak i dinamički niz cifara, a implementacija obezbedjuje sabiranje, oduzimanje, množenje, poređenje, kao i čitanje/pisanje iz fajlova.
Zadatak se rešava kroz fajlove bignum.h, bignum.c i main.c.
Podržane funkcije u biblioteci:
BigNum bignum_from_string(const char *s)– pravi novi (označeni) broj iz decimalne reprezentacije (dozvoljene vodeće nule i prefiksi+/-);BigNum bignum_from_file(FILE *f)– cita sledeći broj iz datoteke (preskače beline);int bignum_compare(const BigNum *a, const BigNum *b)– vraća-1,0ili1u zavisnosti od poređenja;BigNum bignum_add(const BigNum *a, const BigNum *b)– sabiranje;BigNum bignum_sub(const BigNum *a, const BigNum *b)– oduzimanje;BigNum bignum_mul(const BigNum *a, const BigNum *b)– množenje;BigNum bignum_neg(const BigNum *n)– kopira i menja znak broja;int bignum_fprint(FILE *f, const BigNum *n)ivoid bignum_print(const BigNum *n)– ispis u uobičajenoj decimalnoj formi; ivoid bignum_free(BigNum *n)– oslobađa dinamički niz cifara.
Ulaz
Sa standardnog ulaza se učitavaju komande sve do kraja ulaza. Dostupno je:
add <A> <B>– ispisuje zbir;sub <A> <B>– ispisuje razliku;mul <A> <B>– ispisuje proizvod;cmp <A> <B>– ispisuje-1,0ili1u zavisnosti od poređenja;neg <A>– ispisuje negaciju broja;addf <fA> <fB>,subf,mulf,cmpf,negf– isto, ali brojevi se čitaju iz fajlova sa putanjama<fA>i<fB>(jedan broj po fajlu);read <putanja>– učitava broj iz fajla i ispisuje ga; iwrite <broj> <putanja>– upisuje broj u fajl (prepisuje ga) i ispisuje isti broj nastdoutradi potvrde.
Izlaz
Za svaku validnu komandu ispisati traženi rezultat u posebnoj liniji.
U slučaju nepoznate komande ili neuspešnog čitanja fajla program prijavljuje grešku na standardni izlaz za greške i završava se neuspešno.
Primer
stdin
add -123456789123456789 987654321
sub 1000 5000
mul -999 999
cmp -10 -10
cmp -5 7
cmp 7 -5
stdout
-123456788135802468
-4000
-998001
0
1
-1
Primer
a.txt
-9999
b.txt
9999
stdin
addf a.txt b.txt
mulf a.txt b.txt
write 12345678901234567890 dump.txt
stdout
0
-99980001
12345678901234567890
dump.txt
12345678901234567890
Primer
b.txt
100
stdin
addf missing.txt b.txt
stderr
Error: Could not open file missing.txt
Rešenje
bignum.h
#ifndef BIGNUM_H
#define BIGNUM_H
#include <stddef.h>
#include <stdio.h>
typedef struct {
int sign; // 1 for non-negative, -1 for negative
size_t size; // number of digits
int *digits; // least significant digit first
} BigNum;
BigNum bignum_from_string(const char *s);
BigNum bignum_from_file(FILE *f);
void bignum_free(BigNum *n);
int bignum_compare(const void *a, const void *b); // returns 1, 0, -1
BigNum bignum_add(const BigNum *a, const BigNum *b);
BigNum bignum_sub(const BigNum *a, const BigNum *b);
BigNum bignum_mul(const BigNum *a, const BigNum *b);
BigNum bignum_neg(const BigNum *a);
int bignum_fprint(FILE *f, const BigNum *n);
void bignum_print(const BigNum *n);
#endifmain.c
#include "bignum.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static int read_two_inline(BigNum *a, BigNum *b)
{
char a_buf[4096];
char b_buf[4096];
if (scanf("%4095s %4095s", a_buf, b_buf) != 2) {
return 0;
}
*a = bignum_from_string(a_buf);
*b = bignum_from_string(b_buf);
return 1;
}
static int read_two_files(const char *path_a, const char *path_b, BigNum *a, BigNum *b)
{
FILE *fa = fopen(path_a, "r");
if (!fa) {
fprintf(stderr, "Error: Could not open file %s\n", path_a);
return 0;
}
FILE *fb = fopen(path_b, "r");
if (!fb) {
fclose(fa);
fprintf(stderr, "Error: Could not open file %s\n", path_b);
return 0;
}
*a = bignum_from_file(fa);
*b = bignum_from_file(fb);
fclose(fa);
fclose(fb);
return 1;
}
static void handle_binary_op(BigNum (*op)(const BigNum *, const BigNum *), int print_cmp)
{
BigNum a, b;
if (!read_two_inline(&a, &b)) {
fprintf(stderr, "Error: Invalid input format.\n");
exit(EXIT_FAILURE);
}
if (print_cmp) {
printf("%d\n", bignum_compare(&a, &b));
} else {
BigNum res = op(&a, &b);
bignum_print(&res);
bignum_free(&res);
}
bignum_free(&a);
bignum_free(&b);
}
static void handle_binary_file_op(BigNum (*op)(const BigNum *, const BigNum *), int print_cmp)
{
char path_a[512], path_b[512];
if (scanf("%511s %511s", path_a, path_b) != 2) {
fprintf(stderr, "Error: Invalid input format.\n");
exit(EXIT_FAILURE);
}
BigNum a, b;
if (!read_two_files(path_a, path_b, &a, &b)) {
exit(EXIT_FAILURE);
}
if (print_cmp) {
printf("%d\n", bignum_compare(&a, &b));
} else {
BigNum res = op(&a, &b);
bignum_print(&res);
bignum_free(&res);
}
bignum_free(&a);
bignum_free(&b);
}
static void handle_unary_op(BigNum (*op)(const BigNum *))
{
char num_buf[4096];
if (scanf("%4095s", num_buf) != 1) {
fprintf(stderr, "Error: Invalid input format.\n");
exit(EXIT_FAILURE);
}
BigNum n = bignum_from_string(num_buf);
BigNum res = op(&n);
bignum_print(&res);
bignum_free(&n);
bignum_free(&res);
}
static void handle_unary_file_op(BigNum (*op)(const BigNum *))
{
char path[512];
if (scanf("%511s", path) != 1) {
fprintf(stderr, "Error: Invalid input format.\n");
exit(EXIT_FAILURE);
}
FILE *f = fopen(path, "r");
if (!f) {
fprintf(stderr, "Error: Could not open file %s\n", path);
exit(EXIT_FAILURE);
}
BigNum n = bignum_from_file(f);
BigNum res = op(&n);
fclose(f);
bignum_print(&res);
bignum_free(&res);
}
static void handle_read()
{
char path[512];
if (scanf("%511s", path) != 1) {
fprintf(stderr, "Error: Invalid input format.\n");
exit(EXIT_FAILURE);
}
FILE *f = fopen(path, "r");
if (f == NULL) {
fprintf(stderr, "Error: Could not open file %s\n", path);
exit(EXIT_FAILURE);
}
BigNum n = bignum_from_file(f);
fclose(f);
bignum_print(&n);
bignum_free(&n);
}
static void handle_write()
{
char num_buf[4096];
char path[512];
if (scanf("%4095s %511s", num_buf, path) != 2) {
fprintf(stderr, "Error: Invalid input format.\n");
exit(EXIT_FAILURE);
}
BigNum n = bignum_from_string(num_buf);
FILE *out = fopen(path, "w");
if (out == NULL) {
fprintf(stderr, "Error: Could not open file %s\n", path);
bignum_free(&n);
exit(EXIT_FAILURE);
}
if (!bignum_fprint(out, &n)) {
fprintf(stderr, "Error: Could not write file %s\n", path);
fclose(out);
bignum_free(&n);
exit(EXIT_FAILURE);
}
bignum_print(&n);
fclose(out);
bignum_free(&n);
}
int main(void)
{
char op[16];
while (scanf("%15s", op) == 1) {
if (strcmp(op, "add") == 0) {
handle_binary_op(bignum_add, 0);
} else if (strcmp(op, "sub") == 0) {
handle_binary_op(bignum_sub, 0);
} else if (strcmp(op, "mul") == 0) {
handle_binary_op(bignum_mul, 0);
} else if (strcmp(op, "cmp") == 0) {
handle_binary_op(bignum_add, 1);
} else if (strcmp(op, "neg") == 0) {
handle_unary_op(bignum_neg);
} else if (strcmp(op, "addf") == 0) {
handle_binary_file_op(bignum_add, 0);
} else if (strcmp(op, "subf") == 0) {
handle_binary_file_op(bignum_sub, 0);
} else if (strcmp(op, "mulf") == 0) {
handle_binary_file_op(bignum_mul, 0);
} else if (strcmp(op, "cmpf") == 0) {
handle_binary_file_op(bignum_add, 1);
} else if (strcmp(op, "negf") == 0) {
handle_unary_op(bignum_neg);
} else if (strcmp(op, "read") == 0) {
handle_read();
} else if (strcmp(op, "write") == 0) {
handle_write();
} else {
fprintf(stderr, "Error: Unknown operation %s\n", op);
exit(EXIT_FAILURE);
}
}
exit(EXIT_SUCCESS);
}bignum.c
#include "bignum.h"
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
static BigNum bignum_zero(void)
{
BigNum n;
n.sign = 1;
n.size = 1;
n.digits = calloc(1, sizeof(int));
if (n.digits == NULL) {
exit(EXIT_FAILURE);
}
n.digits[0] = 0;
return n;
}
static void bignum_strip(BigNum *n)
{
while (n->size > 1 && n->digits[n->size - 1] == 0) {
n->size--;
}
if (n->size == 1 && n->digits[0] == 0) {
n->sign = 1;
}
}
static int bignum_compare_abs(const BigNum *a, const BigNum *b)
{
if (a->size < b->size) {
return 1;
}
if (a->size > b->size) {
return -1;
}
for (size_t i = a->size; i-- > 0;) {
if (a->digits[i] < b->digits[i]) {
return 1;
}
if (a->digits[i] > b->digits[i]) {
return -1;
}
}
return 0;
}
static BigNum bignum_add_abs(const BigNum *a, const BigNum *b)
{
BigNum res;
size_t max_len = (a->size > b->size) ? a->size : b->size;
res.sign = 1;
res.digits = calloc(max_len + 1, sizeof(int));
if (res.digits == NULL) {
exit(EXIT_FAILURE);
}
res.size = max_len + 1;
int carry = 0;
for (size_t i = 0; i < max_len; i++) {
int sum = carry;
if (i < a->size) {
sum += a->digits[i];
}
if (i < b->size) {
sum += b->digits[i];
}
res.digits[i] = sum % 10;
carry = sum / 10;
}
res.digits[max_len] = carry;
bignum_strip(&res);
return res;
}
static BigNum bignum_sub_abs(const BigNum *a, const BigNum *b) // assumes |a| >= |b|
{
BigNum res;
res.sign = 1;
res.size = a->size;
res.digits = calloc(res.size, sizeof(int));
if (res.digits == NULL) {
exit(EXIT_FAILURE);
}
int borrow = 0;
for (size_t i = 0; i < a->size; i++) {
int diff = a->digits[i] - borrow;
if (i < b->size) {
diff -= b->digits[i];
}
if (diff < 0) {
diff += 10;
borrow = 1;
} else {
borrow = 0;
}
res.digits[i] = diff;
}
bignum_strip(&res);
return res;
}
static int is_zero(const BigNum *a)
{
return a->size == 1 && a->digits[0] == 0;
}
BigNum bignum_from_string(const char *s)
{
if (s == NULL) {
return bignum_zero();
}
while (isspace(*s)) {
s++;
}
int sign = 1;
if (*s == '+') {
s++;
} else if (*s == '-') {
sign = -1;
s++;
}
while (*s == '0' && isdigit(*(s + 1))) {
s++;
}
const char *start = s;
size_t len = 0;
while (isdigit(start[len])) {
len++;
}
if (len == 0) {
return bignum_zero();
}
BigNum n;
n.sign = sign;
n.size = len;
n.digits = calloc(len, sizeof(int));
if (n.digits == NULL) {
exit(EXIT_FAILURE);
}
for (size_t i = 0; i < len; i++) {
n.digits[i] = start[len - 1 - i] - '0';
}
bignum_strip(&n);
return n;
}
BigNum bignum_from_file(FILE *f)
{
if (f == NULL) {
return bignum_zero();
}
char *buffer = NULL;
size_t size = 0;
ssize_t len = getline(&buffer, &size, f);
if (len == -1) {
free(buffer);
return bignum_zero();
}
BigNum res = bignum_from_string(buffer);
free(buffer);
return res;
}
void bignum_free(BigNum *n)
{
if (n != NULL && n->digits != NULL) {
free(n->digits);
n->digits = NULL;
n->size = 0;
n->sign = 1;
}
}
int bignum_compare(const void *a, const void *b)
{
const BigNum *num_a = (const BigNum *) a;
const BigNum *num_b = (const BigNum *) b;
if (num_a->sign < num_b->sign) {
return 1;
}
if (num_a->sign > num_b->sign) {
return -1;
}
int abs_cmp = bignum_compare_abs(num_a, num_b);
return num_a->sign * abs_cmp;
}
BigNum bignum_add(const BigNum *a, const BigNum *b)
{
if (a->sign == b->sign) {
BigNum res = bignum_add_abs(a, b);
res.sign = a->sign;
return res;
}
int cmp = bignum_compare_abs(a, b);
if (cmp == 0) {
return bignum_zero();
}
if (cmp > 0) {
BigNum res = bignum_sub_abs(b, a);
res.sign = b->sign;
return res;
} else {
BigNum res = bignum_sub_abs(a, b);
res.sign = a->sign;
return res;
}
}
BigNum bignum_sub(const BigNum *a, const BigNum *b)
{
BigNum neg_b = bignum_neg(b);
BigNum res = bignum_add(a, &neg_b);
bignum_free(&neg_b);
return res;
}
BigNum bignum_mul(const BigNum *a, const BigNum *b)
{
if (is_zero(a) || is_zero(b)) {
return bignum_zero();
}
BigNum res;
res.sign = a->sign * b->sign;
res.size = a->size + b->size;
res.digits = calloc(res.size, sizeof(int));
if (res.digits == NULL) {
exit(EXIT_FAILURE);
}
for (size_t i = 0; i < a->size; i++) {
for (size_t j = 0; j < b->size; j++) {
res.digits[i + j] += a->digits[i] * b->digits[j];
}
}
int carry = 0;
for (size_t k = 0; k < res.size; k++) {
int value = res.digits[k] + carry;
res.digits[k] = value % 10;
carry = value / 10;
}
if (carry > 0) {
int *tmp = realloc(res.digits, (res.size + 1) * sizeof(int));
if (tmp == NULL) {
bignum_free(&res);
exit(EXIT_FAILURE);
}
res.digits = tmp;
res.digits[res.size] = carry;
res.size++;
}
bignum_strip(&res);
return res;
}
BigNum bignum_neg(const BigNum *a)
{
BigNum res;
res.sign = -a->sign;
res.size = a->size;
res.digits = calloc(res.size, sizeof(int));
if (res.digits == NULL) {
exit(EXIT_FAILURE);
}
memcpy(res.digits, a->digits, res.size * sizeof(int));
return res;
}
int bignum_fprint(FILE *f, const BigNum *n)
{
if (f == NULL || n == NULL || n->digits == NULL) {
return 0;
}
if (n->sign < 0 && !(n->size == 1 && n->digits[0] == 0)) {
if (fputc('-', f) == EOF) {
return 0;
}
}
for (int i = n->size - 1; i >= 0; i--) {
char c = '0' + n->digits[i];
if (fputc(c, f) == EOF) {
return 0;
}
}
if (fputc('\n', f) == EOF) {
return 0;
}
return 1;
}
void bignum_print(const BigNum *n)
{
bignum_fprint(stdout, n);
}