wu :: forums - Calculating Modulus

wu :: forums « wu :: forums - Calculating Modulus » Welcome, Guest. Please Login or Register. May 14^th, 2024, 9:21pm
RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

   wu :: forums
   riddles
   cs (Moderators: Grimbal, ThudnBlunder, towr, SMQ, Eigenray, william wu, Icarus)
   Calculating Modulus

« Previous topic | Next topic »

Pages: 1

Notify of replies

Send Topic

Author

Topic: Calculating Modulus (Read 1731 times)

Skandh
Junior Member

Gender:

Posts: 77

Calculating Modulus
« on: May 3^rd, 2011, 7:17am »

Quote

Modify

Given : X - integer > 1
Y - floating point number with fixed digits after decimal point and Y>=0

To find : X^Y%X

If Y=0 then X^Y%X=1
If 0<Y<1 then X^Y%X=X^Y
If Y=1 then X^Y%X=0
but how can we calculate result for Y>1. Is there any efficient method other than calculating X^Y and then taking modulus.

IP Logged

I wanna pull by legs!!!

Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:

Posts: 7527

Re: Calculating Modulus
« Reply #1 on: May 4^th, 2011, 8:06am »

Quote

Modify

Since Y is a float, I don't see a better way to compute X^Y than by using the logs. X^Y = exp(Y·log X).

The problem with %X is that it amplifies errors, so if you want an accurate result, depending on the size of X^Y, you might have to compute with a very high precision before taking the modulo.

X^Y%X = X·frac(X^Y-1) (frac is the fractional part, after the decimal point). So the precision you need to use for X^Y is the number of digits in X^Y-1 plus the number of significant digits you want for your result.

IP Logged

wiley
Newbie

Posts: 12

Re: Calculating Modulus
« Reply #2 on: Jun 26^th, 2011, 7:13am »

Quote

Modify

Even if Y > 1, say 1.52, the X^Y mod X should be X^.52, i.e. fractional part of Y.

Hence calculating X^Y-floor(Y) is sufficient..
Correct me if I made some silly mistake in understanding the problem..

IP Logged

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender: male

Posts: 13730

Re: Calculating Modulus
« Reply #3 on: Jun 26^th, 2011, 12:14pm »

Quote

Modify

2^1.52 ~= 2.8679105 ==> 2^1.52 % 2 ~= 0.8679105
2^0.52 ~= 1.43395525 ==> 2^0.52 % 2 ~= 1.43395525
therefor 2^1.52 % 2 != 2^0.52 % 2

So as a general rule it fails.

IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB

Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:

Posts: 7527

Re: Calculating Modulus
« Reply #4 on: Jun 27^th, 2011, 1:03am »

Quote

Modify

It is not even true with integers:
2² mod 2 = 0
2^2-floor(2) mod 2= 2⁰ mod 2 = 1.

IP Logged

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender: male

Posts: 13730

Re: Calculating Modulus
« Reply #5 on: Jun 27^th, 2011, 8:39am »

Quote

Modify

Yeah, but for positive integers it's true if instead of floor(X) you taken ceil(X)-1. Which for positive non-integer reals would be the same.

IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB

Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:

Posts: 7527

Re: Calculating Modulus
« Reply #6 on: Jun 27^th, 2011, 10:11am »

Quote

Modify

So it pretty much never works the way it was stated.

It would work for X=1, or 0<Y<1, but that was explicitly excluded...

IP Logged

wiley
Newbie

Posts: 12

Re: Calculating Modulus
« Reply #7 on: Sep 3^rd, 2011, 9:25am »

Quote

Modify

Yeah got it wrong Sad

We may need not compute X^Y by taking modulus on each multiplication with X:
Something like:
To compute 2^4.52%2,

2^.52%2 = 1.4339
1.4339 * 2 = 2.8679 - 2 = .8679
0.8679 * 2 = 1.7358
1.7358 * 2 = 3.4716 - 2 = 1.4716
1.4716 * 2 = .9432

IP Logged

Pages: 1

Notify of replies

Send Topic


« Previous topic \| Next topic »