# muldiv 512x512

$$\gdef\a{\mathtt{a}} \gdef\b{\mathtt{b}}$$

Goal. Compute $$\mathtt{div512}(\a_0, \a_1, \b_0, \b_1) = \floor{\frac{\a_0 + \a_1 ⋅ 2^{256}}{\b_0 + \b_1 ⋅ 2^{256}}}$$ where all arguments are integers in the range $[0, 2^{256})$.

contract Div512 {
function div512(uint256 a0, uint256 a1, uint256 b0, uint256 b1)
internal pure returns (uint256 result)
{
if(b1 == 0) {
return div512x256(a0, a1, b0)
}
// ...
}


Here we can use Knuth's algorithm D, see for example the implementation in OpenZKP.

If $\mathtt{b}_1 = 0$ we can use the previous method, so assume $\mathtt{b}_1 ≥ 1$. In this case the high limbs bound the answer:

$$\floor{\frac {\mathtt{a}_1} {\mathtt{b}_1 + 1} } ≤ \floor{\frac {\mathtt{a}_0 + \mathtt{a}_1 ⋅ 2^{256}} {\mathtt{b}_0 + \mathtt{b}_1 ⋅ 2^{256}} } ≤ \floor{\frac {\mathtt{a}_1 + 1} {\mathtt{b}_1} }$$

So we can start by subtracting

$$a' = a - \floor{\frac {\mathtt{a}_1} {\mathtt{b}_1 + 1} } ⋅ b$$

If $a' < b$ we are done.

Remco Bloemen
Math & Engineering
https://2π.com