Fizzbuzz Algorithmus

[blackberry]

Hmmm. Ich habe schon etwas länger nicht mehr programmiert, bin also etwas eingerostet. Nach meiner Brainfuck-Version aus dem von ReiDC0Re verlinkten Thread, wollte ich es nun auch mal in C versuchen. Leider war ich mir nicht mehr sicher, ob C noch modern genug ist, um so große Zahlen wie 100 speichern zu können. Aber dem kann man ja problemlos Abhilfe schaffen, wenn man sich passende Funktionen implementiert, um mit großen Zahlen umgehen zu können. Der eigentliche Code für das FizzBuzz geht einem dann sehr flüssig von der Hand:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <assert.h>

/*------------------------------------------------------------------*\
	I N T L I B:		H E A D E R
 \*------------------------------------------------------------------*/
#ifndef _LST_H
#define _LST_H

typedef struct {
	unsigned char *ptr;
	unsigned int len;
	unsigned int reallen;
} INT;

#define INTLIB_DEFAULT_LEN		8
#define INTLIB_EXPONENT			(1 << 8)

int intlib_init_len(INT *a, unsigned int len);
int intlib_init(INT *a);
void intlib_zero(INT *a);
void intlib_set(INT *a, unsigned int b);
int intlib_copy(INT *a, INT *b);
int intlib_resize(INT *a, unsigned int reallen);
void intlib_destroy(INT *a);
int intlib_add(INT *a, INT *b, INT *c);
int intlib_sub(INT *a, INT *b, INT *c);
int intlib_shift_left(INT *a, INT *b);
void intlib_print(INT *a);
int intlib_mul(INT *a, INT *b, INT *ab);
int intlib_div_mod(INT *a, INT *b, INT *c, INT *res);
int intlib_div(INT *a, INT *b, INT *c);
int intlib_mod(INT *a, INT *b, INT *c);

#define __DEBUG_PRINT printf("\n__LINE__ = %d\n", __LINE__)

#endif

/*------------------------------------------------------------------*\
	I N T L I B:		M E M O R Y   M A N A G E M E N T
 \*------------------------------------------------------------------*/

static unsigned int intlib_instance_counter = 0;

int intlib_init_len(INT *a, unsigned int len)
{
	unsigned int l = 1+len/8;
	if (l < INTLIB_DEFAULT_LEN)
		l = INTLIB_DEFAULT_LEN;
	a->reallen = a->len = 0;
	a->ptr = 0;
	intlib_instance_counter++;
	return intlib_resize(a, l);
}

int intlib_init(INT *a)
{
	return intlib_init_len(a, 0);
}

void intlib_destroy(INT *a)
{
	if (!(intlib_instance_counter--))
		intlib_instance_counter = 9999;
	free(a->ptr);
	a->ptr = 0;
	a->len = 0;
}

int intlib_resize(INT *a, unsigned int reallen)
{
	unsigned char *ptr;
	if (reallen < sizeof(int))
		return 1;
	if (a->reallen > reallen && a->len > reallen*8)
		return 2;
	if (a->reallen != reallen)
	{
		if (!(ptr = realloc(a->ptr, reallen)))
			return 4;
		if (a->reallen < reallen)
			memset(ptr + a->reallen, 0, reallen - a->reallen);
		a->ptr = ptr;
		a->reallen = reallen;
	}
	return 0;
}

/*------------------------------------------------------------------*\
	I N T L I B:		I N T   I N I T I A L I Z A T I O N
 \*------------------------------------------------------------------*/

void intlib_zero(INT *a)
{
	a->len = 0;
	memset(a->ptr, 0, a->reallen);
}

void intlib_set(INT *a, unsigned int b)
{
	int e = 1, i, j;
	intlib_zero(a);
	for(i = j = 0; b > 0; i++, b >>= 1)
	{
		a->len++;
		if (b & 1)
			a->ptr[j] |= e;
		if ((e <<= 1) == INTLIB_EXPONENT)
		{
			j++;
			e = 1;
		}
	}
}

int intlib_copy(INT *a, INT *b)
{
	int r;
	if ((r = intlib_resize(b, a->reallen)))
		return r;
	memcpy(b->ptr, a->ptr, a->reallen);
	b->len = a->len;
	return 0;
}

int intlib_equal(INT *a, INT *b)
{
	int i;
	unsigned int reallen = (a->reallen > b->reallen) ? b->reallen : a->reallen;
	if (a->len != b->len)
		return 0;
	for(i = 0; i < reallen; i++)
	{
		if (a->ptr[i] != b->ptr[i])
			return 0;
	}
	return 1;
}

/*------------------------------------------------------------------*\
	I N T L I B:		B A S I C   A R I T H M E T I C
 \*------------------------------------------------------------------*/

int intlib_add(INT *a, INT *b, INT *c)
{
	int i, j, r, carry = 0, bit, bit1, bit2, e = 1;
	unsigned int len = 1 + ((a->len > b->len) ? a->len : b->len);
	INT d;
	if ((r = intlib_init_len(&d, len)))
		return r;
	for(i = j = 0; i < len; i++)
	{
		bit1 = bit2 = 0;
		if (j < a->reallen)
			bit1 = (a->ptr[j] & e) > 0;
		if (j < b->reallen)
			bit2 = (b->ptr[j] & e) > 0;
		bit = bit1 + bit2 + carry;
		carry = bit > 1;
		if (bit & 1)
		{
			d.ptr[j] |= e;
			d.len = i + 1;
		}
		if ((e <<= 1) == INTLIB_EXPONENT)
		{
			j++;
			e = 1;
		}
	}
	intlib_destroy(c);
	*c = d;
	return 0;
}

int intlib_sub(INT *a, INT *b, INT *c)
{
	int i, j, r, carry = 0, bit, bit1, bit2, e = 1;
	unsigned int len = (a->len > b->len) ? a->len : b->len;
	INT d, x;
	if (a->len < b->len)
	{
		intlib_zero(c);
		return 0;
	}
	if ((r = intlib_init_len(&d, len)))
		return r;
	for(i = j = 0; i < len; i++)
	{
		bit1 = 0;
		bit2 = 1;
		if (j < a->reallen)
			bit1 = (a->ptr[j] & e) > 0;
		if (j < b->reallen)
			bit2 = (b->ptr[j] & e) == 0;
		bit = bit1 + bit2 + carry;
		carry = bit > 1;
		if (bit & 1)
		{
			d.ptr[j] |= e;
			d.len = i + 1;
		}
		if ((e <<= 1) == INTLIB_EXPONENT)
		{
			j++;
			e = 1;
		}
	}
	if (carry)
	{
		if ((r = intlib_init(&x)))
			return r;
		intlib_set(&x, 1);
		intlib_add(&d, &x, &d);
		intlib_destroy(&x);
	}
	else
		intlib_zero(&d);
	intlib_destroy(c);
	*c = d;
	return 0;
}

int intlib_shift_left(INT *a, INT *b)
{
	int r, i, carry = 0;
	INT c;
	if (!a->len)
		intlib_zero(b);
	else
	{
		if ((r = intlib_init_len(&c, a->len + 1)))
			return r;
		c.len = a->len + 1;
		for(i = 0; 8*i < a->len; i++)
		{
			c.ptr[i] = (a->ptr[i] << 1) | carry;
			carry = a->ptr[i] >> 7;
		}
		if (i < c.reallen)
			c.ptr[i] = carry;
		intlib_destroy(b);
		*b = c;
	}
	return 0;
}

int intlib_mul(INT *a, INT *b, INT *ab)
{
	int i, j, r, e = 1;
	INT c, d, *tmp;
	if (a->len > b->len)
	{
		tmp = a;
		a = b;
		b = tmp;
	}
	if (!b->len)
	{
		intlib_zero(ab);
		return 0;
	}
	if ((r = intlib_init_len(&c, a->len + b->len)) ||
		(r = intlib_init_len(&d, a->len + b->len)))
		return r;
	intlib_copy(b, &c);
	for(i = j = 0; i < a->len; i++)
	{
		if (a->ptr[j] & e)
		{
			intlib_add(&c, &d, &d);
		}
		if ((r = intlib_shift_left(&c, &c)))
			return r;
		if ((e <<= 1) == INTLIB_EXPONENT)
		{
			j++;
			e = 1;
		}
	}
	intlib_destroy(&c);
	intlib_destroy(ab);
	*ab = d;
	return 0;
}

int intlib_div_mod(INT *a, INT *b, INT *c, INT *res)
{
	int i, j, r, e = 1;
	INT d, x, y;
	if (a->len < b->len)
	{
		intlib_copy(a, res);
		intlib_zero(c);
		return 0;
	}
	if (!b->len)
	{
		return 8; // division by zero
	}
	if ((r = intlib_init_len(&d, 1 + a->len - b->len)) ||
		(r = intlib_init_len(&x, 1 + b->len)) ||
		(r = intlib_init_len(&y, 1 + b->len)))
		return r;
	j = (a->len-1) / 8;
	if (j < 0)
		j = 0;
	e = 1 << ((a->len-1) % 8);
	if (a->len < 2)
		e = 1;
	for(i = 0; i < a->len; i++)
	{
		intlib_shift_left(&d, &d);
		intlib_shift_left(&x, &x);
		
		if (a->ptr[j] & e)
		{
			x.ptr[0] |= 1;
			if (!x.len)
				x.len = 1;
		}
		intlib_sub(&x, b, &y);
		if (y.len || intlib_equal(&x, b))
		{
			d.ptr[0] |= 1;
			if (!d.len)
				d.len = 1;
			intlib_copy(&y, &x);
		}
		if (!(e >>= 1))
		{
			j--;
			e = 1 << 7;
		}
	}
	intlib_destroy(&y);
	intlib_destroy(res);
	intlib_destroy(c);
	*c = d;
	*res = x;
	return 0;
}

int intlib_div(INT *a, INT *b, INT *c)
{
	int r;
	INT d;
	if ((r = intlib_init(&d)))
		return r;
	r = intlib_div_mod(a, b, c, &d);
	intlib_destroy(&d);
	return r;
}

int intlib_mod(INT *a, INT *b, INT *c)
{
	int r;
	INT d;
	if ((r = intlib_init(&d)))
		return r;
	r = intlib_div_mod(a, b, &d, c);
	intlib_destroy(&d);
	return r;
}

/*------------------------------------------------------------------*\
	I N T L I B:		D E B U G   O U T P U T
 \*------------------------------------------------------------------*/

void intlib_print(INT *a)
{
	if (a->len)
	{
		INT m, ten, b;
		char *s, *ptr;
		int l = (int) (3 + 0.31*(float)a->len);
		if ((s = malloc(l)))
		{
			ptr = s + l - 1;
			*ptr-- = 0;
			if (!intlib_init(&m))
			{
				if (!intlib_init(&ten))
				{
					intlib_set(&ten, 10);
					if (!intlib_init(&b))
					{
						intlib_copy(a, &b);
						do
						{
							intlib_div_mod(&b, &ten, &b, &m);
							*ptr-- = '0' + m.ptr[0];
						}
						while(b.len);
						//printf(" %8s", &ptr[1]);
						printf("%s", &ptr[1]);
						intlib_destroy(&b);
					}
					intlib_destroy(&ten);
				}
				intlib_destroy(&m);
			}
			free(s);
		}
	}
	else
		printf("0");
	putchar('\n');
}

/*------------------------------------------------------------------*\
	F I Z Z  B U Z Z
 \*------------------------------------------------------------------*/

int main()
{
	INT i, zero, one, two, three, five, onehundred, res;
	int x;
	
	intlib_init(&i);
	intlib_init(&zero);
	intlib_init(&one);
	intlib_init(&two);
	intlib_init(&three);
	intlib_init(&five);
	intlib_init(&onehundred);
	intlib_init(&res);
	
	intlib_zero(&zero);
	intlib_set(&one, 1);
	intlib_set(&two, 2);
	intlib_set(&three, 3);
	intlib_set(&five, 5);
	
	intlib_copy(&one, &onehundred);
	intlib_mul(&onehundred, &two, &onehundred);
	intlib_mul(&onehundred, &five, &onehundred);
	intlib_mul(&onehundred, &onehundred, &onehundred);
	
	intlib_zero(&i);
	do
	{
		intlib_add(&i, &one, &i);
		intlib_mod(&i, &three, &res);
		if ((x = intlib_equal(&res, &zero)))
			printf("Fizz");
		intlib_mod(&i, &five, &res);
		x += intlib_equal(&res, &zero);
		if (intlib_equal(&res, &zero))
			printf("Buzz");
		if (!x)
			intlib_print(&i);
		else
			putchar('\n');
	}
	while(!intlib_equal(&i, &onehundred));
	
	intlib_destroy(&i);
	intlib_destroy(&zero);
	intlib_destroy(&one);
	intlib_destroy(&two);
	intlib_destroy(&three);
	intlib_destroy(&five);
	intlib_destroy(&onehundred);
	intlib_destroy(&res);
	return 0;
}