3. Frage zu Algorithmus zum Multiplizieren großer Zahlen

Frage zu Algorithmus zum Multiplizieren großer Zahlen

  • V

    Kannst Du bestimmen, wieviel für sagen wie mal length=1024 und kara_threshold=64 nötig ist?

    0
  • ?

    Ich habs jetzt so gelöst (scheint zu funktionieren):

    uint_t tmp (length);
uint_t size(length);
while(tmp>Grenze)
{
    tmp/=2; //simuliert Rekursion :D
    size += tmp;
}
nrs* buffer((nrs*)malloc(sizeof(nrs)*size*3)); //*3 weil 3 mal die Funktion in der Funktion aufgerufen wird.
    0
  • V

    GroßeZahlen schrieb:

    uint_t tmp (length);
uint_t size(length);
while(tmp>Grenze)
{
    tmp/=2; //simuliert Rekursion :D
    size += tmp;
}

    Die Schleife macht also
    size = length/2 + length/4 + length/8 + ... + 2Grenze
    ?
    Das wäre wenn ich recht rate gleich zu
    size = length - 2    Grenze

    GroßeZahlen schrieb:

    nrs* buffer((nrs*)malloc(sizeof(nrs)*size*3)); //*3 weil 3 mal die Funktion in der Funktion aufgerufen wird.

    Jo, klingt schlau.

    0
  • ?

    Ich muss diesen Thread nochmal aus der Versenkung holen. Es geht um den "Standard" Multiplikationsalgorithmus (siehe unten). Der verhält sich bei mir sehr komisch. Nochmal zum Konzept: Das Array number (unsigned int number[]) ist Member der Klasse Zahl und repräsentiert eine Zahl. Wenn ich zwei solcher "Zahlen" multiplizieren will, funktioniert das NUR, wenn die Anzahl der Elemente der arrays (array_size) eine Potenz von zwei ist.

    //number und a.number sind gleich lang, result ist doppelt so lang
void mult_school(const Zahl& a, Zahl& result) const
{
	std::memset(result.number, 0, array_size*2*sizeof(unsigned int)); //result auf 0 setzen

	for(unsigned int i=0;i!=array_size;++i)
	{
		unsigned int carry = 0;

		for(unsigned int j=0;j!=array_size;++j)
		{
			unsigned int index = i+j; //position, ab der "result" bearbeitet wird

			//-----------------------------------------
			// Errechne number[i]*a.number[j]
			// Splitte das Ergebnis in part1 und part2
			//-----------------------------------------
			unsigned int ahi = number[i] >> 16;
			unsigned int alo = number[i] & 0xFFFF; 
			unsigned int bhi = a.number[j] >> 16;
			unsigned int blo = a.number[j] & 0xFFFF;

			unsigned int part1 = alo * blo;
			unsigned int part2 = ahi * bhi;

			unsigned int middle1 = ahi * blo;
			unsigned int tmp = alo * bhi;
			middle1 += tmp;
			unsigned int middle2 = middle1 < tmp;
			middle2 <<= 16;
			middle2 |= (middle1>>16);
			middle1 <<= 16;

			part1 += middle1;
			unsigned int cyt = part1 < middle1;
			part2 += cyt;
			part2 += middle2;
			/*
			unsigned long long eins = (unsigned long long)number[i] * a.number[j];
			unsigned long long zwei = part1 + ((unsigned long long)part2<<32);
			if(eins!=zwei) std::cerr<<"FEHLER"<<std::endl;
			*/

			//-----------------------------------------
			// Verrechne part1 und part2 mit result
			//-----------------------------------------
			result.number[index] += part1;
			unsigned int cy1 = result.number[index] < part1; //overflow bei addition

			result.number[index+1]+=cy1; //overflow vom Schritt hiervor mit dem nächsten element verrechnen
			unsigned int cy2 = result.number[index+1] < cy1;

			result.number[index+1]+=part2; //nächstes element mir part2 verrechnen
			unsigned int cy3 = result.number[index+1] < part2;

			result.number[index+1]+=carry; //nächstes element mit übertrag vom letzten schleifendurchlauf verrechnen

			carry = result.number[index+1] < carry; //übertrag für nächsten schleifendurchlauf festsetzen 
			carry += (cy3|cy2);
		}
	}
}

    Im Prinzip multipliziere ich das ite Element von this mit dem jten Element von a und speichere das Ergebnis in part1 und part2. Das Funktioniert immer und ist auch immer richtig. Anschließend verrechne ich das mit result.
    Der Algorithmus an sich scheint richtig zu sein, da alle Arraylängen, die eine Potenz von 2 sind, das richtige Ergebnis produzieren. Wenn die Arraylänge von this und a keine Potenz von 2 ist, erhalte ich solche Fehler:

    Array Size = 3;
Aufgabe:      45675872532487774540918482702 * 62469334509438103030645792939
Richtige Lösung: 2853341360242434495933484427440446062475097909763545241178
Erzeuge Lösung:  2853341360242434495933484427440446062457389175715234054144

    Auffällig ist, dass die oberen paar bits immer richtig sind, alle weiteren Bits aber auf 0 stehen (nochmal: mit einer Arraysize, die eine Potenz von 2 ist, ist das Ergebnis immer richtig)

    Zur Aufgabe oben:
Richtige Lösung: 11101000101111001000110000101111110111111000110101010001101010111001000001011101011111101110100101000001100011110101011011111011111010111000010000011111100101011000011011101000001011001011010
Erzeugte Lösung: 1110100010111100100011000010111111011111100011010101000110101011100100000101110101111110111010010100000110001111010101101111101[b]0000000000000000000000000000000000000000000000000000000000000000[/b]

    Viel extremer ist es bei größeren Zahlen. Dann sind die oberen hundert bits richtig gesetzt und dann kommen 500 nullen.

    Kann sich jemand vorstellen, woran sowas liegen kann? Provoziere ich irgendwo undefiniertes Verhalten?

    0
Anmelden zum Antworten