Beliebige dezimale Eingaben in die Basis 2^32 umwandeln

TobiasK

Guten Tag an alle,

ich bin es mal wieder. Immernoch das gleiche wundervolle Projekt für die Uni. Also, es geht sich hier um folgendes ^^

Wir haben zwei Eingaben, a und b, die entweder dezimal oder hexagesimal sind. Nun sollen wir die Standardrechenoperationen + - und * implementieren. Dazu werden unsere Eingangsdaten als Datentypen der Struktur BigInteger dargestellt:

typedef unsigned int uint32;
typedef struct {
uint32 n;
uint32* words;
} BigInt;

Sofern die Eingabe hexagesimal ist, läuft auch alles, da 8 Stellen im 16er-System eine Stelle im System zur Basis 2^32 sind. (Hier bitte nicht irgendwas von wegen Dual und 32Bit denken). Zur weiteren Erklärung:

2^32 = 4294967296

Demnach wird zum Beispiel die Zahl 123456789012345 (= 0x7048860DDF79)wie
folgt dargestellt:

word ...10 ...16 ...232
0     5     9     2249056121
1     4     7     28744
2     3     F     0
3     2     D     0
4     1     D     0
5     0     0     0
6     9     6     0
7     8     8     0
8     7     8     0
9     6     4     0
10    5     0     0
11    4     7     0
12    3     0     0
13    2     0     0
14    1     0     0

Eine größere Basis benötigt also weniger words um eine große Zahl zu speichern.
Und wie man sieht ist 2249056121 · 2³²0 + 28744 · 2³²1 = 123456789012345

Ich hoffe, dass damit die Grundzüge der Aufgabenstellung soweit klar sind.

Wenn ich meine Daten einlese, dann habe ich mir ein Array erzeugt, welches dynamisch immer die passende Länge besitzt. Wie gesagt, bei Hexa ist das kein Problem. ABER:
**
Wie mache ich das mit einer dezimalen Eingabe?**

volkard

TobiasK schrieb:

Demnach wird zum Beispiel die Zahl 123456789012345 (= 0x7048860DDF79)

log_2[h]32[/h](123456789012345)=1.4628

Kannste machen so: 123456789012345 ≈ 1234*10¹¹
log₁₀(123456789012345)≈=log₁₀(1234)+11=14.0914

14.0914*ln(10)/ln(2)=1.4628

Aber ich kann mir gar nicht vorstellen, daß man die Länge vorher schon braucht.

Wenns nicht supergenau sein muß, also eine Stelle mehr nicht weh tzut, die wäre nach der Rechnung ja auch hobsch erkennbar, weil da eine 0 drin steht, nimm einfach die dezimale Stellenzahl und plutimiziere mit ln(10)/ln(2)/32<0.10382 und runde großzügig auf.

SeppJ

Mach die Länge deines BigIntegers am besten variabel. Das brauchst du ohnehin, um + und * zu implementieren. Und wenn du dann + und * hast, kannst du damit Stellenwertsysteme umrechnen.

Merke: Versuche nicht für jede Aufgabenstellung komplett alles neu zu schreiben, sondern zerlege Probleme in einfache Teilschritte (hier + und und mach diese so universell wie möglich (hier: + und * passen variabel die Länge an). Dann kannst du alle höheren Aufgabenstellungen aus den kleinen Teilen ganz einfach zusammensetzen.
Außerdem hast du viel weniger, viel einfacher wartbaren Code. Und Optimierungen an den Teilschritten verbessern auch gleich alle höheren Algorithmen.

TobiasK

Also die Länge herausfinden ist kein Problem
Mein Problem ist folgendes:
Ich habe eine beliebige Eingabe zur Basis 10 und möchte das gerne zur Basis 4294967296(2^32) umwandeln. Sofern meine Eingabe zur Basis 16 war, kann ich einfach 8 Stellen der Eingabe als eine Stelle des BigInts interpretieren.

Es geht nur um die Umwandlung von der Basis 10 in die Basis 2^32

Edit: Es muss genau sein. Hoffe, jeder weiß jetzt, was mein Problem ist. Ich habe alleine eine Woche gebraucht um überhaupt mein Problem zu finden

SeppJ

TobiasK schrieb:

Immernoch das gleiche wundervolle Projekt für die Uni.

TobiasK schrieb:

Es geht nur um die Umwandlung von der Basis 10 in die Basis 2^32

Das ist doch wohl nicht dein Ernst, oder? Mathematik, siebte Klasse?

http://de.wikipedia.org/wiki/Stellenwertsystem

volkard

TobiasK schrieb:

Es geht nur um die Umwandlung von der Basis 10 in die Basis 2^32

Das machst Du ganz normal. Stör Dich einfach nicht am Typ BigInt. Ist nichts anderes als long oder double.

BigInt mbi(char const* str){
  BigInt x=0;
  while(str!='\0')
    x=x*10+BigInt(*str-'0');
  return x;
}

Upps, kein C++-Land hier. Also ohne Operatorüberladung und zum Jux this als Bezeichner nehmen.

void mbi(struct BigInt* this,char const* str){
  bigIntLoadZero(this);
  while(str!='\0'){
    bigIntMulInt(this,10);
    bigIntAddInt(this,*str-'0');
  }
}

TobiasK

SeppJ schrieb:

TobiasK schrieb:

Immernoch das gleiche wundervolle Projekt für die Uni.

TobiasK schrieb:

Es geht nur um die Umwandlung von der Basis 10 in die Basis 2^32

Das ist doch wohl nicht dein Ernst, oder? Mathematik, siebte Klasse?

http://de.wikipedia.org/wiki/Stellenwertsystem

Bitte lesen, dann schreiben.
Schau dir mal mul-giant-a.txt und mul-giant-b.txt an und nenne mir einen Datentyp in C, mit denen ich dei Eingaben nach Wikipedia verarbeiten kann. Ich habe doch nur maximal den Typ ull

http://www.cn.uni-duesseldorf.de/teaching/sose10/info2/tests.zip

volkard schrieb:

TobiasK schrieb:

Es geht nur um die Umwandlung von der Basis 10 in die Basis 2^32

Upps, kein C++-Land hier. Also ohne Operatorüberladung und zum Jux this als Bezeichner nehmen.
void mbi(struct BigInt* this,char const* str){
  bigIntLoadZero(this);
  while(str!='\0'){
    bigIntMulInt(this,10);
    bigIntAddInt(this,*str-'0');
  }
}

Das würde voraussetzen, dass die Multiplikation und Addition schon geschrieben ist, wenn ich dich richtig verstehe?
Boah Leute ist das nen Scheiß Stehe aber irgendwie immernoch auf dem Schlauch.
Sofern ich als Eingabe eine Textdatei habe, kann ich die doch mit fgetc nur zeichenweise einlesen. Und wie ich von dem Schritt zur Basis 2^32 komme, ist mir leider unklar. Ich weiß leider nicht, was deine Methoden bigIntMulInt und bigIntAddInt genau bewirken. Bzw. wie ich dann den BigInteger aufbaue, da ich doch jedes Wort einzeln anspreche (s.o. der struct).

Bitte nicht direkt auf mich drauf haun

volkard

TobiasK schrieb:

Das würde voraussetzen, dass die Multiplikation und Addition schon geschrieben ist, wenn ich dich richtig verstehe?

Ja! Das ist genau das, was SeppJ in seinem ersten Posting von Dir wollte.
Und genau dafür gibt's die Hex-Version, damit Du erstmal * und + testen kannst.

Sofern ich als Eingabe eine Textdatei habe, kann ich die doch mit fgetc nur zeichenweise
einlesen.

Ja. Ich hab halt einen string gelesen und dann den int mbi (steht für macheBigInteger) den string ausgelesen.

Und wie ich von dem Schritt zur Basis 2^32 komme, ist mir leider unklar.

Die Basis ist integralser Bestandteil der BigInteger-Typs.

Ich weiß leider nicht, was deine Methoden bigIntMulInt und bigIntAddInt genau bewirken. Bzw. wie ich dann den BigInteger aufbaue, da ich doch jedes Wort einzeln anspreche (s.o. der struct).

Ach, der ist nur

struct BigInt{
  unsigned int* ziffern;
  int ziffernAnzahl;
};

oder sowas. In den Funktionen greifst Du dann schon brav auf das ziffern-Array zu. Dadurch, daß die ziffernAnzahl auch da ist, können so Zahlen bei Bedarf wachsen (umkopieren in größeres Array und kleineres löschen oder realloc). Das wollte SeppJ auch haben.

Bitte nicht direkt auf mich drauf haun

Mal schauen, ob sich der Drang lange genug unterdrücken läßt.

Wutz

Neben dem schon genannten Artikel hier im C++ Forum bieten sich auch an:

https://mattmccutchen.net/bigint/index.html C++ / PD
http://gmplib.org/ C+Asm / GNU LGPL
https://www.openssl.org/docs/crypto/bn.html C / Free
http://msdn.microsoft.com/en-us/library/aa387677%28v=VS.85%29.aspx C / nur Windows
http://www.cryptopp.com/docs/ref/class_hex_encoder.html C++ / Free
http://www.codeproject.com/KB/cpp/largenumber.aspx C+++STL / MS-PL
http://shygypsy.com/tools/ C++ / Free
http://codepad.org/t84OokJn C / GPL

Insbesondere der 1. und der letzte sollten sich wohl leicht an deine Ansprüche anpassen lassen.

TobiasK

Morgen Jungs,

mittlerweile habe ich:

void mbi(struct BigInt* this,char const* str){
  bigIntLoadZero(this);
  while(str!='\0'){
    bigIntMulInt(this,10);
    bigIntAddInt(this,*str-'0');
  }
}

verstanden Ich müsste sogar nur aus meinem Array auslesen, da ich dort schon jede dezimale Ziffer passend drin habe. Umwandlungen sollten wie folgt aussehen (vorausgesetzt meine Methoden sind richtig :D)

DEZ <- BIGINT

int array[length];
j=0;
for ( i=0; i<length; i++) {
	array[i] = bi.words[j]%10;
	bi.words[j] /= 10;
	if ( bi.words[j]/10 == 0 ){
		array[i] = bi.words[j];
		j++;
	}
}
for ( i=length-1; i>=0; i--) {
	fprintf(data, "%i",array[i]);
}

BIGINT <- DEZ

bi.n = 1;
bi.words = realloc (bi.words, sizeof(uint32) ) ;
if (bi.words == NULL){
	printf ( "\tERROR: while allocating memory\n" );
	exit(1);
}
for ( i=length-1; i>=0; i--){
	bi.words = multiply (bi.words, 10);
	bi.words = add (bi.words, array[i]);
}

Es versteht sich von alleine das am höchsten Indiz im Array das MSB steht. Mal schauen, ob das alles rund laufen wird oder ob ich vor dem rof heulen muss

Wutz

TobiasK schrieb:

DEZ -> BIGINT

int array[length];
j=0;
for ( i=0; i<length; i++) {
	array[i] = bi.words[j]%10;
	bi.words[j] /= 10;
	if ( bi.words[j]/10 == 0 ){
		array[i] = bi.words[j];
		j++;
	}
}
for ( i=length-1; i>=0; i--) {
	fprintf(data, "%i",array[i]);
}

Du zerstörst hier den Inhalt der words.
Ich kenne die Definition von bi nicht, aber gelten muss: sizeof(int)==sizeof(bi.words[0]). Ein eventuelles Vorzeichen müsstest du auch noch irgendwie berücksichtigen? Statt %i würde ich auch %d nehmen.

TobiasK schrieb:

BIGINT -> DEZ

bi.words = realloc (bi.words, sizeof(uint32) ) ;

Das müsste wohl heissen:

bi.words = realloc (bi.words, length*sizeof(uint32) ) ;

bzw. robuster:

bi.words = realloc (bi.words, length*sizeof*bi.words ) ;

TobiasK

Vorzeichen muss nicht beachtet werden. Des weiteren gilt:

typedef unsigned int uint32;
typedef struct {
    uint32 n;
    uint32* words;
} BigInt;

Daraus folgt:

Ich kenne die Definition von bi nicht, aber gelten muss: sizeof(uint32)==sizeof(bi.words[0])

bzw. wir können auch direkt sizeof(4) schreiben.

Frage:
Wieso den Platzhalter %d und nicht %i? Habe kurz gegoogelt und finde nichts. Galileo Computing gibt auch nur Beide an, ohne Erklärungen $:\$