# \`mul\_hi\` in Julia?
**URL:** https://discourse.julialang.org/t/mul-hi-in-julia/14235
**Category:** General Usage
**Created:** [August 29, 2018, 10:46am UTC](https://discourse.julialang.org/t/mul-hi-in-julia/14235 "2018-08-29T10:46:13Z")
**Posts on this page:** 20
**Page:** 1
### Author:  [@fjarri](https://discourse.julialang.org/u/fjarri)
#### Post date: [August 29, 2018, 10:46am UTC](https://discourse.julialang.org/t/mul-hi-in-julia/14235/1 "2018-08-29T10:46:13Z")
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.
---
### Author:  [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)
#### Post date: [August 29, 2018, 11:12am UTC](https://discourse.julialang.org/t/mul-hi-in-julia/14235/2 "2018-08-29T11:12:22Z")
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.
---
### Author:  [@fjarri](https://discourse.julialang.org/u/fjarri)
#### Post date: [August 29, 2018, 11:27am UTC](https://discourse.julialang.org/t/mul-hi-in-julia/14235/3 "2018-08-29T11:27:45Z")
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`](https://github.com/scheinerman/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.
---
### Author:  [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)
#### Post date: [August 29, 2018, 11:30am UTC](https://discourse.julialang.org/t/mul-hi-in-julia/14235/4 "2018-08-29T11:30:13Z")
What is the range of values that are to be used as the modulus when multiplying two UInt128 integers?
---
### Author:  [@fjarri](https://discourse.julialang.org/u/fjarri)
#### Post date: [August 29, 2018, 11:32am UTC](https://discourse.julialang.org/t/mul-hi-in-julia/14235/5 "2018-08-29T11:32:36Z")
Well, the whole `UInt128` range.
---
### Author:  [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)
#### Post date: [August 29, 2018, 11:37am UTC](https://discourse.julialang.org/t/mul-hi-in-julia/14235/6 "2018-08-29T11:37:05Z")
`(UInt128 * UInt128) mod UInt128` appears to fit within a UInt128.
---
### Author:  [@fjarri](https://discourse.julialang.org/u/fjarri)
#### Post date: [August 29, 2018, 11:37am UTC](https://discourse.julialang.org/t/mul-hi-in-julia/14235/7 "2018-08-29T11:37:39Z")
Sorry, I meant that the modulus can be any number from `2` to `2^128-1`.
---
### Author:  [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)
#### Post date: [August 29, 2018, 11:38am UTC](https://discourse.julialang.org/t/mul-hi-in-julia/14235/8 "2018-08-29T11:38:04Z")
that is larger than a UInt128? 🙂
---
### Author:  [@fjarri](https://discourse.julialang.org/u/fjarri)
#### Post date: [August 29, 2018, 11:39am UTC](https://discourse.julialang.org/t/mul-hi-in-julia/14235/9 "2018-08-29T11:39:02Z")
So what are those hi/lo multiplication functions for the smaller types you were talking about? I cannot locate them in the docs.
---
### Author:  [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)
#### Post date: [August 29, 2018, 11:42am UTC](https://discourse.julialang.org/t/mul-hi-in-julia/14235/10 "2018-08-29T11:42:05Z")
They are not part of Julia. Working in Julia, they can run very quickly.
I am busy today. Please check back tomorrow morning.
---
### Author:  [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)
#### Post date: [August 29, 2018, 9:05pm UTC](https://discourse.julialang.org/t/mul-hi-in-julia/14235/11 "2018-08-29T21:05:02Z")
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.
```julia
# 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
```
---
### Author:  [@fjarri](https://discourse.julialang.org/u/fjarri)
#### Post date: [August 29, 2018, 9:32pm UTC](https://discourse.julialang.org/t/mul-hi-in-julia/14235/12 "2018-08-29T21:32:50Z")
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.
---
### Author:  [@fjarri](https://discourse.julialang.org/u/fjarri)
#### Post date: [August 29, 2018, 11:01pm UTC](https://discourse.julialang.org/t/mul-hi-in-julia/14235/13 "2018-08-29T23:01:26Z")
BTW, this function hangs in an infinite loop if called as `mulmod(UInt8(2), UInt8(32), UInt8(195))`. Not sure why yet.
---
### Author:  [@JeffreySarnoff](https://discourse.julialang.org/u/JeffreySarnoff)
#### Post date: [August 29, 2018, 11:19pm UTC](https://discourse.julialang.org/t/mul-hi-in-julia/14235/14 "2018-08-29T23:19:40Z")
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)](https://github.com/JuliaLang/julia/blob/master/base/int.jl) to see how that is done.
---
### Author:  [@fjarri](https://discourse.julialang.org/u/fjarri)
#### Post date: [August 30, 2018, 2:25pm UTC](https://discourse.julialang.org/t/mul-hi-in-julia/14235/15 "2018-08-30T14:25:22Z")
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).
---
### Author:  [@rickhg12hs](https://discourse.julialang.org/u/rickhg12hs)
#### Post date: [August 30, 2018, 8:20pm UTC](https://discourse.julialang.org/t/mul-hi-in-julia/14235/16 "2018-08-30T20:20:48Z")
You may like to use or benchmark with [Nemo.jl](http://nemocas.github.io/Nemo.jl/latest/types.html). Their `nmod/NmodRing` may be of interest to you.
---
### Author:  [@fjarri](https://discourse.julialang.org/u/fjarri)
#### Post date: [August 30, 2018, 10:17pm UTC](https://discourse.julialang.org/t/mul-hi-in-julia/14235/17 "2018-08-30T22:17:08Z")
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…
---
### Author:  [@rickhg12hs](https://discourse.julialang.org/u/rickhg12hs)
#### Post date: [August 30, 2018, 11:03pm UTC](https://discourse.julialang.org/t/mul-hi-in-julia/14235/18 "2018-08-30T23:03:25Z")
Sure, glad to help.
Over a year ago, I used Julia/Nemo to implement the index calculus method for discrete logs as part of a school assignment. Once I was familiar with the package, it was a huge help.
There’s another related package, [Hecke](https://github.com/thofma/Hecke.jl), that you may find useful depending on what you’re doing.
---
### Author:  [@rickhg12hs](https://discourse.julialang.org/u/rickhg12hs)
#### Post date: [September 2, 2018, 10:19am UTC](https://discourse.julialang.org/t/mul-hi-in-julia/14235/19 "2018-09-02T10:19:40Z")
You might want to try [Suppressor](https://github.com/JuliaIO/Suppressor.jl) to selectively quiet messages.
N.B.: I haven’t tried it during Module import, etc.
---
### Author:  [@Lilith](https://discourse.julialang.org/u/Lilith)
#### Post date: [October 1, 2025, 12:05pm UTC](https://discourse.julialang.org/t/mul-hi-in-julia/14235/20 "2025-10-01T12:05:09Z")
Yes, there is! It’s is called `Base.mul_hi` as of Julia 1.13 (yet to be released)
>
>
> Move the \`\_mul\_high\` function from base/multinverses.jl to base/int.jl. Rename i…t to \`mul\_hi\`.
>
> Addresses #53855.
>
> I chose to reuse existing implementation over using the one proposed in #53855 by @LilithHafner because their performance is similar on my PC.
>
> \`\`\`julia
> \# existing
> julia\> @btime Base.MultiplicativeInverses.\_mul\_high(x, y) setup=((x,y)=(rand(UInt128),rand(UInt128)));
> 1.808 ns (0 allocations: 0 bytes)
>
> \# 53855
> julia\> @btime mul\_hi\_li2(x, y) setup=((x,y)=(rand(UInt128),rand(UInt128)));
> 1.800 ns (0 allocations: 0 bytes)
> \`\`\`
Sorry for the delay.