Calculating wrong modulus manually

[sfaisalawan]

BPO	28021
Nosy	@stevendaprano, @zhangyangyu

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2016-09-08.16:14:46.346>
created_at = <Date 2016-09-08.14:21:07.826>
labels = ['type-bug', 'invalid']
title = 'Calculating wrong modulus manually'
updated_at = <Date 2016-09-08.16:14:46.324>
user = 'https://bugs.python.org/sfaisalawan'

bugs.python.org fields:

activity = <Date 2016-09-08.16:14:46.324>
actor = 'steven.daprano'
assignee = 'none'
closed = True
closed_date = <Date 2016-09-08.16:14:46.346>
closer = 'steven.daprano'
components = []
creation = <Date 2016-09-08.14:21:07.826>
creator = 'sfaisalawan'
dependencies = []
files = []
hgrepos = []
issue_num = 28021
keywords = []
message_count = 3.0
messages = ['275015', '275019', '275057']
nosy_count = 3.0
nosy_names = ['steven.daprano', 'xiang.zhang', 'sfaisalawan']
pr_nums = []
priority = 'normal'
resolution = 'not a bug'
stage = None
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue28021'
versions = ['Python 3.5']

[sfaisalawan]

Hi,

when I calculate (11**19)%23 it gives me 15 but when I try to do the same operation manually it give a totally different result which is 1395.

>>> 11**19
61159090448414546291
>>> (11**19)%23
15
>>> a=11**19
>>> a
61159090448414546291
>>> b=23
>>> c=int(a/b)
>>> c
2659090889061501952
>>> d=b*c
>>> d
61159090448414544896
>>> e=a-d
>>> e
1395

[zhangyangyu]

You should use a//b instead of int(a/b).

>>> 11**19 - 11**19//23*23
15
>>> 11**19 - int(11**19/23)*23
1395

[stevendaprano]

That is because of floating point rounding.

When you calculate a/23, the result is the approximate float 2.659090889061502e+18 instead of the exact integer result 2659090889061502012. Converting to an int gives you a result which is too small:

py> a = 11**19
py> a - (a//23)*23 # calculate modulus with no rounding error
15
py> a - int(a/23)*23 # introduces rounding error
1395
py> a/23
2.659090889061502e+18
py> int(a/23)
2659090889061501952
py> int(a/23) - a//23
-60

By the way, are you aware of the third argument to pow()?

py> pow(11, 19, 23)
15