Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!gegeweb.org!de-l.enfer-du-nord.net!feeder2.enfer-du-nord.net!news-transit.tcx.org.uk!news.stack.nl!.POSTED!not-for-mail
From: Willem <willem@toad.stack.nl>
Newsgroups: comp.programming
Subject: Re: Modification to an algorithm involving factorial
Date: Fri, 19 Aug 2011 13:33:14 +0000 (UTC)
Organization: Eindhoven University of Technology
Lines: 31
Message-ID: <slrnj4spgq.240t.willem@toad.stack.nl>
References: <e33eb055-b9ee-43dd-81aa-673fe46822b6@bl1g2000vbb.googlegroups.com> <10bgb9ngoudge$.1ovhq65skxldx$.dlg@40tude.net> <5761b2c9-f879-4eb9-bc92-4f4ce58f3dae@df3g2000vbb.googlegroups.com>
NNTP-Posting-Host: toad.stack.nl
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Trace: mud.stack.nl 1313760794 91335 2001:610:1108:5010::135 (19 Aug 2011 13:33:14 GMT)
X-Complaints-To: abuse@stack.nl
NNTP-Posting-Date: Fri, 19 Aug 2011 13:33:14 +0000 (UTC)
User-Agent: slrn/0.9.9p1 (FreeBSD)
Xref: x330-a1.tempe.blueboxinc.net comp.programming:771

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