Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #771
| 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> (permalink) |
| 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 |
Show key headers only | 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
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