# Python big integer vs. Julia big integer arithmetic
**URL:** https://discourse.julialang.org/t/python-big-integer-vs-julia-big-integer-arithmetic/115777
**Category:** Performance
**Tags:** python
**Created:** [June 17, 2024, 9:39pm UTC](https://discourse.julialang.org/t/python-big-integer-vs-julia-big-integer-arithmetic/115777 "2024-06-17T21:39:43Z")
**Posts on this page:** 20
**Page:** 1
### Author:  [@oOosys](https://discourse.julialang.org/u/oOosys)
#### Post date: [June 17, 2024, 9:39pm UTC](https://discourse.julialang.org/t/python-big-integer-vs-julia-big-integer-arithmetic/115777/1 "2024-06-17T21:39:43Z")
Here what I am wondering about:
```julia
~ $ 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?
---
### Author:  [@greatpet](https://discourse.julialang.org/u/greatpet)
#### Post date: [June 17, 2024, 9:42pm UTC](https://discourse.julialang.org/t/python-big-integer-vs-julia-big-integer-arithmetic/115777/2 "2024-06-17T21:42:11Z")
> [@oOosys](#):
>
> `~ $ time python -c "print( 3^100000000000 % 102 )"`
That’s not the exponential operator in Python. It’s `**`.
---
### Author:  [@sgaure](https://discourse.julialang.org/u/sgaure)
#### Post date: [June 17, 2024, 9:44pm UTC](https://discourse.julialang.org/t/python-big-integer-vs-julia-big-integer-arithmetic/115777/3 "2024-06-17T21:44:20Z")
> [@oOosys](#):
>
> `3^100000000000`
And the intended computation is better done as `powermod(3, 100000000000, 102)` in julia.
---
### Author:  [@oOosys](https://discourse.julialang.org/u/oOosys)
#### Post date: [June 17, 2024, 9:47pm UTC](https://discourse.julialang.org/t/python-big-integer-vs-julia-big-integer-arithmetic/115777/4 "2024-06-17T21:47:59Z")
> [@greatpet](#):
>
> That’s not the exponential operator in Python. It’s `**`.
Thanks for pointing this mistake out 🙂 . So the proper comparison would be:
```julia
~ $ 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:
```julia
~ $ 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?
---
### Author:  [@oOosys](https://discourse.julialang.org/u/oOosys)
#### Post date: [June 17, 2024, 9:59pm UTC](https://discourse.julialang.org/t/python-big-integer-vs-julia-big-integer-arithmetic/115777/5 "2024-06-17T21:59:02Z")
> [@sgaure](#):
>
> powermod(3, 100000000000, 102)
```julia
~ $ 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?
---
### Author:  [@sgaure](https://discourse.julialang.org/u/sgaure)
#### Post date: [June 17, 2024, 10:02pm UTC](https://discourse.julialang.org/t/python-big-integer-vs-julia-big-integer-arithmetic/115777/6 "2024-06-17T22:02:33Z")
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
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.
---
### Author:  [@giordano](https://discourse.julialang.org/u/giordano)
#### Post date: [June 17, 2024, 10:07pm UTC](https://discourse.julialang.org/t/python-big-integer-vs-julia-big-integer-arithmetic/115777/7 "2024-06-17T22:07:51Z")
> [@oOosys](#):
>
> What turns the result upside down: now **Python is 10x times faster** on this one … or is there some mistake in this comparison?
I think a large chunk of what you’re measuring is Julia’s vs Python’s startup time, not really any computation:
```console
% 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
```
---
### Author:  [@oOosys](https://discourse.julialang.org/u/oOosys)
#### Post date: [June 17, 2024, 10:08pm UTC](https://discourse.julialang.org/t/python-big-integer-vs-julia-big-integer-arithmetic/115777/8 "2024-06-17T22:08:27Z")
> [@sgaure](#):
>
> You’re not measuring the integer arithmetic. Most of the time is startup of julia.
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.
---
### Author:  [@sgaure](https://discourse.julialang.org/u/sgaure)
#### Post date: [June 17, 2024, 10:14pm UTC](https://discourse.julialang.org/t/python-big-integer-vs-julia-big-integer-arithmetic/115777/9 "2024-06-17T22:14:13Z")
> [@oOosys](#):
>
> Probably the same is valid for timing Python, right?
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.
---
### Author:  [@oOosys](https://discourse.julialang.org/u/oOosys)
#### Post date: [June 17, 2024, 10:16pm UTC](https://discourse.julialang.org/t/python-big-integer-vs-julia-big-integer-arithmetic/115777/10 "2024-06-17T22:16:43Z")
> [@giordano](#):
>
> I think a large chunk of what you’re measuring is Julia’s vs Python’s startup time, not really any computation
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:
```julia
~ $ 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
```
---
### Author:  [@Benny](https://discourse.julialang.org/u/Benny)
#### Post date: [June 17, 2024, 10:17pm UTC](https://discourse.julialang.org/t/python-big-integer-vs-julia-big-integer-arithmetic/115777/11 "2024-06-17T22:17:48Z")
Not the best way but a quick builtin way to estimate in microseconds:
```julia
>>> import timeit; timeit.timeit("pow(3,100000000000,102)", number=1000000)
2.945086000021547
```
---
### Author:  [@sgaure](https://discourse.julialang.org/u/sgaure)
#### Post date: [June 17, 2024, 10:24pm UTC](https://discourse.julialang.org/t/python-big-integer-vs-julia-big-integer-arithmetic/115777/13 "2024-06-17T22:24:01Z")
> [@Benny](#):
>
> `import timeit; timeit.timeit("pow(3,100000000000,102)", number=1000000)`
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)`
---
### Author:  [@oOosys](https://discourse.julialang.org/u/oOosys)
#### Post date: [June 17, 2024, 10:24pm UTC](https://discourse.julialang.org/t/python-big-integer-vs-julia-big-integer-arithmetic/115777/14 "2024-06-17T22:24:45Z")
> [@Benny](#):
>
> ```julia
> import timeit; timeit.timeit("pow(3,100000000000,102)", number=1000000)
> 2.945086000021547
>
> ```
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.
---
### Author:  [@sgaure](https://discourse.julialang.org/u/sgaure)
#### Post date: [June 17, 2024, 10:26pm UTC](https://discourse.julialang.org/t/python-big-integer-vs-julia-big-integer-arithmetic/115777/15 "2024-06-17T22:26:01Z")
> [@oOosys](#):
>
> 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.
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?
---
### Author:  [@oOosys](https://discourse.julialang.org/u/oOosys)
#### Post date: [June 17, 2024, 10:37pm UTC](https://discourse.julialang.org/t/python-big-integer-vs-julia-big-integer-arithmetic/115777/16 "2024-06-17T22:37:44Z")
> [@sgaure](#):
>
> Uh…? Is the shell’s `time` more trustworthy than various tools in programming languages designed for timing?
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.
---
### Author:  [@Benny](https://discourse.julialang.org/u/Benny)
#### Post date: [June 17, 2024, 10:38pm UTC](https://discourse.julialang.org/t/python-big-integer-vs-julia-big-integer-arithmetic/115777/17 "2024-06-17T22:38:26Z")
> [@sgaure](#):
>
> Is python’s `pow` written in python, or does it dispatch to a C-routine?
`pow` is a builtin, and like in Julia, builtins in CPython are implemented in C.
> [@oOosys](#):
>
> The overall timing you can observe at the shell prompt does not have this disadvantage.
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:
> [@sgaure](#):
>
> How come it measured longer time for doing nothing than doing something, in your above python experiment?
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.
---
### Author:  [@oOosys](https://discourse.julialang.org/u/oOosys)
#### Post date: [June 17, 2024, 10:43pm UTC](https://discourse.julialang.org/t/python-big-integer-vs-julia-big-integer-arithmetic/115777/18 "2024-06-17T22:43:05Z")
> [@sgaure](#):
>
> How come it measured longer time for doing nothing than doing something, in your above python experiment?
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?
---
### Author:  [@mrufsvold](https://discourse.julialang.org/u/mrufsvold)
#### Post date: [June 17, 2024, 11:31pm UTC](https://discourse.julialang.org/t/python-big-integer-vs-julia-big-integer-arithmetic/115777/19 "2024-06-17T23:31:18Z")
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.
---
### Author:  [@rfateman](https://discourse.julialang.org/u/rfateman)
#### Post date: [June 19, 2024, 3:34am UTC](https://discourse.julialang.org/t/python-big-integer-vs-julia-big-integer-arithmetic/115777/20 "2024-06-19T03:34:05Z")
In Maxima, one could do this:
```julia
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.
---
### Author:  [@oOosys](https://discourse.julialang.org/u/oOosys)
#### Post date: [June 19, 2024, 8:17am UTC](https://discourse.julialang.org/t/python-big-integer-vs-julia-big-integer-arithmetic/115777/21 "2024-06-19T08:17:06Z")
> [@rfateman](#):
>
> In Maxima, one could do this:
How to calculate `powmod(3, 100000, 102)` using Maxima and running it from the command line getting the result printed to stdout?
[Next page](https://discourse.julialang.org/t/python-big-integer-vs-julia-big-integer-arithmetic/115777.md?page=2)