//**************************************************************************
// Projekt:
// Rechnen mit groáen Ganzzahlen
//**************************************************************************
// Modul:
//  mpi.h    Headerdatei zur Programmbibliothek
// >mpi.cpp  Programmbibliothek
//  main.cpp beispiel Programm, das die Programmbibliothek verwendet
//**************************************************************************
// Geschichte:
// V1.0		08.12.1997	erste Version
// V1.1		20.12.1997      umgestellt: malloc -> new; printf -> cout
// V1.2		06.01.1998	einlesen langer Zahlen aus text Datei
//**************************************************************************
// Erstellt von:
// Thorsten Milianowitsch			08.12.1997
//**************************************************************************
// Beschreibung:
// Hier sind die Funktionen zum rechnen mit langen Zahlen implementiert.
// F�r ein Beispiel wie man sie verwendet, bitte main.ccp anschauen.
//**************************************************************************
// Einschr„nkung:
// 1.	Es k”nne Zahlen mit bis zu 16000 aus Dateien eingelesen werden.
// 2.   Die gr”sste getestete Zahl hatte 17000 Stellen.
//      Das Programm l„sst 32000 Stellen zu. Die gr”sste Zahl h„ngt vom
//      freien Speicher, und dem verwendetem Speichermodell des Compilers ab.
// 3.   Bei multiplikation sollte erster Parameter die kleinere Zahl
//      enthalten, da hierbei weniger Speicher ben”tigt wird.
// 4.   F�hrende Nullen werden beim Ergebnis nicht entfernt.
// 5.   Die geschwindigkeit h„ngt stark vom Speichermodell des Compilers ab.
//      Tiny, Small, Medium sind schnell, nicht so grosse Zahlen.
//      Compact, Large, Huge sind langsam, groessere Zahlen.
//**************************************************************************
// Bekannte Fehler:
// noch keine ;)
//**************************************************************************

//**************************************************************************
// Header Dateien
//**************************************************************************
#include <iostream.h>
//#include <stdlib.h> // f�r exit();
#include <fcntl.h>
#include <io.h>
#include "mpi.h"

// Makro max() gibt es nur in C nicht in C++
#ifdef __cplusplus
  int max (int value1, int value2);
  int max(int value1, int value2)
  {
     return ( (value1 > value2) ? value1 : value2);
  }
#endif

//**************************************************************************
// Implementation der Funktionen
//**************************************************************************

//**************************************************************************
// Speicher fuer eine lange Zahl reservieren
//**************************************************************************
tlang mpi_getmem(signed int laenge) {
  tlang tmp;
  if (laenge>=0) {
    tmp.lang=laenge;
//    if ((tmp.zahl=(tzahl *)malloc((tmp.lang+1)*sizeof(tzahl)))==NULL) {
// Speicher reservieren
    if ((tmp.zahl=new tzahl [tmp.lang])==NULL) {
      tmp.lang=-1;
      cerr << "\nNicht Genug Speicher!\n\n";
    }
  }
  else {
    tmp.lang=-1;
    tmp.zahl=NULL;
    cerr << "\nKann keinen negativen Speicher reservieren!\n\n";
  }
  return tmp;
}

//**************************************************************************
// Speicher einer langen Zahl freigeben
//**************************************************************************
tlang mpi_freemem(tlang tmp) {
  if ((tmp.lang>=0)&&(tmp.zahl!=NULL)) {
    delete [] tmp.zahl; //    free(tmp.zahl);
    tmp.zahl=NULL;
    tmp.lang=-1;
  }
  else {
    tmp.lang=-1;
    tmp.zahl=NULL;
    cerr << "\nKonnte Speicher nicht freigeben!\n\n";
  }
  return tmp;
}

//**************************************************************************
// Eine lange Zahl aus einer text Datei lesen
//**************************************************************************
tlang mpi_lese(const char * name) {
  tlang tmp,tmp2;
  int i,handle,bytes;
// Datei zum lesen ”ffnen
  if ((handle=open(name,O_RDONLY | O_TEXT))==-1) {
    cerr << "\nFehler beim ”ffnen der Datei\n\n";
    tmp.zahl=NULL;
    tmp.lang=-1;
    return tmp;
  }
// Puffer mit 16000 Stellen erzeugen
  tmp=mpi_getmem(16000);
// Aus Datei in Puffer tmp lesen
  if ((bytes=read(handle,tmp.zahl,16000))==-1) {
    cerr << "\nFehler beim lesen der Datei\n\n";
    tmp.zahl=NULL;
    tmp.lang=-1;
    return tmp;
  }
// Tats„chliche l„nge ermitteln und restlichen Speicher freigeben
  bytes-=1;
  tmp2=mpi_getmem(bytes);
// Zahl konvertieren
  for (i=0; i<bytes; i++) {
    tmp2.zahl[i]=tmp.zahl[bytes-i-1]-48;
  }
  tmp=mpi_freemem(tmp);
// Datei schliessen
  close(handle);
  return tmp2;
}

//************************************************
// Eine lange Zahl in eine text Datei schreiben
//************************************************
void mpi_schreibe(const char * name, tlang tmp) {
  tlang tmp2;
  int i,handle,bytes;
  tmp2=mpi_getmem(tmp.lang);
// Zahl konvertieren
  for (i=0; i<tmp.lang; i++) {
    tmp2.zahl[i]=tmp.zahl[tmp.lang-i-1]+48;
  }
// Datei zum schreiben ”ffnen
  if ((handle=open(name,O_RDWR | O_TRUNC | O_CREAT | O_TEXT))==-1) {
    cerr << "\nFehler beim ”ffnen der Datei\n\n";
    return;
  }
// Zahl in Datei schreiben
  if ((bytes=write(handle,tmp2.zahl,tmp2.lang))==-1) {
    cerr << "\nFehler beim schreiben der Datei\n\n";
    tmp2=mpi_freemem(tmp2);
    return;
  }
  tmp2=mpi_freemem(tmp2);
// Datei schliessen
  close(handle);
}

//************************************************
// Zwei lange Zahlen addieren
//************************************************
tlang mpi_addiere(tlang u, tlang v) {
  int i=0,j=0,k=0;
  tlang tmp;
  signed short int carry=0;
  signed short int uu,vv;
// Reserviere Speicher f�r Ergebnis (eine Stelle l„nger als l„ngste Zahl)
  tmp=mpi_getmem(max(u.lang,v.lang)+1);
// beginne mit niedrigster stelle
  for (k=0;k<tmp.lang;k++) {
// merke aktuelle Stelle bzw. 0 falls Zahl zu klein
    if (i<u.lang) {
      uu=u.zahl[i];
      i++;
    }
    else uu=0;
// merke aktuelle Stelle bzw. 0 falls Zahl zu klein
    if (j<v.lang) {
      vv=v.zahl[j];
      j++;
    }
    else vv=0;
// addiere Stellen und šbertrag
    tmp.zahl[k]=uu+vv+carry;
// Ergebnis Stelle pr�fen und šbertrag evtl. setzen
    if (tmp.zahl[k]>9) {
      carry=1;
      tmp.zahl[k]-=10;
    }
    else carry=0;
  }
  return tmp;
}

//************************************************
// Zwei lange Zahlen addieren
// UND Speicher von erster Zahl freimachen
// UND zweite Zahl *10^n
// wird fuer multiplikation benoetigt
//************************************************
tlang mpi_addiere_free(tlang u, tlang v, int n) {
  int i=0,j=0,k=0;
  tlang tmp;
  signed short int carry=0;
  signed short int uu,vv;
// Addition fast identisch zu normaler Addition
  tmp=mpi_getmem(max(u.lang,v.lang+n)+1);
  for (k=0;k<tmp.lang;k++) {
    if (i<u.lang) {
      uu=u.zahl[i];
      i++;
    }
    else uu=0;
// Stellen der zweiten Zahl erst ber�cksichtigen, wenn aktuell berechnete
// Stelle gr”sser oder gleich n ist.
    if (k<n) vv=0;
    else {
// aktuelle Stelle der zweiten Zahl auf 0 setzen, sobald n gleich der
// gerade berechneten Stelle. Danach Stelle immer um eins erh”hen.
      if (k==n) j=0;
      if (j<v.lang) {
	vv=v.zahl[j];
	j++;
      }
      else vv=0;
    }
    tmp.zahl[k]=uu+vv+carry;
    if (tmp.zahl[k]>9) {
      carry=1;
      tmp.zahl[k]-=10;
    }
    else carry=0;
  }
  u=mpi_freemem(u);
  return tmp;
}

//************************************************
// Zwei lange Zahlen subtrahieren
// c=mpi_subtrahiere(u,v); // c = u - v;
// mit u>=v!
//************************************************
tlang mpi_subtrahiere(tlang u, tlang v) {
  int i=0,j=0,k=0;
  tlang tmp;
  signed short int carry=0;
  signed short int uu,vv;
// test ob laenge u < laenge v
  if (u.lang<v.lang) tmp.lang=-1;
// laenge u >= laenge v
  else tmp=mpi_getmem(max(u.lang,v.lang));
  if (tmp.lang>=0) {
// bei laenge u = lanege v erfolgt test, ob
// u > v ist bei der berechnung (dann speicher frei machen!)
    for (k=0;k<tmp.lang;k++) {
// Merke Stelle oder 0, falls Zahl k�rzer als aktuelle Stelle
      if (i<u.lang) {
	uu=u.zahl[i];
	i++;
      }
      else uu=0;
// Merke Stelle oder 0, falls Zahl k�rzer als aktuelle Stelle
      if (j<v.lang) {
	vv=v.zahl[j];
	j++;
      }
      else vv=0;
// zu der zu subtrahierenden Zahl den šbertrag addieren
      vv+=carry;
// ist die zu subtrahierende Zahl gr”sser, wird šbertrag gesetzt.
// (borgen von der n„chst h”heren Stelle)
      if (vv>uu) {
	carry=1;
	uu+=10;
      }
      else carry=0;
      tmp.zahl[k]=uu-vv;
    }
// falls carry nach letztem schritt
// war v groesser als u !!
    if (carry==1) tmp=mpi_freemem(tmp);
  }
  else tmp.zahl=NULL;
  return tmp;
}

//************************************************
// Eine lange Zahl mit einer stelle multiplizieren
//************************************************
tlang mpi_mulkurz(tlang u, tzahl n) {
  int i=0;
  tlang tmp;
  signed short int carry=0;
  tmp=mpi_getmem(u.lang+1);
// wiederhole f�r jede Stelle, mit der niedrigsten Stelle beginnend
  for (i=0; i<u.lang; i++) {
   tmp.zahl[i]=u.zahl[i]*n+carry;
   carry=tmp.zahl[i]/10;
   tmp.zahl[i]%=10;
  }
  tmp.zahl[i]=carry;
  return tmp;
}

//************************************************
// Zwei lange Zahlen multiplizieren
// M”glichst u k�rzer als v (geringeger Speicherbedarf)
//************************************************
tlang mpi_multipliziere(tlang u, tlang v) {
  int i=0,j=0;
  tlang tmp;
  tlang mul[10];
  signed short int uu,vv;
// vorberechnung der multiplikatioonen
// u jeweils mit 0 bis 9 multiplizieren, damit diese
// multiplikation nicht nachher mehrfach gemacht werden muss
// dazu wird u zehn mal im Speicher abgelegt!
  for (i=0;i<10;i++) {
   mul[i]=mpi_mulkurz(u,i);
  }
// addiere die vorberechneten zahlen stellenrichtig
  tmp=mpi_getmem(0);
  tmp.zahl[0]=0;
  for (j=0; j<v.lang; j++) {
    tmp=mpi_addiere_free(tmp,mul[v.zahl[j]],j);
  }
// gebe den Speicher der vorberechneten Zahlen wieder frei
  for (i=0;i<10;i++) {
   mul[i]=mpi_freemem(mul[i]);
  }
  return tmp;
}