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

Groups > comp.programming > #771

Re: Modification to an algorithm involving factorial

Show all headers | View raw

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?

Obvious.  If N >= M, then N! is a multiple of M.

Anyway, the simplest approach would be to calculate N!, and take the
M-modulo at each step.  The second-simplest would be to implement mod-M
multiplication (if M^2 is too large for your precision).


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

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