Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #764

Re: Modification to an algorithm involving factorial

Show all headers | View raw

On 8/18/2011 1:58 PM, divcurl wrote:
> On Aug 18, 2:39 pm, "Dmitry A. Kazakov"<mail...@dmitry-kazakov.de>
> wrote:
>> On Thu, 18 Aug 2011 12:04:08 -0700 (PDT), divcurl wrote:
>>> So I'm changing an algorithm that involves the use of
>>> factorial to be computed as follows:
>>> N! mod M but such that overflow is a non-issue.
>>
>>> How would this be achieved?  By relying on the
>>> M residues from 0 to M-1?  But then how would
>>> one relate N! to that without actually computing it?
>>
>> forall N>= M    N!=0 mod M
>>
>
> How does that follow?

If 0 < M <= N then M is a factor of N! by definition of factorial. The
difference between 0 and N! is an integer multiple of M, so 0 and N! are
equal mod M.

What is wrong with actually computing the factorial, as long as you work
mod M? Your worst case intermediate result would be (M-1)*(M-1), so find
a number representation that can handle that. Remember you only have to
this for N < M, and any time the current product is 0 you can stop and
return 0.

Patricia

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Modification to an algorithm involving factorial divcurl <divcurl@europe.com> - 2011-08-18 12:04 -0700
  Re: Modification to an algorithm involving factorial "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2011-08-18 21:39 +0200
    Re: Modification to an algorithm involving factorial divcurl <divcurl@europe.com> - 2011-08-18 13:58 -0700
      Re: Modification to an algorithm involving factorial "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> - 2011-08-18 23:31 +0200
      Re: Modification to an algorithm involving factorial Patricia Shanahan <pats@acm.org> - 2011-08-18 15:40 -0700
      Re: Modification to an algorithm involving factorial Willem <willem@toad.stack.nl> - 2011-08-19 13:33 +0000
        Re: Modification to an algorithm involving factorial Patricia Shanahan <pats@acm.org> - 2011-08-19 07:57 -0700
    Re: Modification to an algorithm involving factorial Hallvard B Furuseth <h.b.furuseth@usit.uio.no> - 2011-08-19 10:20 +0200
      Re: Modification to an algorithm involving factorial Hallvard B Furuseth <h.b.furuseth@usit.uio.no> - 2011-08-19 10:22 +0200
        Re: Modification to an algorithm involving factorial Patricia Shanahan <pats@acm.org> - 2011-08-19 02:28 -0700

csiph-web