1 /*
2 * Copyright (c) 2020-2024 Stefan Krah. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 *
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24 * SUCH DAMAGE.
25 */
26
27
28 #include <iostream>
29
30 #include "decimal.hh"
31
32
33 using decimal::Decimal;
34 using decimal::MaxContext;
35 using decimal::context;
36
37 using decimal::ConversionSyntax;
38 using decimal::InvalidOperation;
39 using decimal::MallocError;
40
41 using decimal::DecRounded;
42 using decimal::DecInexact;
43
44
45 Decimal
f(const Decimal & n,const Decimal & m)46 f(const Decimal& n, const Decimal& m)
47 {
48 if (n > m) {
49 return f(m, n);
50 }
51 else if (m == 0) {
52 return 1;
53 }
54 else if (n == m) {
55 return n;
56 }
57 else {
58 return f(n, (n + m).divint(2)) * f((n + m).divint(2) + 1, m);
59 }
60 }
61
62 Decimal
factorial(const Decimal & n)63 factorial(const Decimal& n)
64 {
65 context = MaxContext();
66
67 // DecRounded can be skipped if integer results with non-zero
68 // exponents are allowed.
69 context.add_traps(DecInexact|DecRounded);
70
71 return f(n, Decimal(0));
72 }
73
74 void
err_exit(const std::string & msg)75 err_exit(const std::string& msg)
76 {
77 std::cerr << msg << std::endl;
78 std::exit(1);
79 }
80
81 int
main(int argc,char * argv[])82 main(int argc, char *argv[])
83 {
84 Decimal n;
85
86 if (argc != 2) {
87 err_exit("usage: ./factorial n");
88 }
89
90 try {
91 n = Decimal(argv[1]);
92 }
93 catch (ConversionSyntax&) {
94 err_exit("invalid decimal string");
95 }
96 catch (InvalidOperation&) {
97 err_exit("value exceeds internal limits");
98 }
99 catch (MallocError&) {
100 err_exit("out of memory");
101 }
102
103 // The exponent could be nonzero, this is to avoid surprise at the result.
104 if (!n.isinteger() || n.exponent() != 0 || n < 0) {
105 err_exit("n must be a non-negative integer with exponent zero");
106 }
107
108 std::cout << factorial(n) << std::endl;
109
110 return 0;
111 }
112