Python big integer vs. Julia big integer arithmetic

General Usage Performance
1

Here what I am wondering about:

~ $ time python -c "print( 3^100000000000 % 102 )"
91

real	0m0.030s
user	0m0.026s
sys	0m0.004s
~ $ time julia -e "println( big(3)^100000000000 % 102 )"
ERROR: OutOfMemoryError()
Stacktrace:
 [1] pow_ui!(x::BigInt, a::BigInt, b::UInt64)
   @ Base.GMP.MPZ ./gmp.jl:179
 [2] pow_ui
   @ ./gmp.jl:180 [inlined]
 [3] ^
   @ ./gmp.jl:628 [inlined]
 [4] bigint_pow(x::BigInt, y::Int64)
   @ Base.GMP ./gmp.jl:649
 [5] ^
   @ ./gmp.jl:654 [inlined]
 [6] literal_pow(f::typeof(^), x::BigInt, ::Val{100000000000})
   @ Base ./intfuncs.jl:351
 [7] top-level scope
   @ none:1

real	0m0.582s
user	0m0.530s
sys	0m0.174s

How does it come that Julia fails to work with big integers? Or did I make some mistake in the comparison?

2

That’s not the exponential operator in Python. It’s **.

4 Likes
3

And the intended computation is better done as powermod(3, 100000000000, 102) in julia.

4 Likes
4

Thanks for pointing this mistake out :slight_smile: . So the proper comparison would be:

~ $ time python -c "print( 3**10000000 % 102 )"
69

real	0m3.403s
user	0m3.382s
sys	0m0.021s
~ $ time julia -e "println( big(3)^10000000 % 102 )"
69

real	0m0.325s
user	0m0.331s
sys	0m0.117s

Showing that Julia outperforms Python by a factor of 10 on this one. … but … I made a mistake to compare this ones. The proper comparison would be:

~ $ time julia -e "println( powermod(3, 100000000000, 102) )"
69

real	0m0.312s
user	0m0.288s
sys	0m0.143s
~ $ time python -c "print( pow(3,100000000000,102) )"
69

real	0m0.033s
user	0m0.025s
sys	0m0.008s

What turns the result upside down: now Python is 10x times faster on this one … or is there some mistake in this comparison?

5 
~ $ time julia -e "println( powermod(3, 100000000000, 102) )"
69

real	0m0.312s
user	0m0.288s
sys	0m0.143s
~ $ time python -c "print( pow(3,100000000000,102) )"
69

real	0m0.033s
user	0m0.025s
sys	0m0.008s

Hmmm … on this one Python outperforms Julia by a factor of 10 … or did I some mistake as in the initial comparison?

6

You’re not measuring the integer arithmetic. Most of the time is startup of julia.

To measure the integer arithmetic, use e.g. the package BenchmarkTools.

julia> using BenchmarkTools
julia> @btime powermod(3, 100000000000, 102)

I get 184 nanoseconds. How to do such a timing in python, I don’t know.

5 Likes
7

I think a large chunk of what you’re measuring is Julia’s vs Python’s startup time, not really any computation:

% time python -c ""  
python -c ""  0.02s user 0.00s system 96% cpu 0.021 total
% time julia -e "" 
julia -e ""  0.12s user 0.04s system 111% cpu 0.142 total
7 Likes
8

Probably the same is valid for timing Python, right?
Comparison using the each language native language tools for timing in the REPL … is somehow also not really representative … because the overall time depends on the amount of operations which need to be done at once … and if the REPL is already run anyway for other purposes.

9

Certainly. Julia is quite heavy, and typically used for larger computations taking minutes to days. There is a startup time of some tenths of seconds, and compilation time, including optimizations. For this reason it’s not very well suited for simple scripting and other sub-second tasks.

4 Likes
10

It is getting really weird, doesn’t it? The Python startup time for empty string takes more than the calculation … In other words, considering the startup times Python calculates while traveling into the past … and Julia … is still behind Python:

~ $ time julia -e "println( powermod(3, 100000000000, 102) )"
69

real	0m0.316s
user	0m0.308s
sys	0m0.129s
~ $ time julia -e ""

real	0m0.195s
user	0m0.113s
sys	0m0.083s
~ $ time python -c "print( pow(3,100000000000,102) )"
69

real	0m0.025s
user	0m0.025s
sys	0m0.000s
~ $ time python -c ""

real	0m0.032s
user	0m0.022s
sys	0m0.010s
11

Not the best way but a quick builtin way to estimate in microseconds:

>>> import timeit; timeit.timeit("pow(3,100000000000,102)", number=1000000)
2.945086000021547
13

I get 854 nanoseconds in python. So julia is 4.6 times faster on this one. Is python’s pow written in python, or does it dispatch to a C-routine? Julia’s powermod is written in julia, and can be inspected by
julia> @less powermod(3,100000000000, 102)

14

You need to trust the timing … in this order of magnitude you can’t verify anymore if the result does make sense … and need to believe it does the right job. The overall timing you can observe at the shell prompt does not have this disadvantage.

15

Uh…? Is the shell’s time more trustworthy than various tools in programming languages designed for timing? Why do you think so? How come it measured longer time for doing nothing than doing something, in your above python experiment?

3 Likes
16

No it isn’t … but … with examples taking the order of one tenth to a second you can see yourself without the need to trust the numbers in the timing.

17

pow is a builtin, and like in Julia, builtins in CPython are implemented in C.

This is incorrect. Your shell prompt timing is running 1 call polluted by other hefty routines like IO and loading the session, which makes it susceptible to system variation and explains this paradoxical result:

This is the exact reason why there are dedicated timing libraries, some included in the standard library of language implementations like timeit for CPython, capable of repeating calls to account for or average out the variation.

5 Likes
18

Why should the time for doing nothing be less than time for doing something? It sure depends … the usual “logic” can’t anyway be applied to computation times. Maybe the interpreter is not optimized to process “nothing” and copes with it having trouble to arrive at valid bytecode what takes more time than straightforward translation of what is?

19

All programs have some start up time to load the necessary data into RAM, acquire resources from the OS, etc.

This is normally negligible relative to the running time of the program. However, for scripting utilities where you might need to kick off the same program over and over again from the start, this cost adds up.

Python and Julia both have runtimes that need to get started. Julia also has to spin up LLVM, its compiler, and other things that Python doesn’t.

This means Python is a better scripting language than Julia. If you need to execute your program from a cold start over and over and it doesn’t run very long, Julia is not the right tool.

But in the case of anything for which Julia is the right job, measuring start up time on a micro benchmark is a distraction.

13 Likes
20

In Maxima, one could do this:

showtime:all$
modulus:101$
rat(3)^10000000;  /* rational arithmetic package uses modular arith */
Evaluation took 0.000 seconds...    returns result 1.
to get a timing, run it in a loop...
for i:1 thru 1000 do rat(3)^10000000 ;
Evaluation took 0.0000 seconds (0.0040 elapsed) using 698.297 KB.
 now subtract off the empty loop..
(%i6)	for i:1 thru 1000 do nil;
Evaluation took 0.0000 seconds (0.0020 elapsed) using 380.984 KB.
(%o6)	done
  So it is appears to be about 0.0020 milliseconds using 317 bytes.
 (Times on 2.6GHz Intel I5)

Maxima is written mostly in Common Lisp and is primarily aimed at
symbolic math, but also supports some numerical stuff.

1 Like
21

How to calculate powmod(3, 100000, 102) using Maxima and running it from the command line getting the result printed to stdout?