// Factorial for big numbers. Read a (small) integer on standard // input, and print its factorial. Works easily with 1000. // $Id: bignums.eins,v 1.1 2005/04/27 13:56:09 dragos Exp $ def printNewLine(): Unit = printChar(10); def isEmpty(l: List): Int = (l == null); def bigPrint(n: List): Unit = if (!isEmpty(n)) { if (isEmpty(n.tail)) printInt(n.head) else { do bigPrint(n.tail); do printInt((n.head / 1000) % 10); do printInt((n.head / 100) % 10); do printInt((n.head / 10) % 10); do printInt(n.head % 10); } }; // add two numbers def bigAddC(n1: List, n2: List, carry: Int): List = if (isEmpty(n1)) if (carry == 0) n2 else bigAddC(new List(carry, null), n2, 0) else if (isEmpty(n2)) if (carry == 0) n1 else bigAddC(n1, new List(carry, null), 0) else { var h1: Int = n1.head; var h2: Int = n2.head; var res: Int = h1 + h2 + carry; new List((res % 10000), bigAddC(n1.tail, n2.tail, res / 10000)) }; def bigAdd(n1: List, n2: List): List = bigAddC(n1, n2, 0); def bigScaleC(n: List, c: Int, carry: Int): List = if (isEmpty(n)) if (carry == 0) null else new List(carry, null) else { var sh: Int = n.head * c + carry; new List((sh % 10000), bigScaleC(n.tail, c, sh / 10000)) }; def bigScale(n: List, c: Int): List = bigScaleC(n, c, 0); def bigMul(n1: List, n2: List): List = if (isEmpty(n1)) null else bigAdd(bigScale(n2, n1.head), bigScale(bigMul(n1.tail, n2), 10000)); def bigOfInt(n: Int): List = new List(n, null); def bigZero(n: List): Int = isEmpty(n); def fact(n: Int): List = if (n == 0) bigOfInt(1) else bigMul(bigOfInt(n), fact(n - 1)); { do bigPrint(fact(readInt())); printNewLine() }