Bitshifting using GMP.MPZ

General Usage Performance
1

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

GMP manual

slow bitshifts…

Using GMP to convert to bytes

2

Sounds like a good PR to Base.

1 Like
3

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

1 Like
4

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

5

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

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
1 Like
6

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?

7

The calls seem to end up here:

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

Seems so.

1 Like
8

Here is my code for testing purposes

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

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

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…