ggT mit Zahlen > int

Loomis

Hallo!
Erst mal möchte ich euch alle begrüßen, denn dies ist mein erster Post hier im Forum.

Nun zu meinem Problem:
Ich sollte die ggT-Funktion programmieren. Hab ich auch gemacht:

#include <iostream>
using namespace std;

int ggT(int, int);

int main(void)
{
	int a, b, ggTeiler;

	cout << "Berechnung des groessten gemeinsamen Teilers" << endl << endl;
	cout << "Geben sie die erste Zahl ein:" << endl;
	cin >> a;
	cout << "Geben sie die zweite Zahl ein:" << endl;
	cin >> b;
	ggTeiler = ggT(a, b);
	cout << "Der groesste gemeinsame Teiler von " << a << " und " << b << " ist " << ggTeiler << endl;
	return 0;
}

int ggT(int a, int b)
{
	if(a%b != 0)
		return ggT(b, a%b);
	else if(a%b == 0)
		return b;
}

Funktioniert auch so weit, allerdings soll ich in einer Übungsaufgabe die Funktion mit sehr großen Zahlen testen (>197 Milliarden).
Das geht mit integer als Datentyp natürlich nicht, selbst unsigned int wäre zu klein.
Und mit double funktioniert wiederum % (Modulo) nicht.
Was soll ich tun?

Windalf

Was soll ich tun?

Selbstmord ist ne Lösung

nö du kannst ja ganz normal teilen und multiplizierst dann den die nachkommastellen mit dem divisor... wenns keine rundungsfehler gibt hast du so auch den rest...

Loomis

Na ja, Rundungsfehler gibts ja so gut wie immer.
Das ist wohl auch jetzt das Problem, oder entdeckt jemand was anderes:

#include <math.h>
#include <iostream>
using namespace std;

double ggT(double, double);

int main(void)
{
	double a, b, ggTeiler;

	cout << "Berechnung des groessten gemeinsamen Teilers" << endl << endl;
	cout << "Geben sie die erste Zahl ein:" << endl;
	cin >> a;
	cout << "Geben sie die zweite Zahl ein:" << endl;
	cin >> b;
	ggTeiler = ggT(a, b);
	cout << "Der groesste gemeinsame Teiler von " << a << " und " << b << " ist " << ggTeiler << endl;
	return 0;
}

double ggT(double a, double b)
{
	double temp, rest;
	temp = a/b;
	temp = (temp-floor(temp));
	rest = b * temp;
	if(rest != 0)
		return ggT(b, rest);
	else if(rest == 0)
		return b;
}

EDIT:
Wobei...
Geht das mit der floor() so überhaupt? Ich meine, wie ist die Reihenfolge?
1. floor(temp) sprich aus z.B. 5.3 wird 5
2. temp -temp sprich 5 - 5, da ja schon floor()
3. Zuweisung

???

Ein neuer Ansatz wäre:

double ggT(double a, double b)
{
	double temp, temp2, temp3, rest;
	temp = a/b;
	temp2 = floor(temp);
	temp3 = (temp-temp2);
	rest = b * temp3;
	if(rest != 0)
		return ggT(b, rest);
	else if(rest == 0)
		return b;
}

Aber die Rundungsfehler bestehen natürlich trotzdem.

groovemaster

Eine Möglichkeit für das Problem wären 64 bit Integer. Seit C99 gibts long long, ist aber kein C++ Standard. Jedoch haben die meisten aktuellen Compiler einen entsprechenden Datentyp parat. So gibts für den MSC zB __int64.

Loomis

Ah, geil so funktionierts. Vielen Dank.

Der Vollständigkeit halber hier noch der Sourcecode, wie es endgültig aussieht:

#include <iostream>
using namespace std;

__int64 ggT(__int64, __int64);

int main(void)
{
    __int64 a, b, ggTeiler;

    cout << "Berechnung des groessten gemeinsamen Teilers" << endl << endl;
    cout << "Geben sie die erste Zahl ein:" << endl;
    cin >> a;
    cout << "Geben sie die zweite Zahl ein:" << endl;
    cin >> b;
    ggTeiler = ggT(a, b);
    cout << "Der groesste gemeinsame Teiler von " << a << " und " << b << " ist " << ggTeiler << endl;
    return 0;
}

__int64 ggT(__int64 a, __int64 b)
{
    if(a%b != 0)
        return ggT(b, a%b);
    else if(a%b == 0)
        return b;
}

ggT mit Zahlen &gt; int

ggT mit Zahlen > int