Curiousness at 1200! (factorial)... ?

[qtfkwk]

This used to work just fine about a year ago (with num 0.4.0 and factorial 0.2.1) to calculate permutations:

$ xpg --analyze
* Word list length: 1,259
* Words in password: 4
* Total permutations (without repetition): 2,500,525,503,024

    ```
    1,259! / (1,259 - 4)!
    1,259! / 1,255!
    2,500,525,503,024
    ```

Words | Permutations
---|---:
1 | 1,259
2 | 1,583,822
3 | 1,990,864,254
4 | 2,500,525,503,024
5 | 3,138,159,506,295,120
6 | 3,935,252,020,894,080,480
7 | 4,930,870,782,180,282,841,440
8 | 6,173,450,219,289,714,117,482,880
... | ...

Reference xpg/README.md and xpg/src/lib.rs: permutations() function and use.

---

Now working with num 0.4.1 (with or without num-bigint feature, doesn't seem to matter) and factorial 0.3.0 and otherwise same code says:

$ xpg --analyze
* Word list length: 1,259
* Words in password: 4
* Total permutations (without repetition): 51

    ```
    1,259! / (1,259 - 4)!
    1,259! / 1,255!
    51
    ```

Words | Permutations
---|---:
1 | 1
2 | 1,258
3 | 1,581,306
4 | 51
5 | 64,808
6 | 81,269,380
7 | 101,830,534,280
8 | 13,283
... | ...

What? Any idea what could be going on here?

---

Dev'd a quick test...

Cargo.toml:

[package]
name = "factorial-issue"
version = "0.1.0"
edition = "2021"

[dependencies]
factorial = "0.3.0"
num = { version = "0.4.1", features = ["num-bigint"] }

src/main.rs:

use factorial::Factorial;
use num::BigUint;

fn main() {
    let k = 2_u128;

    for n in 1190_u128..=1220_u128 {
        let d = n - k;

        let n_fac = BigUint::from(n).factorial();
        let d_fac = BigUint::from(d).factorial();

        let p = n_fac.clone() / d_fac.clone();

        println!("P({n}, {k}) = {n}! / ({n} - {k})! = {n}! / {d}! = {p}");
    }
}

which prints:

P(1190, 2) = 1190! / (1190 - 2)! = 1190! / 1188! = 1414910
P(1191, 2) = 1191! / (1191 - 2)! = 1191! / 1189! = 1417290
P(1192, 2) = 1192! / (1192 - 2)! = 1192! / 1190! = 1419672
P(1193, 2) = 1193! / (1193 - 2)! = 1193! / 1191! = 1422056
P(1194, 2) = 1194! / (1194 - 2)! = 1194! / 1192! = 1424442
P(1195, 2) = 1195! / (1195 - 2)! = 1195! / 1193! = 1426830
P(1196, 2) = 1196! / (1196 - 2)! = 1196! / 1194! = 1429220
P(1197, 2) = 1197! / (1197 - 2)! = 1197! / 1195! = 1431612
P(1198, 2) = 1198! / (1198 - 2)! = 1198! / 1196! = 1434006
P(1199, 2) = 1199! / (1199 - 2)! = 1199! / 1197! = 1436402
P(1200, 2) = 1200! / (1200 - 2)! = 1200! / 1198! = 0
P(1201, 2) = 1201! / (1201 - 2)! = 1201! / 1199! = 0
P(1202, 2) = 1202! / (1202 - 2)! = 1202! / 1200! = 3
P(1203, 2) = 1203! / (1203 - 2)! = 1203! / 1201! = 4807
P(1204, 2) = 1204! / (1204 - 2)! = 1204! / 1202! = 523167862812
P(1205, 2) = 1205! / (1205 - 2)! = 1205! / 1203! = 524037634820
P(1206, 2) = 1206! / (1206 - 2)! = 1206! / 1204! = 1453230
P(1207, 2) = 1207! / (1207 - 2)! = 1207! / 1205! = 1455642
P(1208, 2) = 1208! / (1208 - 2)! = 1208! / 1206! = 0
P(1209, 2) = 1209! / (1209 - 2)! = 1209! / 1207! = 0
P(1210, 2) = 1210! / (1210 - 2)! = 1210! / 1208! = 1462890
P(1211, 2) = 1211! / (1211 - 2)! = 1211! / 1209! = 1465310
P(1212, 2) = 1212! / (1212 - 2)! = 1212! / 1210! = 1467732
P(1213, 2) = 1213! / (1213 - 2)! = 1213! / 1211! = 1212
P(1214, 2) = 1214! / (1214 - 2)! = 1214! / 1212! = 3
P(1215, 2) = 1215! / (1215 - 2)! = 1215! / 1213! = 4855
P(1216, 2) = 1216! / (1216 - 2)! = 1216! / 1214! = 22395356673661425442004249299214815912574782761274542951623296515259630626327360
P(1217, 2) = 1217! / (1217 - 2)! = 1217! / 1215! = 18432392324001173203295678435567749722283771819979047696809297543423564301504
P(1218, 2) = 1218! / (1218 - 2)! = 1218! / 1216! = 1482306
P(1219, 2) = 1219! / (1219 - 2)! = 1219! / 1217! = 1806931014
P(1220, 2) = 1220! / (1220 - 2)! = 1220! / 1218! = 1487180

So something weird going on around n = 1200...

Any help/pointers are greatly appreciated! Thanks!

[qtfkwk]

Cross posted as rust-num/num#429

[thomwiggers]

We do have a different implementation of the factorial algorithm since 0.3.0; maybe there is an error?

[thomwiggers]

Of course, the computation of n! / (n-k)! can be simplified as n * (n-1) * ... * (n-k) which is possibly much faster to compute than using the full factorial computation.

[thomwiggers]

1200 is one of the limits for crossing over implementations, so presumably we are making a mistake there.

[thomwiggers]

Tagging in @marcantoinem, who contributed the original implementation; but otherwise I need to dig into the code to and find out what is going on.

[qtfkwk]

Of course, the computation of n! / (n-k)! can be simplified as n * (n-1) * ... * (n-k) which is possibly much faster to compute than using the full factorial computation.

Good point... my use is pretty simple... can probably implement this and also take advantage of intermediate values... 🤔

[thomwiggers]

I've pushed some tests based on your example, something fishy is also definitely going on at around 37!

[marcantoinem]

I'm investigating this issue and it seem that all odds factorial that I calculated were wrong after 37 (it's were the first implementation of the prime swing is used with array) and all factorials with the other implementation over 1200 are wrong.

[marcantoinem]

I think I found the culprit, my prime swing function doesn't work as it should, I will take a bit of time to fix this. Please rollback to a version without the new implementation in the meantime.

[qtfkwk]

Confirm my quick test is now looking good following #17, #18, and upgrading to factorial 0.4.0.

Thanks for the quick response @thomwiggers and @marcantoinem!

diff --git a/Cargo.toml b/Cargo.toml
index b616e70..51e18fa 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -4,5 +4,5 @@ version = "0.1.0"
 edition = "2021"

 [dependencies]
-factorial = "0.3.0"
+factorial = "0.4.0"
 num = { version = "0.4.1", features = ["num-bigint"] }

P(1190, 2) = 1190! / (1190 - 2)! = 1190! / 1188! = 1414910
P(1191, 2) = 1191! / (1191 - 2)! = 1191! / 1189! = 1417290
P(1192, 2) = 1192! / (1192 - 2)! = 1192! / 1190! = 1419672
P(1193, 2) = 1193! / (1193 - 2)! = 1193! / 1191! = 1422056
P(1194, 2) = 1194! / (1194 - 2)! = 1194! / 1192! = 1424442
P(1195, 2) = 1195! / (1195 - 2)! = 1195! / 1193! = 1426830
P(1196, 2) = 1196! / (1196 - 2)! = 1196! / 1194! = 1429220
P(1197, 2) = 1197! / (1197 - 2)! = 1197! / 1195! = 1431612
P(1198, 2) = 1198! / (1198 - 2)! = 1198! / 1196! = 1434006
P(1199, 2) = 1199! / (1199 - 2)! = 1199! / 1197! = 1436402
P(1200, 2) = 1200! / (1200 - 2)! = 1200! / 1198! = 1438800
P(1201, 2) = 1201! / (1201 - 2)! = 1201! / 1199! = 1441200
P(1202, 2) = 1202! / (1202 - 2)! = 1202! / 1200! = 1443602
P(1203, 2) = 1203! / (1203 - 2)! = 1203! / 1201! = 1446006
P(1204, 2) = 1204! / (1204 - 2)! = 1204! / 1202! = 1448412
P(1205, 2) = 1205! / (1205 - 2)! = 1205! / 1203! = 1450820
P(1206, 2) = 1206! / (1206 - 2)! = 1206! / 1204! = 1453230
P(1207, 2) = 1207! / (1207 - 2)! = 1207! / 1205! = 1455642
P(1208, 2) = 1208! / (1208 - 2)! = 1208! / 1206! = 1458056
P(1209, 2) = 1209! / (1209 - 2)! = 1209! / 1207! = 1460472
P(1210, 2) = 1210! / (1210 - 2)! = 1210! / 1208! = 1462890
P(1211, 2) = 1211! / (1211 - 2)! = 1211! / 1209! = 1465310
P(1212, 2) = 1212! / (1212 - 2)! = 1212! / 1210! = 1467732
P(1213, 2) = 1213! / (1213 - 2)! = 1213! / 1211! = 1470156
P(1214, 2) = 1214! / (1214 - 2)! = 1214! / 1212! = 1472582
P(1215, 2) = 1215! / (1215 - 2)! = 1215! / 1213! = 1475010
P(1216, 2) = 1216! / (1216 - 2)! = 1216! / 1214! = 1477440
P(1217, 2) = 1217! / (1217 - 2)! = 1217! / 1215! = 1479872
P(1218, 2) = 1218! / (1218 - 2)! = 1218! / 1216! = 1482306
P(1219, 2) = 1219! / (1219 - 2)! = 1219! / 1217! = 1484742
P(1220, 2) = 1220! / (1220 - 2)! = 1220! / 1218! = 1487180