[MarekKnapek]

On division: There is a paper about a division algorithm. If you split your 128bit integer into four 32bit integers, you can use a 64bit CPU built-in instruction to do the 128bit division. If you are on 32bit CPU that doesn't have the 32bit division operation, then split your 128bit number into 8 16bit integers and leverage the 32bit CPU built-in operation. https://surface.syr.edu/eecs_techreports/166/

[Joker_vD]

And having a CPU with "128-by-64" or "64-by-32" division instruction (such as x86/x64) simplifies the algorithm even further.

    Inputs: uint[128] N, uint[128] D
    Outputs: uint[128] Q, uint[128] R
        such that Q ≤ N, R < D, and N = Q * D + R
    Uses: (uint[64] quot, uint[64] rem) hw_divmod(uint[128] dividend, uint[64] divisor)

    if D.high = 0:
        # long division; quotient can be 128-bit wide, but remainder will fit in 64 bits
        uint[192] N' := N ≪ lzcnt(D.low)
        uint[64] D' := D ≪ lzcnt(D.low)
        uint[64] Q', uint[64] R' := hw_divmod(N'.high ≪ 64 + N'.mid, D')
        uint[64] Q'', uint[64] R'' := hw_divmod(R' ≪ 64 + N'.low, D')
        Q := Q' ≪ 64 + Q''
        R := R'' ≫ lzcnt(D.low)
    else:
        # Quotient will fit in 64 bits, but remainder could be 128-bits wide
        uint[192] N' := N ≪ lzcnt(D.high)
        uint[128] D' := D ≪ lzcnt(D.high)
        uint[64] Q', uint[64] R' := hw_divmod(N'.high ≪ 64 + N'.mid, D'.high)
        uint[128] R'' := R' ≪ 64 + N'.low
        uint[128] T := Q' * D'.low
        if R'' < T:
            Q := Q' - 1
            R := D' + R'' - T
        else:
            Q := Q'
            R := R'' - T
        R := R ≫ lzcnt(D.high)

[rramadass]

What is the notation used? Seems like some-sort of pseudocode but is it something specific?

[Joker_vD]

It's pseudocode. A mix of Python's block structure, C's style of variable introduction, and Pascal's use of ":=" for assignment and "=" for equality. Oh, and assigning to output variables instead of explicit return is from Go, although the tradition is much older, of course.

As for using "'" in variable names, can't recall from the top of my head what language it's from (I don't think it's Lisp), but something does that.

[rramadass]

Nice, that's what i noticed; I rather like its clean structure.

But since it was put together by you/not-you, does it have a name and is it used as a Specification/IR/DSL language somewhere (since you gave the algorithm in it) ?