# Bitshifting using GMP.MPZ

**URL:** <https://discourse.julialang.org/t/bitshifting-using-gmp-mpz/97356>\
**Category:** Performance\
**Created:** [April 11, 2023, 5:13pm UTC](https://discourse.julialang.org/t/bitshifting-using-gmp-mpz/97356 "2023-04-11T17:13:45Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![x13420x](https://avatars.discourse-cdn.com/v4/letter/x/ecc23a/32.png) [@x13420x](https://discourse.julialang.org/u/x13420x)\
**Post date:** [April 11, 2023, 5:13pm UTC](https://discourse.julialang.org/t/bitshifting-using-gmp-mpz/97356/1 "2023-04-11T17:13:45Z")

</div>

I am noticing that the GMP functions are faster that the native julia functions for example:

`Base.GMP.MPZ.gcd(a,b)` 20 percent faster

…only tried 2 values…sorry I am certain for 1000 digit numbers I will see an even larger increase because GMP has specialized algorithms(Binary GCD for large numbers is not always more effecient than normal GCD when the diference of bitlength is large…I feel like maybe there should be one modulus done before doing the Binary GCD).

`Base.GMP.MPZ.sizeinbase(a,2)` 80 percent speedup and 80 percent less memory

So my question is can I do a call to libgmp to get bitshifting on BigInts because the julia bitshifting seems somewhat slow. I believe I need to use mpz\_tdiv\_q\_2exp() looking at this post [bitshifting in C using GMP](https://stackoverflow.com/questions/67388748/how-to-properly-do-a-gmp-bit-shift)

[GMP manual](https://gmplib.org/gmp-man-6.2.1.pdf)

[slow bitshifts…](https://discourse.julialang.org/t/how-to-shift-bits-faster/19405)

[Using GMP to convert to bytes](https://discourse.julialang.org/t/bigint-to-bytes/91107/5)

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [April 11, 2023, 5:23pm UTC](https://discourse.julialang.org/t/bitshifting-using-gmp-mpz/97356/2 "2023-04-11T17:23:04Z")

</div>

Sounds like a good PR to Base.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [April 11, 2023, 5:38pm UTC](https://discourse.julialang.org/t/bitshifting-using-gmp-mpz/97356/3 "2023-04-11T17:38:57Z")

</div>

Maybe I am misunderstanding, but Base already calls `GMP.MPZ.gcd`.

---

<div class="post-metadata">

**Author:** ![x13420x](https://avatars.discourse-cdn.com/v4/letter/x/ecc23a/32.png) [@x13420x](https://discourse.julialang.org/u/x13420x)\
**Post date:** [April 11, 2023, 6:36pm UTC](https://discourse.julialang.org/t/bitshifting-using-gmp-mpz/97356/4 "2023-04-11T18:36:53Z")

</div>

These are 2 expamples of where calling GMP gets a performance boost…I am assuming that using the bitshift from GMP would be a performance increase also…the problem with the bigint gcd seems to be that it is not doing a modulus before doing the binary gcd…If I choose numbers with similar bit lengths the there is only a 5 or 10 percent gain by using GMP and the timing of the bigint gcd stays the same even though one of the bigger number decreased in size

[Native julia gcd](https://github.com/JuliaLang/julia/blob/master/base/intfuncs.jl)

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [April 11, 2023, 7:50pm UTC](https://discourse.julialang.org/t/bitshifting-using-gmp-mpz/97356/5 "2023-04-11T19:50:40Z")

</div>

I beg your pardon, but can you demonstrate this difference? Unless I misunderstand, Julia _does_ use GMP, so the difference is zero.

```julia
julia> @edit gcd(big"10", big"20")

# Binary ops
for (fJ, fC) in ((:+, :add), (:-,:sub), (:*, :mul),
                 (:mod, :fdiv_r), (:rem, :tdiv_r),
                 (:gcd, :gcd), (:lcm, :lcm),
                 (:&, :and), (:|, :ior), (:xor, :xor))
    @eval begin
        ($fJ)(x::BigInt, y::BigInt) = MPZ.$fC(x, y)
    end
end

```

---

<div class="post-metadata">

**Author:** ![x13420x](https://avatars.discourse-cdn.com/v4/letter/x/ecc23a/32.png) [@x13420x](https://discourse.julialang.org/u/x13420x)\
**Post date:** [April 11, 2023, 8:48pm UTC](https://discourse.julialang.org/t/bitshifting-using-gmp-mpz/97356/6 "2023-04-11T20:48:03Z")

</div>

Yeah you are correct…it seemed faster because I was calling it for the fourth time(unknowingly) and the compiler was doing further optimizations…I guess…or because of pipelining…So does bitshifting use GMP?

Does it always call GMP for gcd?

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [April 11, 2023, 9:13pm UTC](https://discourse.julialang.org/t/bitshifting-using-gmp-mpz/97356/7 "2023-04-11T21:13:07Z")

</div>

> [@x13420x](#):
>
> So does bitshifting use GMP?

The calls seem to end up here:

```julia
>>(x::BigInt, c::UInt) = c == 0 ? x : MPZ.fdiv_q_2exp(x, c)

```

> [@x13420x](#):
>
> Does it always call GMP for gcd?

Seems so.

---

<div class="post-metadata">

**Author:** ![x13420x](https://avatars.discourse-cdn.com/v4/letter/x/ecc23a/32.png) [@x13420x](https://discourse.julialang.org/u/x13420x)\
**Post date:** [April 11, 2023, 10:49pm UTC](https://discourse.julialang.org/t/bitshifting-using-gmp-mpz/97356/8 "2023-04-11T22:49:53Z")

</div>

> [@DNF](#):
>
> `MPZ.fdiv_q_2exp(x, c)`

Here is my code for testing purposes

```julia
function gcdmodified(a, b)
    while b!=ZERO
        zb = trailing_zeros(b)
        #b>>=zb    
        b=Base.GMP.MPZ.fdiv_q_2exp(b,zb)
        #if zb>2
            #b>>=zb
           # b=Base.GMP.MPZ.fdiv_q_2exp(b,zb)
        #end
        #println("( $a , $b , $zb )")  
         b,a = rem(a, b),b
    end
    a
end

```

Here is using b\>\>=zb

![image](https://global.discourse-cdn.com/julialang/original/3X/1/3/137f04062bfb7abfaae9d39229e828e296037d94.png)

and using b=Base.GMP.MPZ.fdiv\_q\_2exp(b,zb) which not sure why it uses 50 percent more memory. Do I need to do modulus to keep the memory down or maybe thats why its faster because its not truncating the zeros to the left. For the leftshift it might be more crucial to do the modulus? The real gain in speed seems around 15 or 20 percent but its still interesting.

![image](https://global.discourse-cdn.com/julialang/original/3X/4/2/4230ecc067c6e0eb414284e04e6a5d7749d87b1c.png)

my real code only bitshifts when zb is over a certain value because often its not worth it to do the bitshift…with this speedup I think I could do the bit shift when its 2 or over…

This Lshifts b by 2 … `Base.GMP.MPZ.mul_2exp(b,2)` The problem maybe is doubling the memory allocation everytime…not sure…also not sure if leftshift gives speedup like right shift…

**UPDATE: There seems to be no real difference in calling GMP directly to do bitshifts…**