# `mul_hi` in Julia?

Is there some way to get the higher bits of the result of multiplying two integers (of the same type) in Julia? Something that’s usually called `mul_hi` or `mulhi` in assembly languages. Of course, one could implement it by splitting the arguments into hi/lo halves, or translating to larger integers/`BigInt`s, but a native way (if one exists) would probably be faster.

There is more than one way. Please tell me what you want to do with those higher bits. If you want to obtain the product of two 16, 32 or 64 bit integers as a pair (higher order bits, lower order bits) of 16, 32 or 64 bit integers, we have that.

I want to implement some modulo multiplication algorithms for `UInt128` integers (by the way, if there’s already an implementation for that, I’d be grateful for a link — so far I’ve only seen `Mods.jl` which assumes the multiplication result always fits in the chosen integer type).

If you want to obtain the product of two 16, 32 or 64 bit integers as a pair (higher order bits, lower order bits) of 16, 32 or 64 bit integers, we have that.

I’d be interested in that as well.

What is the range of values that are to be used as the modulus when multiplying two UInt128 integers?

Well, the whole `UInt128` range.

`(UInt128 * UInt128) mod UInt128` appears to fit within a UInt128.

Sorry, I meant that the modulus can be any number from `2` to `2^128-1`.

that is larger than a UInt128? So what are those hi/lo multiplication functions for the smaller types you were talking about? I cannot locate them in the docs.

They are not part of Julia. Working in Julia, they can run very quickly.
I am busy today. Please check back tomorrow morning.

This version benchmarks well and works with all bits used.

I find it not all that visually pleasing, though. A reworking of the organization and determination of subsidiary conditionals would be helpful to have.

``````# adapted from
# https://stackoverflow.com/questions/12168348

isone(x::T) where {T<:Real} = one(T) === x

function mulmod(a::T, b::T, modby::T) where {T<:Unsigned}
(iszero(a) || isone(b)) && return a
(iszero(b) || isone(a)) && return b

result  = zero(T)
onlymsb =  xor(~result, ~result >> one(T))

a = a % modby
b = b % modby

while !iszero(b)
if isodd(b)
result = result + a
if result < a || result >= modby
result = result - modby
end
end

t = a
a = a << 1
if a < t || a >= modby
a = a - modby
end
b = b >> 1
end

return result
end
``````
2 Likes

Thanks, Jeffrey, I’ll benchmark your method against my implementations (when they’re ready). The thing is, the original question was about a non-modulo `mulhi`, which is required for various modulus multiplication algorithms, namely for the ones operating on large integers combined out of multiple smaller ones. For instance, while I can use this algorithm for `UInt128`, I can’t use it for, say, 256-bit or larger integers, for which there’s no corresponding Julia (or CPU) type - that’s where I need `mulhi` in some form and Montgomery or Barrett reduction.

BTW, this function hangs in an infinite loop if called as `mulmod(UInt8(2), UInt8(32), UInt8(195))`. Not sure why yet.

Its because the originally cited code is not correct when `modby` has its most significant bit set. I have replaced it with another implementation from that thread.

Search for `widemul` in Julia’s own source (int.jl) to see how that is done.

1 Like

Thanks for the corrections, and `widemul` is exactly the function I was looking for (or, rather, one of the implementations in `int.jl` that can be adapted for `UInt128` values).

1 Like

You may like to use or benchmark with Nemo.jl. Their `nmod/NmodRing` may be of interest to you.

Thanks, for some reason I didn’t find it when I looked for modulo arithmetic in google. Their implementation is indeed slightly faster than mine The only problem is their obnoxious disclaimer that shows up on every import…