formualizer_eval/builtins/math/
combinatorics.rs

1use super::super::utils::{ARG_NUM_LENIENT_ONE, ARG_NUM_LENIENT_TWO, coerce_num};
2use crate::args::ArgSchema;
3use crate::function::Function;
4use crate::traits::{ArgumentHandle, CalcValue, FunctionContext};
5use formualizer_common::{ExcelError, LiteralValue};
6use formualizer_macros::func_caps;
7
8#[derive(Debug)]
9pub struct FactFn;
10/// Returns the factorial of a non-negative integer.
11///
12/// `FACT` truncates fractional inputs toward zero before computing the factorial.
13///
14/// # Remarks
15/// - Non-numeric values that cannot be coerced return `#VALUE!`.
16/// - Negative inputs return `#NUM!`.
17/// - Results above `170!` overflow Excel-compatible limits and return `#NUM!`.
18///
19/// # Examples
20///
21/// ```yaml,sandbox
22/// title: "Basic factorial"
23/// formula: "=FACT(5)"
24/// expected: 120
25/// ```
26///
27/// ```yaml,sandbox
28/// title: "Fractional input is truncated"
29/// formula: "=FACT(5.9)"
30/// expected: 120
31/// ```
32///
33/// ```yaml,sandbox
34/// title: "Negative input returns numeric error"
35/// formula: "=FACT(-1)"
36/// expected: "#NUM!"
37/// ```
38///
39/// ```yaml,docs
40/// related:
41///   - FACTDOUBLE
42///   - GAMMALN
43///   - COMBIN
44/// faq:
45///   - q: "Why does FACT(171) return #NUM!?"
46///     a: "Excel-compatible factorial support is capped at 170!; larger values overflow and return #NUM!."
47///   - q: "Does FACT round fractional inputs?"
48///     a: "No. It truncates toward zero before computing the factorial."
49/// ```
50///
51/// [formualizer-docgen:schema:start]
52/// Name: FACT
53/// Type: FactFn
54/// Min args: 1
55/// Max args: 1
56/// Variadic: false
57/// Signature: FACT(arg1: number@scalar)
58/// Arg schema: arg1{kinds=number,required=true,shape=scalar,by_ref=false,coercion=NumberLenientText,max=None,repeating=None,default=false}
59/// Caps: PURE
60/// [formualizer-docgen:schema:end]
61impl Function for FactFn {
62    func_caps!(PURE);
63    fn name(&self) -> &'static str {
64        "FACT"
65    }
66    fn min_args(&self) -> usize {
67        1
68    }
69    fn arg_schema(&self) -> &'static [ArgSchema] {
70        &ARG_NUM_LENIENT_ONE[..]
71    }
72    fn eval<'a, 'b, 'c>(
73        &self,
74        args: &'c [ArgumentHandle<'a, 'b>],
75        _: &dyn FunctionContext<'b>,
76    ) -> Result<CalcValue<'b>, ExcelError> {
77        let v = args[0].value()?.into_literal();
78        let n = match v {
79            LiteralValue::Error(e) => return Ok(CalcValue::Scalar(LiteralValue::Error(e))),
80            other => coerce_num(&other)?,
81        };
82
83        // Excel truncates to integer
84        let n = n.trunc() as i64;
85
86        if n < 0 {
87            return Ok(CalcValue::Scalar(
88                LiteralValue::Error(ExcelError::new_num()),
89            ));
90        }
91
92        // Factorial calculation (Excel supports up to 170!)
93        if n > 170 {
94            return Ok(CalcValue::Scalar(
95                LiteralValue::Error(ExcelError::new_num()),
96            ));
97        }
98
99        let mut result = 1.0_f64;
100        for i in 2..=(n as u64) {
101            result *= i as f64;
102        }
103
104        Ok(CalcValue::Scalar(LiteralValue::Number(result)))
105    }
106}
107
108#[derive(Debug)]
109pub struct GcdFn;
110/// Returns the greatest common divisor of one or more integers.
111///
112/// `GCD` truncates each argument toward zero before calculating the divisor.
113///
114/// # Remarks
115/// - Inputs must be between `0` and `9.99999999e9` after truncation, or `#NUM!` is returned.
116/// - Negative values return `#NUM!`.
117/// - Any argument error propagates immediately.
118///
119/// # Examples
120///
121/// ```yaml,sandbox
122/// title: "Greatest common divisor of two numbers"
123/// formula: "=GCD(24, 36)"
124/// expected: 12
125/// ```
126///
127/// ```yaml,sandbox
128/// title: "Variadic and fractional arguments"
129/// formula: "=GCD(18.9, 6, 30)"
130/// expected: 6
131/// ```
132///
133/// ```yaml,sandbox
134/// title: "Negative values are invalid"
135/// formula: "=GCD(-2, 4)"
136/// expected: "#NUM!"
137/// ```
138///
139/// ```yaml,docs
140/// related:
141///   - LCM
142///   - MOD
143///   - QUOTIENT
144/// faq:
145///   - q: "What happens to decimal inputs in GCD?"
146///     a: "Each argument is truncated toward zero before the divisor is computed."
147///   - q: "When does GCD return #NUM!?"
148///     a: "Negative values or values outside the supported bound return #NUM!."
149/// ```
150///
151/// [formualizer-docgen:schema:start]
152/// Name: GCD
153/// Type: GcdFn
154/// Min args: 1
155/// Max args: variadic
156/// Variadic: true
157/// Signature: GCD(arg1: number@scalar, arg2...: number@scalar)
158/// Arg schema: arg1{kinds=number,required=true,shape=scalar,by_ref=false,coercion=NumberLenientText,max=None,repeating=None,default=false}; arg2{kinds=number,required=true,shape=scalar,by_ref=false,coercion=NumberLenientText,max=None,repeating=None,default=false}
159/// Caps: PURE
160/// [formualizer-docgen:schema:end]
161impl Function for GcdFn {
162    func_caps!(PURE);
163    fn name(&self) -> &'static str {
164        "GCD"
165    }
166    fn min_args(&self) -> usize {
167        1
168    }
169    fn variadic(&self) -> bool {
170        true
171    }
172    fn arg_schema(&self) -> &'static [ArgSchema] {
173        &ARG_NUM_LENIENT_TWO[..]
174    }
175    fn eval<'a, 'b, 'c>(
176        &self,
177        args: &'c [ArgumentHandle<'a, 'b>],
178        _: &dyn FunctionContext<'b>,
179    ) -> Result<CalcValue<'b>, ExcelError> {
180        fn gcd(a: u64, b: u64) -> u64 {
181            if b == 0 { a } else { gcd(b, a % b) }
182        }
183
184        let mut result: Option<u64> = None;
185
186        for arg in args {
187            let v = arg.value()?.into_literal();
188            let n = match v {
189                LiteralValue::Error(e) => return Ok(CalcValue::Scalar(LiteralValue::Error(e))),
190                other => coerce_num(&other)?,
191            };
192
193            // Excel truncates and requires non-negative
194            let n = n.trunc();
195            if !(0.0..=9.99999999e9).contains(&n) {
196                return Ok(CalcValue::Scalar(
197                    LiteralValue::Error(ExcelError::new_num()),
198                ));
199            }
200            let n = n as u64;
201
202            result = Some(match result {
203                None => n,
204                Some(r) => gcd(r, n),
205            });
206        }
207
208        Ok(CalcValue::Scalar(LiteralValue::Number(
209            result.unwrap_or(0) as f64
210        )))
211    }
212}
213
214#[derive(Debug)]
215pub struct LcmFn;
216/// Returns the least common multiple of one or more integers.
217///
218/// `LCM` truncates fractional arguments toward zero and combines values iteratively.
219///
220/// # Remarks
221/// - Inputs must be non-negative and within the supported Excel-compatible range.
222/// - If any input is `0`, the resulting least common multiple is `0`.
223/// - Any argument error propagates immediately.
224///
225/// # Examples
226///
227/// ```yaml,sandbox
228/// title: "Least common multiple for two integers"
229/// formula: "=LCM(4, 6)"
230/// expected: 12
231/// ```
232///
233/// ```yaml,sandbox
234/// title: "Fractional values are truncated"
235/// formula: "=LCM(6.8, 8.2)"
236/// expected: 24
237/// ```
238///
239/// ```yaml,sandbox
240/// title: "Negative values return numeric error"
241/// formula: "=LCM(-3, 6)"
242/// expected: "#NUM!"
243/// ```
244///
245/// ```yaml,docs
246/// related:
247///   - GCD
248///   - MOD
249///   - MROUND
250/// faq:
251///   - q: "Why does LCM return 0 when one argument is 0?"
252///     a: "LCM is defined as 0 if any truncated input is 0 in this implementation."
253///   - q: "Are fractional inputs accepted?"
254///     a: "Yes, but they are truncated toward zero before the LCM calculation."
255/// ```
256///
257/// [formualizer-docgen:schema:start]
258/// Name: LCM
259/// Type: LcmFn
260/// Min args: 1
261/// Max args: variadic
262/// Variadic: true
263/// Signature: LCM(arg1: number@scalar, arg2...: number@scalar)
264/// Arg schema: arg1{kinds=number,required=true,shape=scalar,by_ref=false,coercion=NumberLenientText,max=None,repeating=None,default=false}; arg2{kinds=number,required=true,shape=scalar,by_ref=false,coercion=NumberLenientText,max=None,repeating=None,default=false}
265/// Caps: PURE
266/// [formualizer-docgen:schema:end]
267impl Function for LcmFn {
268    func_caps!(PURE);
269    fn name(&self) -> &'static str {
270        "LCM"
271    }
272    fn min_args(&self) -> usize {
273        1
274    }
275    fn variadic(&self) -> bool {
276        true
277    }
278    fn arg_schema(&self) -> &'static [ArgSchema] {
279        &ARG_NUM_LENIENT_TWO[..]
280    }
281    fn eval<'a, 'b, 'c>(
282        &self,
283        args: &'c [ArgumentHandle<'a, 'b>],
284        _: &dyn FunctionContext<'b>,
285    ) -> Result<CalcValue<'b>, ExcelError> {
286        fn gcd(a: u64, b: u64) -> u64 {
287            if b == 0 { a } else { gcd(b, a % b) }
288        }
289        fn lcm(a: u64, b: u64) -> u64 {
290            if a == 0 || b == 0 {
291                0
292            } else {
293                (a / gcd(a, b)) * b
294            }
295        }
296
297        let mut result: Option<u64> = None;
298
299        for arg in args {
300            let v = arg.value()?.into_literal();
301            let n = match v {
302                LiteralValue::Error(e) => return Ok(CalcValue::Scalar(LiteralValue::Error(e))),
303                other => coerce_num(&other)?,
304            };
305
306            let n = n.trunc();
307            if !(0.0..=9.99999999e9).contains(&n) {
308                return Ok(CalcValue::Scalar(
309                    LiteralValue::Error(ExcelError::new_num()),
310                ));
311            }
312            let n = n as u64;
313
314            result = Some(match result {
315                None => n,
316                Some(r) => lcm(r, n),
317            });
318        }
319
320        Ok(CalcValue::Scalar(LiteralValue::Number(
321            result.unwrap_or(0) as f64
322        )))
323    }
324}
325
326#[derive(Debug)]
327pub struct CombinFn;
328/// Returns the number of combinations for selecting `k` items from `n`.
329///
330/// `COMBIN` evaluates `n` choose `k` using truncated integer inputs.
331///
332/// # Remarks
333/// - Fractional inputs are truncated toward zero before evaluation.
334/// - If `n < 0`, `k < 0`, or `k > n`, the function returns `#NUM!`.
335/// - Argument errors propagate directly.
336///
337/// # Examples
338///
339/// ```yaml,sandbox
340/// title: "Basic combinations"
341/// formula: "=COMBIN(5, 2)"
342/// expected: 10
343/// ```
344///
345/// ```yaml,sandbox
346/// title: "Fractional arguments are truncated"
347/// formula: "=COMBIN(6.9, 3.2)"
348/// expected: 20
349/// ```
350///
351/// ```yaml,sandbox
352/// title: "Invalid k returns numeric error"
353/// formula: "=COMBIN(3, 5)"
354/// expected: "#NUM!"
355/// ```
356///
357/// ```yaml,docs
358/// related:
359///   - COMBINA
360///   - PERMUT
361///   - FACT
362/// faq:
363///   - q: "When does COMBIN return #NUM!?"
364///     a: "It returns #NUM! if n or k is negative, or if k is greater than n after truncation."
365///   - q: "Can COMBIN take non-integer values?"
366///     a: "Yes, but both inputs are truncated toward zero before evaluation."
367/// ```
368///
369/// [formualizer-docgen:schema:start]
370/// Name: COMBIN
371/// Type: CombinFn
372/// Min args: 2
373/// Max args: 2
374/// Variadic: false
375/// Signature: COMBIN(arg1: number@scalar, arg2: number@scalar)
376/// Arg schema: arg1{kinds=number,required=true,shape=scalar,by_ref=false,coercion=NumberLenientText,max=None,repeating=None,default=false}; arg2{kinds=number,required=true,shape=scalar,by_ref=false,coercion=NumberLenientText,max=None,repeating=None,default=false}
377/// Caps: PURE
378/// [formualizer-docgen:schema:end]
379impl Function for CombinFn {
380    func_caps!(PURE);
381    fn name(&self) -> &'static str {
382        "COMBIN"
383    }
384    fn min_args(&self) -> usize {
385        2
386    }
387    fn arg_schema(&self) -> &'static [ArgSchema] {
388        &ARG_NUM_LENIENT_TWO[..]
389    }
390    fn eval<'a, 'b, 'c>(
391        &self,
392        args: &'c [ArgumentHandle<'a, 'b>],
393        _: &dyn FunctionContext<'b>,
394    ) -> Result<CalcValue<'b>, ExcelError> {
395        // Check minimum required arguments
396        if args.len() < 2 {
397            return Ok(CalcValue::Scalar(LiteralValue::Error(
398                ExcelError::new_value(),
399            )));
400        }
401
402        let n_val = args[0].value()?.into_literal();
403        let k_val = args[1].value()?.into_literal();
404
405        let n = match n_val {
406            LiteralValue::Error(e) => return Ok(CalcValue::Scalar(LiteralValue::Error(e))),
407            other => coerce_num(&other)?,
408        };
409        let k = match k_val {
410            LiteralValue::Error(e) => return Ok(CalcValue::Scalar(LiteralValue::Error(e))),
411            other => coerce_num(&other)?,
412        };
413
414        let n = n.trunc() as i64;
415        let k = k.trunc() as i64;
416
417        if n < 0 || k < 0 || k > n {
418            return Ok(CalcValue::Scalar(
419                LiteralValue::Error(ExcelError::new_num()),
420            ));
421        }
422
423        // Calculate C(n, k) = n! / (k! * (n-k)!)
424        // Use the more efficient formula: C(n, k) = product of (n-i)/(i+1) for i in 0..k
425        let k = k.min(n - k) as u64; // Use symmetry for efficiency
426        let n = n as u64;
427
428        let mut result = 1.0_f64;
429        for i in 0..k {
430            result = result * (n - i) as f64 / (i + 1) as f64;
431        }
432
433        Ok(CalcValue::Scalar(LiteralValue::Number(result.round())))
434    }
435}
436
437#[derive(Debug)]
438pub struct PermutFn;
439/// Returns the number of permutations for selecting and ordering `k` items from `n`.
440///
441/// `PERMUT` computes `n!/(n-k)!` after truncating both inputs toward zero.
442///
443/// # Remarks
444/// - Fractional inputs are truncated to integers.
445/// - If `n < 0`, `k < 0`, or `k > n`, the function returns `#NUM!`.
446/// - Argument errors propagate directly.
447///
448/// # Examples
449///
450/// ```yaml,sandbox
451/// title: "Basic permutations"
452/// formula: "=PERMUT(5, 2)"
453/// expected: 20
454/// ```
455///
456/// ```yaml,sandbox
457/// title: "Fractional arguments are truncated"
458/// formula: "=PERMUT(7.9, 3.1)"
459/// expected: 210
460/// ```
461///
462/// ```yaml,sandbox
463/// title: "Out-of-range k returns numeric error"
464/// formula: "=PERMUT(4, 6)"
465/// expected: "#NUM!"
466/// ```
467///
468/// ```yaml,docs
469/// related:
470///   - COMBIN
471///   - FACT
472///   - MULTINOMIAL
473/// faq:
474///   - q: "Why does PERMUT fail when k is larger than n?"
475///     a: "Permutations require choosing at most n items, so k > n returns #NUM!."
476///   - q: "How are decimal inputs handled?"
477///     a: "PERMUT truncates n and k toward zero before computing n!/(n-k)!."
478/// ```
479///
480/// [formualizer-docgen:schema:start]
481/// Name: PERMUT
482/// Type: PermutFn
483/// Min args: 2
484/// Max args: 2
485/// Variadic: false
486/// Signature: PERMUT(arg1: number@scalar, arg2: number@scalar)
487/// Arg schema: arg1{kinds=number,required=true,shape=scalar,by_ref=false,coercion=NumberLenientText,max=None,repeating=None,default=false}; arg2{kinds=number,required=true,shape=scalar,by_ref=false,coercion=NumberLenientText,max=None,repeating=None,default=false}
488/// Caps: PURE
489/// [formualizer-docgen:schema:end]
490impl Function for PermutFn {
491    func_caps!(PURE);
492    fn name(&self) -> &'static str {
493        "PERMUT"
494    }
495    fn min_args(&self) -> usize {
496        2
497    }
498    fn arg_schema(&self) -> &'static [ArgSchema] {
499        &ARG_NUM_LENIENT_TWO[..]
500    }
501    fn eval<'a, 'b, 'c>(
502        &self,
503        args: &'c [ArgumentHandle<'a, 'b>],
504        _: &dyn FunctionContext<'b>,
505    ) -> Result<CalcValue<'b>, ExcelError> {
506        // Check minimum required arguments
507        if args.len() < 2 {
508            return Ok(CalcValue::Scalar(LiteralValue::Error(
509                ExcelError::new_value(),
510            )));
511        }
512
513        let n_val = args[0].value()?.into_literal();
514        let k_val = args[1].value()?.into_literal();
515
516        let n = match n_val {
517            LiteralValue::Error(e) => return Ok(CalcValue::Scalar(LiteralValue::Error(e))),
518            other => coerce_num(&other)?,
519        };
520        let k = match k_val {
521            LiteralValue::Error(e) => return Ok(CalcValue::Scalar(LiteralValue::Error(e))),
522            other => coerce_num(&other)?,
523        };
524
525        let n = n.trunc() as i64;
526        let k = k.trunc() as i64;
527
528        if n < 0 || k < 0 || k > n {
529            return Ok(CalcValue::Scalar(
530                LiteralValue::Error(ExcelError::new_num()),
531            ));
532        }
533
534        // P(n, k) = n! / (n-k)! = n * (n-1) * ... * (n-k+1)
535        let mut result = 1.0_f64;
536        for i in 0..k {
537            result *= (n - i) as f64;
538        }
539
540        Ok(CalcValue::Scalar(LiteralValue::Number(result)))
541    }
542}
543
544pub fn register_builtins() {
545    use std::sync::Arc;
546    crate::function_registry::register_function(Arc::new(FactFn));
547    crate::function_registry::register_function(Arc::new(GcdFn));
548    crate::function_registry::register_function(Arc::new(LcmFn));
549    crate::function_registry::register_function(Arc::new(CombinFn));
550    crate::function_registry::register_function(Arc::new(PermutFn));
551}
552
553#[cfg(test)]
554mod tests {
555    use super::*;
556    use crate::test_workbook::TestWorkbook;
557    use crate::traits::ArgumentHandle;
558    use formualizer_parse::parser::{ASTNode, ASTNodeType};
559
560    fn interp(wb: &TestWorkbook) -> crate::interpreter::Interpreter<'_> {
561        wb.interpreter()
562    }
563    fn lit(v: LiteralValue) -> ASTNode {
564        ASTNode::new(ASTNodeType::Literal(v), None)
565    }
566
567    #[test]
568    fn fact_basic() {
569        let wb = TestWorkbook::new().with_function(std::sync::Arc::new(FactFn));
570        let ctx = interp(&wb);
571        let n = lit(LiteralValue::Number(5.0));
572        let f = ctx.context.get_function("", "FACT").unwrap();
573        assert_eq!(
574            f.dispatch(
575                &[ArgumentHandle::new(&n, &ctx)],
576                &ctx.function_context(None)
577            )
578            .unwrap()
579            .into_literal(),
580            LiteralValue::Number(120.0)
581        );
582    }
583
584    #[test]
585    fn fact_zero() {
586        let wb = TestWorkbook::new().with_function(std::sync::Arc::new(FactFn));
587        let ctx = interp(&wb);
588        let n = lit(LiteralValue::Number(0.0));
589        let f = ctx.context.get_function("", "FACT").unwrap();
590        assert_eq!(
591            f.dispatch(
592                &[ArgumentHandle::new(&n, &ctx)],
593                &ctx.function_context(None)
594            )
595            .unwrap()
596            .into_literal(),
597            LiteralValue::Number(1.0)
598        );
599    }
600
601    #[test]
602    fn gcd_basic() {
603        let wb = TestWorkbook::new().with_function(std::sync::Arc::new(GcdFn));
604        let ctx = interp(&wb);
605        let a = lit(LiteralValue::Number(12.0));
606        let b = lit(LiteralValue::Number(18.0));
607        let f = ctx.context.get_function("", "GCD").unwrap();
608        assert_eq!(
609            f.dispatch(
610                &[ArgumentHandle::new(&a, &ctx), ArgumentHandle::new(&b, &ctx)],
611                &ctx.function_context(None)
612            )
613            .unwrap()
614            .into_literal(),
615            LiteralValue::Number(6.0)
616        );
617    }
618
619    #[test]
620    fn lcm_basic() {
621        let wb = TestWorkbook::new().with_function(std::sync::Arc::new(LcmFn));
622        let ctx = interp(&wb);
623        let a = lit(LiteralValue::Number(4.0));
624        let b = lit(LiteralValue::Number(6.0));
625        let f = ctx.context.get_function("", "LCM").unwrap();
626        assert_eq!(
627            f.dispatch(
628                &[ArgumentHandle::new(&a, &ctx), ArgumentHandle::new(&b, &ctx)],
629                &ctx.function_context(None)
630            )
631            .unwrap()
632            .into_literal(),
633            LiteralValue::Number(12.0)
634        );
635    }
636
637    #[test]
638    fn combin_basic() {
639        let wb = TestWorkbook::new().with_function(std::sync::Arc::new(CombinFn));
640        let ctx = interp(&wb);
641        let n = lit(LiteralValue::Number(5.0));
642        let k = lit(LiteralValue::Number(2.0));
643        let f = ctx.context.get_function("", "COMBIN").unwrap();
644        assert_eq!(
645            f.dispatch(
646                &[ArgumentHandle::new(&n, &ctx), ArgumentHandle::new(&k, &ctx)],
647                &ctx.function_context(None)
648            )
649            .unwrap()
650            .into_literal(),
651            LiteralValue::Number(10.0)
652        );
653    }
654
655    #[test]
656    fn permut_basic() {
657        let wb = TestWorkbook::new().with_function(std::sync::Arc::new(PermutFn));
658        let ctx = interp(&wb);
659        let n = lit(LiteralValue::Number(5.0));
660        let k = lit(LiteralValue::Number(2.0));
661        let f = ctx.context.get_function("", "PERMUT").unwrap();
662        assert_eq!(
663            f.dispatch(
664                &[ArgumentHandle::new(&n, &ctx), ArgumentHandle::new(&k, &ctx)],
665                &ctx.function_context(None)
666            )
667            .unwrap()
668            .into_literal(),
669            LiteralValue::Number(20.0)
670        );
671    }
672}
formualizer_eval/builtins/math/combinatorics.rs

formualizer_eval/builtins/math/
combinatorics.rs
