home *** CD-ROM | disk | FTP | other *** search
/ back2roots/padua / padua.7z / padua / misc / bignum.lzh / BIGNUM.C < prev    next >
C/C++ Source or Header  |  1990-10-01  |  6KB  |  257 lines
  1. /* bignum.c -- following an idea from c't-magazine 9/88
  2.    Compiler: Aztec C3.6a for Amiga using "make -f bignum.make" */
  3.  
  4. #include <stdio.h>
  5. #define FALSCH 0
  6. #define WAHR !FALSCH
  7.  
  8. #define USHORT unsigned short
  9. #define ULONG  unsigned long
  10.  
  11. USHORT *feld1, *feld2, *ergeb;
  12. USHORT potenz;
  13.  
  14. main(argc,argv)
  15. int argc;
  16. char *argv[];
  17. {
  18.   USHORT Groesse, Stellen;
  19.   extern USHORT *malloc();
  20.  
  21.   if (argc<=1) {
  22.     printf("gewⁿnschte Anzahl Stellen: ");
  23.     scanf("%d",&Stellen);
  24.   }
  25.   else {
  26.     sscanf(argv[1],"%d",&Stellen);
  27.   };
  28.   Groesse=Stellen/4+1;
  29.   if ((feld1=malloc(Groesse*sizeof(USHORT)))==0L) {
  30.     printf("Es ist zu wenig Speicher frei !\n");
  31.     exit(30);
  32.   };
  33.   if ((feld2=malloc(Groesse*sizeof(USHORT)))==0L) {
  34.     printf("Es ist zu wenig Speicher frei !\n");
  35.     exit(30);
  36.   };
  37.   if ((ergeb=malloc(Groesse*sizeof(USHORT)))==0L) {
  38.     printf("Es ist zu wenig Speicher frei !\n");
  39.     exit(30);
  40.   };
  41.  
  42.   euler(feld1, ergeb, Groesse);
  43.   printf("\n");
  44.   pi(feld1, feld2, ergeb, Groesse);
  45.   printf("\n");
  46.   /* belegten Speicher wieder freigeben */
  47.   free(feld1);
  48.   free(feld2);
  49.   free(ergeb);
  50.   exit(0);
  51. }
  52.  
  53. /* Berechnung der Eulerschen Zahl e = 1 + 1/1! + 1/2! + 1/3! + ... + 1/n! */
  54.  
  55. euler(feld1,ergeb,Groesse)
  56. USHORT feld1[], ergeb[];
  57. register USHORT Groesse;
  58. {
  59.   int nicht_fertig;
  60.   register USHORT i;
  61.   register USHORT fakulz; /* FakultΣtszΣhler (n) */
  62.  
  63.   /* L÷schen der Vektoren */
  64.   for (i=0; i<Groesse; i++) feld1[i]=ergeb[i]=0;
  65.   fakulz=1;
  66.   ergeb[Groesse-1]=1; /* Ergebnisvektor */
  67.   feld1[Groesse-1]=1; /* Feld1 enthaelt 1/n! */
  68.   nicht_fertig=WAHR;
  69.   /* e berechnen */
  70.   while (nicht_fertig) {
  71.     /* (1 / n!) / (n+1) = 1 / (n+1)! */
  72.     nicht_fertig=division(feld1, fakulz, Groesse);
  73.     /* 1 / (n+1)! zum alten Ergebnis addieren */
  74.     addition(ergeb,feld1,Groesse);
  75.     fakulz++;
  76.   }
  77.   printf("\ne=2,");
  78.   ausgabe(ergeb,Groesse);
  79. }
  80.  
  81. /* Berechnung von PI */
  82. pi(feld1,feld2,ergeb,Groesse)
  83. USHORT feld1[],feld2[],ergeb[], Groesse;
  84. {
  85.   register int addieren, nicht_fertig;
  86.   register USHORT i, zaehler;
  87.   for (i=0; i<Groesse; i++) feld1[i]=feld2[i]=ergeb[i]=0;
  88.   feld1[Groesse-1]=1;
  89.   zaehler = 1;
  90.   potenz = 5;
  91.   nicht_fertig=WAHR;
  92.   addieren=WAHR;
  93.   while (nicht_fertig) {
  94.     /* Ersten Term berechnen */
  95.     division(feld1, potenz, Groesse); /* durch 5 dividieren */
  96.     copy(feld1, feld2, Groesse); /* Kopie anlegen */
  97.     /* Kopie durch Zaehler (3,5,7,9) dividieren
  98.     und prⁿfen, ob Quotient bereits 0 ist */
  99.     nicht_fertig=division(feld2, zaehler, Groesse);
  100.     /* Ergebnis der Divisionen abwechselnd addieren und subtrahieren */
  101.     if (addieren) {
  102.       addition(ergeb,feld2, Groesse);
  103.     }
  104.     else {
  105.       subtraktion(ergeb,feld2, Groesse);
  106.     };
  107.     addieren= !addieren;
  108.     zaehler+=2;
  109.     /* Original noch einmal durch 5 dividieren */
  110.     division(feld1,potenz,Groesse);
  111.   };
  112.   printf("\nzaehler=%u\n",zaehler);
  113.   /* Ergebnis mit 4 multiplizieren */
  114.   addition(ergeb, ergeb, Groesse);
  115.   addition(ergeb, ergeb, Groesse);
  116.   /* Vektoren fⁿr die zweite Runde initialisieren */
  117.   for (i=0; i<Groesse; i++) feld1[i]=feld2[i]=0;
  118.   feld1[Groesse-1]=1;
  119.   potenz=239;
  120.   zaehler=1;
  121.   addieren=FALSCH;
  122.   nicht_fertig=WAHR;
  123.   while (nicht_fertig) {
  124.     /* Term in der zweiten Klammer berechnen */
  125.     division(feld1,potenz,Groesse);
  126.     copy(feld1,feld2,Groesse);
  127.     nicht_fertig=division(feld2,zaehler,Groesse);
  128.     if (addieren) {
  129.       addition(ergeb,feld2,Groesse);
  130.     }
  131.     else {
  132.       subtraktion(ergeb,feld2,Groesse);
  133.     };
  134.     addieren= !addieren;
  135.     zaehler+=2;
  136.     division(feld1,potenz,Groesse);
  137.   };
  138.   /* Ergebnis noch einmal mit 4 multiplizieren */
  139.   addition(ergeb,ergeb,Groesse);
  140.   addition(ergeb,ergeb,Groesse);
  141.   printf("zaehler=%u\n",zaehler);
  142.   printf("\nPI=3,");
  143.   ausgabe(ergeb,Groesse);
  144. }
  145.  
  146. /* feld = feld / divisor */
  147. division(feld, divisor, Groesse)
  148. USHORT feld[], Groesse;
  149. register USHORT divisor;
  150. {
  151.   register ULONG rest, dividend;
  152.   int ergebnis_nicht_null;
  153.   register short i;
  154.  
  155.   rest = 0L;
  156.   ergebnis_nicht_null=FALSCH;
  157.   for (i=Groesse-1; i>=0; i--) {
  158.     dividend=rest*10000+feld[i];
  159.     feld[i]=dividend / divisor;
  160.     if (feld[i]!=0) ergebnis_nicht_null=WAHR;
  161.     rest=dividend % divisor;
  162.   };
  163.     
  164.   return(ergebnis_nicht_null);
  165. }
  166.  
  167. /* feld = feld * faktor */
  168. /*
  169. multiplikation(feld,faktor,Groesse)
  170. USHORT feld[], faktor, Groesse;
  171. {
  172.   register short i;
  173.   register USHORT uebertrag;
  174.   register ULONG produkt;
  175.   uebertrag=0;
  176.   for (i=Groesse-1; i>=0; i--) {
  177.     produkt=feld[i]*faktor;
  178.     if (produkt>9999) {
  179.       feld[i]=(USHORT)(produkt % 10000) + uebertrag;
  180.       uebertrag=(USHORT)(produkt / 10000);
  181.     }
  182.     else {
  183.       feld[i]=(USHORT)produkt;
  184.       uebertrag=0;
  185.     };
  186.   };
  187. }
  188. */
  189.  
  190. /* summe = summe + feld */
  191. addition(summe,feld,Groesse)
  192. USHORT summe[],feld[];
  193. register USHORT Groesse;
  194. {
  195.   register USHORT uebertrag,i;
  196.  
  197.   uebertrag=0;
  198.   for (i=0; i<Groesse; i++) {
  199.     summe[i]+=feld[i]+uebertrag;
  200.     if (summe[i]>9999) {
  201.       summe[i]-=10000;
  202.       uebertrag=1;
  203.     }
  204.     else uebertrag=0;
  205.   };
  206. }
  207.  
  208. /* differenz = differenz - feld */
  209. subtraktion(differenz,feld,Groesse)
  210. USHORT differenz[], feld[];
  211. register USHORT Groesse;
  212. {
  213.   register USHORT uebertrag, i;
  214.   /* Neunerkomplement von Feld berechnen */
  215.   for (i=0; i<Groesse; i++) feld[i]=9999-feld[i];
  216.   /* Eins addieren --> ergibt Zehnerkomplement */
  217.   uebertrag=1;
  218.   i=0;
  219.   while ((uebertrag==1) && (i<Groesse)) {
  220.     feld[i]+=uebertrag;
  221.     if (feld[i] > 9999) {
  222.       feld[i]-=10000;
  223.       uebertrag=1;
  224.     }
  225.     else uebertrag=0;
  226.     i++;
  227.   };
  228.   /* Zehnerkomplement zu Differenz addieren */
  229.   addition(differenz, feld, Groesse);
  230. }
  231.  
  232. copy(original, kopie, Groesse)
  233. USHORT original[], kopie[];
  234. register USHORT Groesse;
  235. {
  236.   register USHORT i;
  237.  
  238.   for (i=0; i<Groesse; i++) kopie[i]=original[i];
  239. }
  240.  
  241. ausgabe(ergeb,Groesse) /* Ergebnis ausgeben */
  242. USHORT ergeb[];
  243. register USHORT Groesse;
  244. {
  245.   char zeichen[5];
  246.   register short i,j;
  247.  
  248.   zeichen[4]=NULL;
  249.   for (i=Groesse-2; i>=0; i--) {
  250.     for (j=0; j<4; j++) {
  251.       zeichen[3-j]= (ergeb[i] % 10) + '0';
  252.       ergeb[i]/=10;
  253.     };
  254.     printf("%4s",zeichen);
  255.   };
  256. }
  257.