`mul_hi` in Julia?

General Usage
1

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/BigInts, but a native way (if one exists) would probably be faster.

2

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.

3

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.

4

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

5

Well, the whole UInt128 range.

6

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

7

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

8

that is larger than a UInt128? :slight_smile:

9

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

10

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

11

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
12

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.

13

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

14

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
15

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
16

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

17

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 :slight_smile: The only problem is their obnoxious disclaimer that shows up on every import…

18

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, that you may find useful depending on what you’re doing.

19

You might want to try Suppressor to selectively quiet messages.

N.B.: I haven’t tried it during Module import, etc.