Very high precision facorials

This project started in the obc section but I decided to back-port it to Modula-2. This program calculates factorials with infinite precision. At least: semi-infinite. The number to be factorialed is finite (not higher than 200000!) so infinite precision is a bit exagerated.
Still, no digits re lost during the calculations. So 1234! is 3282 digits in total and never was there any rounding. I wouldn't know why someone would like to see all digits of 1234! but that doesn't count.

fac2.mod

Below is the source of fac2.mod. It is almost identical to fac2.m as published in the obc section.

MODULE fac2;

IMPORT	InOut, Storage, SYSTEM;


TYPE	numPtr		= POINTER TO numNode;
	numNode		= RECORD
			    val	   : INTEGER;
			    prev,
			    next   : numPtr
			  END;


VAR	n			: INTEGER;
	muls			: LONGINT;
	this, first, last	: numPtr;


PROCEDURE Print (num : INTEGER);

BEGIN
  InOut.WriteInt ( num DIV 1000, 1);
  InOut.WriteInt ((num MOD 1000) DIV 100, 1);
  InOut.WriteInt ((num MOD 100 ) DIV 10 , 1);
  InOut.WriteInt ( num MOD 10, 1)
END Print;


PROCEDURE Multiply (bignum : numPtr; num : INTEGER);

VAR	carry		: INTEGER;
	This, Next	: numPtr;

BEGIN
  carry := 0;
  This := bignum;
  LOOP
    INC (muls);
    This^.val := This^.val * num + carry;
    carry := This^.val DIV 10000;
    This^.val := This^.val MOD 10000;
    IF  (carry > 0) & (This = last)  THEN
      Storage.ALLOCATE (Next, SYSTEM.TSIZE (numNode));
      IF  Next = NIL  THEN
        InOut.WriteString ("Memory allocation failed; aborting.");	InOut.WriteLn;
        HALT
      END;
      This^.next := Next;
      Next^.prev := This;
      Next^.val := carry;
      last := Next;
      EXIT
    END;
    This := This^.next;
    IF  This = NIL  THEN  EXIT  END
  END
END Multiply;


BEGIN
  InOut.WriteString ("Which number : ");	InOut.WriteBf;
  InOut.ReadInt (n);
  InOut.WriteLn;
  IF  n > 200000  THEN
    InOut.WriteString ("This will cause overflow");
    InOut.WriteLn;
    HALT
  ELSIF  n < 2  THEN
    InOut.WriteInt (n, 2);
    InOut.WriteString ("! = 1");
    InOut.WriteLn;
    HALT
  END;
  muls := 0;
  InOut.WriteInt (n, 1);	InOut.WriteString ("! = ");
  Storage.ALLOCATE (first, SYSTEM.TSIZE (numNode));
  last := first;		last^.next := NIL;
  first^.prev := NIL;		first^.val := 1;
  REPEAT  
    Multiply (first, n);
    DEC (n)
  UNTIL  n = 1;
  this := last;
  InOut.WriteInt (this^.val, 1);
  WHILE  this^.prev # NIL  DO
    this := this^.prev;
    INC (n);
    Print (this^.val)
  END;
  InOut.WriteLn;
  InOut.WriteString ("Integers used = ");
  InOut.WriteInt (n, 1);
  InOut.WriteLn;
  InOut.WriteString ("Multiplications = ");
  InOut.WriteInt (muls, 12);
  InOut.WriteLn
END fac2.
   

See it run

jan@nitrogen:~/Modula/fac$ mocka
Mocka 0608m
>> i fac2
>> p fac2
.. Compiling Program Module fac2 I/0003 II/0003
.. Linking fac2
>> ./fac2
Which number : 10

10! = 3628800
Integers used = 2
Multiplications =           13
>> q
jan@nitrogen:~/Modula/fac$ ls -l
total 36
-rwxr-xr-x 1 jan users 23220 Jul 25 20:38 fac2*
-rw-r--r-- 1 jan users  2086 Jul 25 20:38 fac2.mod
-rw-r--r-- 1 jan users  2068 Jul 25 20:36 fac2.mod~
drwxr-xr-x 2 jan users  4096 Jul 25 20:38 m2bin/
jan@nitrogen:~/Modula/fac$ purge
   
Now let's see what it pumps out for 1234!:
51084981466469576881306176261004598750272741624636207875758364885679783886389114
11990436739821490945161686595979719008559595721606020108179086356274071139240840
26061622844243479264441682937703064598774296205499801216218800688121199228255656
03750036793657428476498577316887890689284884464423522469162924654419945496940052
74606695086778408475358154014819431688830383969486087035700823552502811528140237
92702794467430978688961805679014528720317341950564325765687543465282585698835268
59826727735838654082246721751819658052692396270611348013013786739320229706009940
78102558603880949301399211103043247332153222858963615072262136036697860748469287
09556917407233492272203675129943551465674759800063734002158260779494943353705916
23671142026957923937669224771617167959359650439966392673073180139376563073706562
20077124129171082813207892867269337760528069834097651262268620717525910898425397
99702693305919514002658689440140017406063982207098594617099720923169536397076075
09036387468655214963966625322700932867195641466506305265122238332824677892386098
87304547794657047561447073568101153776293006833322975346131117569005319027621721
59381222292540116633195356685622882768145665362541399443274469237496751568383992
58655227114181067181300031191298489076680172983118121156086627360397334232174932
13268608090156949639212926370659550947254192102703994759578799220953706903137951
71129858042764127194913347302477628762607535601990124243602118624660475111847971
59731714330368251192307852167757615200611669009575630075581632200897019110165738
48928823484580141354209008692638175664222887272931958772412064713369544765870946
60471317874675216489673751461760257755459580181498955708174630489683296928120039
96105944812538484291689075721849889797647554854834050132592317503861422078077932
84139625077230589237830496042102484581504792822966934281821896024357947318098699
68834861646135862246777824053636757329403864365601599929614625502185299212142235
56288943276860000631422449845365510986932611414112386178573447134236164502410346
25451642181282535015238390792529919937109390239312631759033734037119928838060369
45170356626658272873520235631287564025160817497053257051964777693153111640297330
67419282135214232605607889159739038923579732630816548135472123812968829466513428
48468376088873190068520530801649553325205571819014264432000968303267716360974461
46297306314548981674629662653878717255800835145656237192706356836622686633339990
29883429331462872848995229714115709023973771126468913873648061531223428749576267
07908453465692351493149674384255966938663850988470930716618720516144581982826367
92701126140123785422738372964270440212520778637069635144862181838064918687911747
85424506337810550453063897866281127060200866754011181906809870372032953354528699
09409614512099784207510905785922612084417645417539378125400438209135099410195940
65901754020866988745836115819373470034234495212232451666657922572521604623577330
00925232292157683100179557359793926298007588370474068230320921987459976042606283
56600515820257280000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000000000000
   

Trouble at the mill

I am an engineer. I have a playful mind. So I was fooling around with the new fac2 program to find out the following:

jan@nitrogen:~/Modula/fac$ ./fac2
Which number : 10580

10580! =
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000
Integers used = 288
Multiplications =      3005424
   
That's 1149 zeroes. And the result took only half a second of calculation time. There was no memory allocation error. No segfault. No nothing. Just a wrong result. I've been studyiong the sources for quite some time but I haven't got a clue.

So I changed all INTEGER values for CARDINALs. And that solved the problem. Was it some kind of overflow? I did a test with the working versions:
Integers used = 9497
Multiplications =     53258938
   
The number of zeroes was 2643. Not 1149. It was a strange problem. I reran the Oberon version:
Integers used = 9494
Multiplications =     53234765
   
Oberon uses three array elements less. And uses 24173 less multiplications. That is strange. Time to compare the results. To cut a long story short: the results are different. I assume the Modula-2 version is wrong. More to follow.

Something fishy around 10556!

Extensive testing has revealed that f8 and fac2 produce identical results for all values upto 10.000! and from 11.000! things go terribly wrong. I guess the problem of fac2 was not solved by changing the INTEGERs into CARDINALs.

Page created 26 July 2014 and