Binomial Coefficients with Large Mod

Revision en4, by sibillalazzerini, 2023-01-10 22:31:56

I have been exploring the idea of Computing Binomial Coefficients $$$\binom{n}{k} \mod m$$$ where n,k ans MOD are all 64 bit integers.ie $$$m$$$ is any integer rather than being a prime. I have found few solutions here

Tags binomial coefficients, modulus, implementations

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en69 English sibillalazzerini 2023-01-17 12:09:27 2 Tiny change: 'm$ and assing it has' -> 'm$ and assuming it has'
en68 English sibillalazzerini 2023-01-17 12:07:36 19 Tiny change: 'category. @SPyofcode might hel' -> 'category. [user:SPyofcode] might hel'
en67 English sibillalazzerini 2023-01-17 12:06:50 37 Tiny change: ' category.\n\nWhere' -> ' category. @SPyofcode might help us understand.\n\nWhere'
en66 English sibillalazzerini 2023-01-17 12:06:11 83
en65 English sibillalazzerini 2023-01-17 11:42:10 1 Tiny change: 'C) use NTTT/FFT I w' -> 'C) use NTT/FFT I w'
en64 English sibillalazzerini 2023-01-17 11:41:30 414
en63 English sibillalazzerini 2023-01-17 11:08:34 38 Tiny change: 'tor of $m$' -> 'tor of $m$ and assing it has $e_{i}=2$ or lesser'
en62 English sibillalazzerini 2023-01-17 11:03:59 74 Tiny change: 'prod_{i=pk}^{p(k+1)}(p^2+i)\ ' -> 'prod_{i=pk+1}^{p(k+1)-1}(p^2+i)\ '
en61 English sibillalazzerini 2023-01-17 10:56:30 242 Tiny change: ' $\prod_{i_1}^{t}p^2+' -> ' $\prod_{i=1}^{t}p^2+'
en60 English sibillalazzerini 2023-01-17 10:45:57 1016 Tiny change: ', $O(log{N,p})$ Time pe' -> ', $O(log{N}(p))$ Time pe'
en59 English sibillalazzerini 2023-01-12 04:36:54 29 Tiny change: 'ially for implementation and of course alternati' -> 'ially for alternati'
en58 English sibillalazzerini 2023-01-11 15:26:17 2 Tiny change: 'e alternate ideas. \' -> 'e alternative ideas. \'
en57 English sibillalazzerini 2023-01-11 13:26:30 103
en56 English sibillalazzerini 2023-01-11 13:17:44 130
en55 English sibillalazzerini 2023-01-11 13:10:29 24
en54 English sibillalazzerini 2023-01-11 13:08:31 40
en53 English sibillalazzerini 2023-01-11 13:06:15 19 Tiny change: 'hin 32-bit.\nI should' -> 'hin 32-bit(ie the fist part)\nI should'
en52 English sibillalazzerini 2023-01-11 12:50:33 73
en51 English sibillalazzerini 2023-01-11 09:31:19 7 Tiny change: 'erhaps my code was ' -> 'erhaps my edited code was '
en50 English sibillalazzerini 2023-01-11 09:29:48 52
en49 English sibillalazzerini 2023-01-11 09:27:59 38 Tiny change: 'orise $m$ and then' -> 'orise $m$ into $p_1^{e_1}p_2^{e_2}...p_t^{e_t}$ and then'
en48 English sibillalazzerini 2023-01-11 09:24:05 9 Tiny change: 'pe should scale for the f' -> 'pe should work for the f'
en47 English sibillalazzerini 2023-01-11 09:22:42 8
en46 English sibillalazzerini 2023-01-11 09:21:52 7 Tiny change: ' k!\n- if netexpo >= total exp' -> ' k!\n- if $netexpo \ge$ total exp'
en45 English sibillalazzerini 2023-01-11 09:21:21 7
en44 English sibillalazzerini 2023-01-11 09:19:58 19 Tiny change: ' all the $p_i$s from n!,' -> ' all the $ p_i $ s from n!,'
en43 English sibillalazzerini 2023-01-11 09:19:04 15 Tiny change: 'f all the factors of pi from n!, ' -> 'f all the $p_i$s from n!, '
en42 English sibillalazzerini 2023-01-11 09:18:25 166 Tiny change: '-2-mod-p2)\n\n\n- Ex' -> '-2-mod-p2) To elborate:\n\n\n- Ex'
en41 English sibillalazzerini 2023-01-11 08:59:33 4
en40 English sibillalazzerini 2023-01-11 08:58:08 60
en39 English sibillalazzerini 2023-01-11 08:54:49 1 Tiny change: 'it integer.\n\n\nHow' -> 'it integer).\n\n\nHow'
en38 English sibillalazzerini 2023-01-11 08:49:23 45
en37 English sibillalazzerini 2023-01-11 08:47:18 2 Tiny change: ' compute netexpo = total exp' -> ' compute $netexpo =$ total exp'
en36 English sibillalazzerini 2023-01-11 08:46:34 2 Tiny change: 'factorise m and then ' -> 'factorise $m$ and then '
en35 English sibillalazzerini 2023-01-11 08:46:07 2 Tiny change: 'factorise and then ' -> 'factorise m and then '
en34 English sibillalazzerini 2023-01-11 06:19:49 122
en33 English sibillalazzerini 2023-01-11 04:27:06 48
en32 English sibillalazzerini 2023-01-11 04:24:41 46
en31 English sibillalazzerini 2023-01-11 03:53:29 93
en30 English sibillalazzerini 2023-01-11 03:52:29 37
en29 English sibillalazzerini 2023-01-11 03:50:56 167
en28 English sibillalazzerini 2023-01-11 03:46:32 88
en27 English sibillalazzerini 2023-01-11 03:45:23 175
en26 English sibillalazzerini 2023-01-11 03:43:33 2
en25 English sibillalazzerini 2023-01-11 03:42:48 91
en24 English sibillalazzerini 2023-01-11 03:41:00 282
en23 English sibillalazzerini 2023-01-11 03:36:37 5 Tiny change: 'nd (n-k)! to compute ' -> 'nd (n-k)! and compute ' (published)
en22 English sibillalazzerini 2023-01-11 03:35:25 121 Tiny change: 'rse(k!) * p_1^(total ex' -> 'rse(k!) * (p_1)^(total ex' (saved to drafts)
en21 English sibillalazzerini 2023-01-11 03:26:56 426 Tiny change: 'p_{2}^e_{2+$ ... $p_t' -> 'p_{2}^e_{2}$ ... $p_t'
en20 English sibillalazzerini 2023-01-11 03:09:47 30 (published)
en19 English sibillalazzerini 2023-01-11 03:08:31 275 (saved to drafts)
en18 English sibillalazzerini 2023-01-11 03:02:29 12
en17 English sibillalazzerini 2023-01-10 23:00:16 14
en16 English sibillalazzerini 2023-01-10 22:50:13 2 Tiny change: 'problem \n- m is 6' -> 'problem \n\n- m is 6'
en15 English sibillalazzerini 2023-01-10 22:48:30 307
en14 English sibillalazzerini 2023-01-10 22:41:54 8 Tiny change: 'at I have gone thro' -> 'at I have already gone thro' (published)
en13 English sibillalazzerini 2023-01-10 22:40:52 8
en12 English sibillalazzerini 2023-01-10 22:40:16 137
en11 English sibillalazzerini 2023-01-10 22:37:49 2 Tiny change: ' k, m$ plesae do share' -> ' k, m$ please do share'
en10 English sibillalazzerini 2023-01-10 22:37:13 4 Tiny change: 'ge 64 bit mod. Just cha' -> 'ge 64 bit $m$. Just cha'
en9 English sibillalazzerini 2023-01-10 22:36:36 2 Tiny change: 'e idea of Computing B' -> 'e idea of computing B'
en8 English sibillalazzerini 2023-01-10 22:36:21 5 Tiny change: 'n,k,m$ ?\nIf any one ' -> 'n,k,m$ ?\nOr if any one '
en7 English sibillalazzerini 2023-01-10 22:36:01 113
en6 English sibillalazzerini 2023-01-10 22:34:14 18
en5 English sibillalazzerini 2023-01-10 22:33:34 232
en4 English sibillalazzerini 2023-01-10 22:31:56 65
en3 English sibillalazzerini 2023-01-10 22:31:00 147 Tiny change: 'fficients (n,k)' -> 'fficients $(n,k)$'
en2 English sibillalazzerini 2023-01-10 22:27:32 50 Tiny change: ' exploring' -> ' exploring the idea of Computing Binomial Coefficients (n,k)'
en1 English sibillalazzerini 2023-01-10 22:26:31 57 Initial revision (saved to drafts)