1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
// uint256: Fixed size 256-bit math library
// Copyright 2020 uint256 Authors
// SPDX-License-Identifier: BSD-3-Clause
package uint256
import "math/bits"
// reciprocal2by1 computes <^d, ^0> / d.
func reciprocal2by1(d uint64) uint64 {
reciprocal, _ := bits.Div64(^d, ^uint64(0), d)
return reciprocal
}
// udivrem2by1 divides <uh, ul> / d and produces both quotient and remainder.
// It uses the provided d's reciprocal.
// Implementation ported from https://github.com/chfast/intx and is based on
// "Improved division by invariant integers", Algorithm 4.
func udivrem2by1(uh, ul, d, reciprocal uint64) (quot, rem uint64) {
qh, ql := bits.Mul64(reciprocal, uh)
ql, carry := bits.Add64(ql, ul, 0)
qh, _ = bits.Add64(qh, uh, carry)
qh++
r := ul - qh*d
if r > ql {
qh--
r += d
}
if r >= d {
qh++
r -= d
}
return qh, r
}
|
