System:

Kernel: 5.15.0-76-generic x86_64 bits: 64 compiler: gcc v: 11.3.0 Desktop: Xfce 4.18.1

tk: Gtk 3.24.33 wm: xfwm dm: LightDM Distro: Linux Mint 21.2 Victoria base: Ubuntu 22.04 jammy

Machine:

Type: Laptop System: LENOVO product: 20DNS01100 v: ThinkPad S3 Yoga 14

CPU:

Info: dual core model: Intel Core i5-5200U bits: 64 type: MT MCP arch: Broadwell rev: 4 cache:

L1: 128 KiB L2: 512 KiB L3: 3 MiB

Speed (MHz): avg: 2475 high: 2598 min/max: 500/2700 cores: 1: 2598 2: 2492 3: 2349 4: 2464

bogomips: 17559

Flags: avx avx2 ht lm nx pae sse sse2 sse3 sse4_1 sse4_2 ssse3

```
~ $ python3.13 -m IPython
Python 3.13.0b1 (main, May 10 2024, 12:32:10) [GCC 11.4.0]
Type 'copyright', 'credits' or 'license' for more information
IPython 8.25.0 -- An enhanced Interactive Python. Type '?' for help.
In [1]: def my_powermod(a, b, c) :
...: assert b >= 0
...: result = 1
...: a_raised_to_powers_of_two = a
...: while b != 0 :
...: if b%2 :
...: result *= a_raised_to_powers_of_two
...: result = result % c;
...: b = b >> 1
...: a_raised_to_powers_of_two = a_raised_to_powers_of_two**2 % c
...: return result
...:
```

```
In [2]: pow(3,100000000000,102)
Out[2]: 69
In [3]: my_powermod(3,100000000000,102)
Out[3]: 69
In [4]: %timeit pow(3,100000000000,102)
1.42 μs ± 44.5 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
In [5]: %timeit my_powermod(3,100000000000,102)
5.79 μs ± 92.4 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
```

```
~ $ julia
_
_ _ _(_)_ | Documentation: https://docs.julialang.org
(_) | (_) (_) |
_ _ _| |_ __ _ | Type "?" for help, "]?" for Pkg help.
| | | | | | |/ _` | |
| | |_| | | | (_| | | Version 1.10.4 (2024-06-04)
_/ |\__'_|_|_|\__'_| | Official https://julialang.org/ release
|__/ |
julia> function my_powermod(a::Int64, b::Int64, c::Int64)
@assert b >= 0
result = one(Int128)
a_raised_to_powers_of_two = convert(Int128, a)
while b != 0
if isodd(b)
result *= a_raised_to_powers_of_two
result = result % c;
end
b = b >>> 1
a_raised_to_powers_of_two = a_raised_to_powers_of_two^2 % c
end
convert(Int64, result)
end
my_powermod (generic function with 1 method)
```

```
julia> using BenchmarkTools
julia> @btime my_powermod(3,100000000000,102)
868.258 ns (0 allocations: 0 bytes)
69
julia> @btime powermod(3,100000000000,102)
1.108 μs (0 allocations: 0 bytes)
69
julia> powermod(3,100000000000,102)
69
julia> my_powermod(3,100000000000,102)
69
```