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

Groups > comp.programming > #759 > unrolled thread

Modification to an algorithm involving factorial

Back to article view | Back to comp.programming

Contents

  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

#759 — Modification to an algorithm involving factorial

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?

[toc] | [next] | [standalone]

#760

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

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [prev] | [next] | [standalone]

#761

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?

I'm thinking: gcd(N!, M) = M here
and so N!/(gcd(N!/M)) mod (M/M) or
N!/M mod 1, yes?

[toc] | [prev] | [next] | [standalone]

#762

On Thu, 18 Aug 2011 13:58:05 -0700 (PDT), 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?

forall K   K*M=0 mod M

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

[toc] | [prev] | [next] | [standalone]

#764

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

[toc] | [prev] | [next] | [standalone]

#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

[toc] | [prev] | [next] | [standalone]

#772

On 8/19/2011 6:33 AM, Willem wrote:
...
> 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).
...

The largest possible multiplication result is actually (M-1)^2. The
current product modulo M is no greater than M-1. For the cases in which
the calculation is needed, N is also no greater than M-1.

It may even make a difference in a few cases. For example, if M is 2^16,
a 32 bit unsigned integer can store (M-1)^2 but not M^2.

Patricia

[toc] | [prev] | [next] | [standalone]

#768

Dmitry A. Kazakov writes:
> forall N >= M    N!=0 mod M

Or rather          N==0 mod M

-- 
Hallvard

[toc] | [prev] | [next] | [standalone]

#769

Hallvard B Furuseth writes:
> Dmitry A. Kazakov writes:
>> forall N >= M    N!=0 mod M
>
> Or rather          N==0 mod M

Sigh,              N! == 0 mod M

-- 
Hallvard

[toc] | [prev] | [next] | [standalone]

#770

On 8/19/2011 1:22 AM, Hallvard B Furuseth wrote:
> Hallvard B Furuseth writes:
>> Dmitry A. Kazakov writes:
>>> forall N>= M    N!=0 mod M
>>
>> Or rather          N==0 mod M
>
> Sigh,              N! == 0 mod M
>

I thought we were writing mathematics in this thread in which case "="
is the symbol for asserting equality and "==" is meaningless. What
symbolic language uses "==" for equality, postfix "!" for factorial, and
infix "mod" for modulo?

Patricia

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web