CHOOSE_MULTIPLIER (for integer division)

main.go

// Tool to get the constant paramaters for “Division by Invariant Integers using
// Multiplication” <https://gmplib.org/~tege/divcnst-pldi94.pdf>.
package main

import (
	"fmt"
	"math/big"
	"os"
	"strconv"
)

func main() {
	if len(os.Args) != 3 {
		os.Stderr.WriteString("need divisor integer & bit precision as arguments\n")
		os.Exit(2)
	}

	// read divisor argument
	d, ok := new(big.Int).SetString(os.Args[1], 10)
	if !ok {
		os.Stderr.WriteString("invalid divisor argument; need 128-bit integer\n")
		os.Exit(2)
	}
	fmt.Printf("> d = %d (%#x, %d-bit)\n", d, d, d.BitLen())

	// read precission argument
	prec, err := strconv.Atoi(os.Args[2])
	if err != nil || prec < 1 || prec > 128 {
		os.Stderr.WriteString("invalid bit-precision argument; need integer in range 1..128\n")
		os.Exit(2)
	}
	fmt.Printf("> prec = %d bit\n", prec)

	m_high, sh_post, l := chooseMultiplier128(d, prec)
	fmt.Printf("N = 128: m_high = %d, sh_post = %d, l = %d\n",
		m_high, sh_post, l)
}

// ChooseMultiplier128 implements the CHOOSE_MULTIPLIER routine for 128 bits
// conform figure 6.2, “Selection of multiplier and shift count”.
func chooseMultiplier128(d *big.Int, prec int) (m_high *big.Int, sh_post, l int) {
	const N = 128

	bigOne := big.NewInt(1)

	// log₂ rounded up
	l = new(big.Int).Sub(d, bigOne).BitLen()
	sh_post = l

	m_low := new(big.Int).Quo(
		new(big.Int).Lsh(bigOne, (uint)(N+l)),
		d,
	)
	m_high = new(big.Int).Quo(
		new(big.Int).Add(
			new(big.Int).Lsh(bigOne, (uint)(N+l)),
			new(big.Int).Lsh(bigOne, (uint)(N+l-prec)),
		),
		d,
	)

	for new(big.Int).Sub(new(big.Int).Rsh(m_low, 1), new(big.Int).Rsh(m_high, 1)).Sign() < 0 && sh_post > 0 {
		m_low.Rsh(m_low, 1)
		m_high.Rsh(m_high, 1)
		sh_post -= 1
	}

	return
}