NWD BigInt, problem z algorytmem/implementacją

0

Witam!

Wiem, że kod długi, ale testowałem wszystkie operatory i wydaje mi się, ze dzialają poprawnie, więc pozostaje kwestia funkcji NWD. Nie mogę poradzić sobie ze znalezieniem błędu.

#include <iostream>
#include <cstring>

#define si short int
#define ui unsigned int
#define FOR(a, b, c) for(ui b=a; b<c; b++)
#define MAX(a, b) (a>b?a:b)
#define max_number_of_digits 2048
using namespace std;
struct BigNum
{
	bool sign;
	ui lenght;
	si* digits;
	BigNum ()
	{
		digits = new si[0];
		lenght=0;
		sign=0;
	}
	BigNum (si s, ui l, si* d)
	{
		digits = new si[max_number_of_digits];
		lenght = l;
		sign = s;
		memmove(digits, d, max_number_of_digits*sizeof(si));
	}
	BigNum (si s, ui l, char* d)
	{
		digits = new si[max_number_of_digits];
		lenght = l;
		sign = s;
		FOR(0, i, l)
			digits[max_number_of_digits-(l-i+1)]=(si)(d[i]-'0');
	}
	BigNum (si s, ui l, string & d)
	{
		digits = new si[max_number_of_digits];
		lenght = l;
		sign = s;
		FOR(1, i, l+1)
			digits[max_number_of_digits-(i)]=(si)(d[l-(i)]-'0');
	}
};
ostream & operator << (ostream & out, const BigNum & s)         
{
	for(ui i=s.lenght; i>0; i--)
		out << s.digits[max_number_of_digits-i];
	return out;
}
istream & operator >> (istream & in, BigNum & s)
{
	string tmp;
	in >> tmp;
	s=BigNum(0, tmp.size(), tmp);
        return in;
}
BigNum operator+ (BigNum & a, BigNum & b)
{
	si* tmp=new si[max_number_of_digits];
	FOR(0, i, 2048) tmp[i]=0;
	for(ui i=max_number_of_digits-1; i>max_number_of_digits-(MAX(a.lenght, b.lenght)+1); i--)
	{
		tmp[i]+=a.digits[i]+b.digits[i];
		if(tmp[i]>=10)
		{
			tmp[i-1]=tmp[i]/10;
			tmp[i]%=10;
		}
	}
	return BigNum(a.sign*b.sign, MAX(a.lenght, b.lenght)+(tmp[max_number_of_digits-(MAX(a.lenght, b.lenght))]==0?1:0), tmp);
}
BigNum operator- (BigNum & a, BigNum & b)
{
	si* tmp=new si[max_number_of_digits];
	for(ui i=max_number_of_digits-1; i>max_number_of_digits-(MAX(a.lenght, b.lenght)+1); i--)
	{
		tmp[i]+=a.digits[i]-b.digits[i];
		if(tmp[i]<0)
		{
			tmp[i-1]--;
			tmp[i]+=10;
		}
	}
	si num=0;
	for(int i=max_number_of_digits-(MAX(a.lenght, b.lenght)+1); i<max_number_of_digits; i++)
		if(tmp[i]!=0)
		{
			num=max_number_of_digits-i;
			break;
		}
	num==0?num=1:0;
	return BigNum(a.sign*b.sign, num, tmp);
}
bool operator < (BigNum & a, BigNum & b)
{
	if(a.lenght!=b.lenght)
		return a.lenght<b.lenght;
	for(int i=max_number_of_digits-a.lenght-1; i<max_number_of_digits; i++)
		if(a.digits[i]!=b.digits[i])
			return a.digits[i]<b.digits[i];
	return false;
}
bool operator == (BigNum & a, BigNum & b)
{
	if(a.lenght!=b.lenght)
		return false;
	for(int i=max_number_of_digits-a.lenght-1; i<max_number_of_digits; i++)
		if(a.digits[i]!=b.digits[i])
			return false;
	return true;
}
bool operator != (BigNum & a, BigNum & b)
{
	return !(a==b);
}
bool operator<= (BigNum & a, BigNum & b)
{
	if(a.lenght!=b.lenght)
		return a.lenght<=b.lenght;
	for(int i=max_number_of_digits-a.lenght-1; i<max_number_of_digits; i++)
		if(a.digits[i]<b.digits[i])
			return a.digits[i]<b.digits[i];
	return false;
}
bool operator> (BigNum & a, BigNum & b)
{
	return b<a;
}
bool operator>= (BigNum & a, BigNum & b)
{
	return b<=a;
}
BigNum operator* (BigNum & a, int b)
{
	if (b==2)
	{
		si* tmp=new si[max_number_of_digits];
		FOR(0, i, 2048) tmp[i]=0;
		for(ui i=max_number_of_digits-1; i>max_number_of_digits-a.lenght-1; i--)
		{
			tmp[i]+=a.digits[i]*2;
			if(tmp[i]>=10)
			{
				tmp[i-1]=tmp[i]/10;
				tmp[i]%=10;
			}
		}
		return BigNum(a.sign, a.lenght+(tmp[max_number_of_digits-(a.lenght)]==0?1:0), tmp);
	}
	return BigNum();
}
BigNum operator/ (BigNum & a, int b)
{
	si* tmp=new si[max_number_of_digits];
	for(ui i=max_number_of_digits-(a.lenght); i<max_number_of_digits; i++)
	{
		tmp[i]+=a.digits[i];
		if(tmp[i]%2==1)
			tmp[i+1]+=10;
		tmp[i]/=2;
	}
	si num;
	for(int i=max_number_of_digits-(a.lenght+1); i<max_number_of_digits; i++)
		if(tmp[i]!=0)
		{
			num=max_number_of_digits-i;
			break;
		}
	num==0?num=1:0;
	return BigNum(a.sign, num, tmp);
}
int operator% (BigNum & a, int b)
{
	if(b==2)
	{
		return a.digits[max_number_of_digits-1]%2;
	}
	return 0;
}
bool operator== (BigNum & a, char b)
{
	if(a.digits[max_number_of_digits-1]+'0'==b && a.lenght==1)
		return true;
	return false;
}
BigNum NWD(BigNum a, BigNum b)
{
	si* tmp=new si[max_number_of_digits];
	tmp[max_number_of_digits-1]=1;
	BigNum zero(0, 1, tmp);
	ui dwojki=0;
	//cout << "dupa" <<endl;
	if(a<b) swap(a, b);
	while (!(b=='0') && !(b=='1'))
	{
		
		if(a%2==0 && b%2==0)
		{
			dwojki++;
			a=a/2;
			b=b/2;
			cout << "(a%2==0 && b%2==0): " << a << ", " << b <<endl;
		}
		else if(a%2==1 && b%2==0)
		{
			b=b/2;
			cout << "(a%2==1 && b%2==0): " << a << ", " << b <<endl;
		}
		else if(a%2==0 && b%2==1)
		{
			a=a/2;
			cout << "(a%2==1 && b%2==0): " << a << ", " << b <<endl;
		}
		else if(a%2==1 && b%2==1)
		{
			a=a-b;
			cout << "(a%2==1 && b%2==1): " << a << ", " << b <<endl;
		}
		//if(b==zero || a==zero) break;
		if(a<b) swap(a, b);
	}
	while (dwojki--)
	{
		a=a*2;
	}	
	return a;
}
int main ()
{
	BigNum k, l;
	int n;
	cin >> n;
	while (n--)
	{
		cin >> k >> l;
		//cout << endl << "a: " << a << ", b: " << b << endl;
		//a=a+a;
		/*
		cout << "a-b= "<< a-b << endl;
		cout << "a+b= " << a+b << endl;
		cout << "a<b? " << ((a<b)?"TAK":"NIE") << endl;
		cout << "a<=b? " << ((a<=b)?"TAK":"NIE") << endl;
		cout << "a==b? " << ((a==b)?"TAK":"NIE") << endl;
		cout << "a*2= " << a*2 << endl;
		cout << "b*2= " << (b*2) << endl;
		cout << "a%2= " << (a%2) << endl;
		cout << "b%2= " << (b%2) << endl;*/
		cout << NWD (l, k) << endl;
	}
		
}
0 
int operator% (BigNum & a, int b)
{
        if(b==2)
        {
                return a.digits[max_number_of_digits-1]%2;
        }
        return 0;
}

mistrz
2. Makro FOR jest bardzo bardzo bardzo do d**y
3. brak możliwości mnożenia i dzielenia dwóch bignum
4.

bool operator== (BigNum & a, char b)
{
        if(a.digits[max_number_of_digits-1]+'0'==b && a.lenght==1)
                return true;
        return false;
}

to też jest zajebiste

więcej nie wypatrzyłem, bo nie chciałem się w to zagłębiać

0

Widzę, że nie chciało ci się w to zagłębiać, bo te operatory służą tylko i wyłącznie wyliczeniu tego NWD.

  1. Potrzebne mi tylko modulo 2, reszta nie.
  2. Makra używam tylko do zerowania, reszta jest napisana bez niego.
  3. Po co mi to do NWD?
  4. Masz rację, działa.

Jedyne w czym masz rację to to, że się nie wgłębiłeś.

0
merlinnot napisał(a):

Widzę, że nie chciało ci się w to zagłębiać, bo te operatory służą tylko i wyłącznie wyliczeniu tego NWD.
no to życzę powodzenia z takim operatorem %

merlinnot napisał(a):
  1. Potrzebne mi tylko modulo 2, reszta nie.
    Czemu? Gdzie to napisałeś? Wiesz w ogóle jak się liczy NWD?
merlinnot napisał(a):
  1. Makra używam tylko do zerowania, reszta jest napisana bez niego.
    Makra to samo zło, które powinni pisać jedynie ci co już umieją programować w C
merlinnot napisał(a):
  1. Po co mi to do NWD?
    Wiesz w ogóle jak się liczy NWD?
merlinnot napisał(a):
  1. Masz rację, działa.
    Czy na drugie masz Sheldon i nie możesz załapać ironii?
merlinnot napisał(a):

Jedyne w czym masz rację to to, że się nie wgłębiłeś.
Brak mi słów. Tu nie ma w co się zagłębiać, chyba że ktoś jest szambonurkiem. Zadałeś pytanie dostałeś poważną krytykę, a ty dalej się upierasz, że masz dobrze. Aż dziw bierze, że jesteś zarejestrowany na forum od roku.

0

Nie będę przecież liczył standardowym algorytmem NWD, bo te operacje byłyby niezwykle wolne...

Algorytm w zamyśle miał opierać się na tym:

NWD(2a, 2b)=2NWD(a, b)
NWD(2a+1, 2b)=NWD(2a+1, b)
NWD(2a+1, 2b+1)=NWD(2a+1-2b-1, 2b+1)

Dlatego zaimplementowałem operatory w ten sposób.

0

#trzeba było napisać to na samym początku
#tylko dzieciuchy, szukają byle okazji do przeciążania operatorów, a za wymyślanie nowej operacji modulo powinieneś zostać powieszony na najbliższej gałęzi. To samo dotyczy się tego makra FOR
#błąd masz w operatorze mnożenia, tu masz dowód, że to tam jest problem

1 użytkowników online, w tym zalogowanych: 0, gości: 1