_doomboo_'s blog

Issue with large value
By _doomboo_, history, 16 months ago, In English

I was solving this problem with a combinatoric based approach. So I compute binomial coefficient using Fermat Little Th. and modular inverse. I have correct values for N up to 34, then my code starts giving wrong values. I belive the approach is correct but there is some issue I cant figure out related to modulo, modular inverse or powmod function. Can anybody help me understanding why my code fails? CODE

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
16 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I might be wrong, but the 70'th line (ll half = nCk(n, n/2, mod)/2;) might mess your calculations up, maybe that nCk returns an odd number but you divide it by 2. I suggest using *inverse(2, mod). I haven't verified the code logic so I cannot say if the approach is correct or not. Hope this helps.

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    thank you very much, this is the actual issue. You made my day :D.

    → Reply