Python Comparing Large Numbers

Question

How does one compare large numbers python? I have the following two numbers:

x = 99 ^ 85, y = 73 ^ 62.

Computing both numbers in the python interpreter gives the following results:

>>> x = 99 ** 85
>>> x
42559012338865490805205255842468783301592970011660094241731171697575386634867177511754750618655432231509140219114042806178869109409115320236642740915044006252790234308499
>>> y = 73 ** 62
>>> y
33575100975948386797110696048991269305533302609246066947133332393856972076850553634350302934134549900847114729991729

Even without computing the results it's quite obvious that x will be greater than y. I performed mod 1000000007 on both numbers in order to reduce the number of digits. I got the following results:

>>> mod = 1000000007
>>> x % mod
195405172
>>> y % mod
297675700
>>>

As you can see the mod results of the numbers results in y being greater than x. Is there an efficient of comparing large numbers and get the right results. I don't think this problem is bound to python alone though the context of the question is under python.

Thanks in advance

Why *shouldn't* y % mod > x % mod? Note that 19 % 10 > 98 % 10. — Scott Hunter, May 22 '18 at 15:04
@ScottHunter so the mod of a small number is sometimes greater than the mod of a large number? If this is the case, is there no efficient way of comparing large numbers? — Michael, May 22 '18 at 15:06

score 0 · Answer 1 · answered May 22 '18 at 15:17

Please see this question How does % work in Python?

Modulo give you the remainder of a number. So 4 % 10 = 4 and 14 % 10 = 4. So for directly comparing two numbers you will lose information by using modulo.
Comparing large numbers is pretty quick in python. Use ipython's %timeit to see.

%timeit (99 ** 85)>( 73 ** 62 )

On my system ( an older i7, 14 GB of ram) it took 46.3 nano seconds which is about as fast as any operation in python.

Please see the comment I've made on Dadep's answer. – Michael May 22 '18 at 15:26 — Michael, May 22 '18 at 15:26

score 0 · Answer 2 · answered May 22 '18 at 15:21

0

The 'size' of the number have a very small influence in term of execution : 'big numbers' :

>>> timeit.timeit('a=99**85; b=73**52; a>b')
0.07298588752746582

'small numbers':

>>> timeit.timeit('a=5**2; b=6**3; a>b')
0.07102680206298828

If the question is how to compare numbers in python use > and < :

>>> 5>9
False
>>> 5<9
True

answered May 22 '18 at 15:21

Dadep

2,796
5
27
40

I've limited the scope of the powers to just one power. if you were to try something like `56 ^ 67 ^ 78 ^ 90......` You'll realize things begin to slow down really quickly. – Michael May 22 '18 at 15:24
@Michael, Did you check if the time delai is due to generating number `85**69**45` or to the comparison of to large number `a – Dadep May 22 '18 at 15:32
Yes I did. It's quite fast. But increase the number of exponents to about 100 it becomes slow. It even becomes slower when you are making multiple comparisons in a list. – Michael May 22 '18 at 15:38

Python Comparing Large Numbers

2 Answers2