Add Muldiv() #110

Planxnx · 2022-02-21T23:28:59Z

(x * y) / denominator is the most common case that cannot be calculated with full precision by normal methods z.Mul(x, y).Div(z, denominator)

ex. (max_uint256 * 2)/10
an overflow occurs when you try to calculated by normal methods, but the result is smaller than max_uint256.

MulDivOverflow() is 512-bit multiplication and 512-bit by 256-bit division.
returns The 256-bit result and overflow occurred.

inspired and realworld use-case from UniswapV3
https://github.com/Uniswap/v3-core/blob/main/contracts/libraries/FullMath.sol

BenchmarkMulDivOverflow/small/uint256-8         	491599033	         2.297 ns/op	       0 B/op	       0 allocs/op
BenchmarkMulDivOverflow/div64/uint256-8         	512714014	         2.351 ns/op	       0 B/op	       0 allocs/op
BenchmarkMulDivOverflow/div128/uint256-8        	488145638	         2.415 ns/op	       0 B/op	       0 allocs/op
BenchmarkMulDivOverflow/div192/uint256-8        	484725356	         2.457 ns/op	       0 B/op	       0 allocs/op
BenchmarkMulDivOverflow/div256/uint256-8        	438809512	         2.509 ns/op	       0 B/op	       0 allocs/op
BenchmarkMulDivOverflow/small/big-8             	58039941	        20.62 ns/op	       0 B/op	       0 allocs/op
BenchmarkMulDivOverflow/div64/big-8             	58061472	        20.61 ns/op	       0 B/op	       0 allocs/op
BenchmarkMulDivOverflow/div128/big-8            	43477892	        24.84 ns/op	       1 B/op	       0 allocs/op
BenchmarkMulDivOverflow/div192/big-8            	46356553	        24.83 ns/op	       2 B/op	       0 allocs/op
BenchmarkMulDivOverflow/div256/big-8            	40076848	        28.15 ns/op	       4 B/op	       0 allocs/op

codecov · 2022-02-21T23:34:19Z

Codecov Report

Merging #110 (4db6416) into master (d97bdee) will not change coverage.
The diff coverage is 100.00%.

❗ Current head 4db6416 differs from pull request most recent head 1c0d673. Consider uploading reports for the commit 1c0d673 to get more accurate results

@@            Coverage Diff            @@
##            master      #110   +/-   ##
=========================================
  Coverage   100.00%   100.00%           
=========================================
  Files            4         4           
  Lines         1388      1396    +8     
=========================================
+ Hits          1388      1396    +8

holiman · 2022-02-22T09:09:36Z

I pushed a fuzzer to this PR, looks good so far. Also, I noticed that the fuzzer was broken, which is also fixed.

fuzz.go

Planxnx · 2022-02-22T10:30:24Z

I've optimized a bit by zero-check on the p[4:] directly instead copy to new Int.

Before

var ph Int
copy(ph[:], p[4:])
if ph.IsZero() { ... }

After
if (p[4] | p[5] | p[6] | p[7]) == 0 { ... }

BenchmarkMulDivOverflow/small/uint256-8         	474043095	         2.285 ns/op	       0 B/op	       0 allocs/op
BenchmarkMulDivOverflow/div64/uint256-8         	501923428	         2.294 ns/op	       0 B/op	       0 allocs/op
BenchmarkMulDivOverflow/div128/uint256-8        	498558622	         2.374 ns/op	       0 B/op	       0 allocs/op
BenchmarkMulDivOverflow/div192/uint256-8        	484291431	         2.404 ns/op	       0 B/op	       0 allocs/op
BenchmarkMulDivOverflow/div256/uint256-8        	441282002	         2.491 ns/op	       0 B/op	       0 allocs/op
BenchmarkMulDivOverflow/small/big-8             	58109386	        20.55 ns/op	       0 B/op	       0 allocs/op
BenchmarkMulDivOverflow/div64/big-8             	58929327	        20.56 ns/op	       0 B/op	       0 allocs/op
BenchmarkMulDivOverflow/div128/big-8            	43171965	        24.07 ns/op	       1 B/op	       0 allocs/op
BenchmarkMulDivOverflow/div192/big-8            	45164564	        24.88 ns/op	       2 B/op	       0 allocs/op
BenchmarkMulDivOverflow/div256/big-8            	41473440	        26.91 ns/op	       4 B/op	       0 allocs/op

holiman · 2022-02-22T11:58:28Z

cc @chfast would you mind taking a look?

Planxnx · 2022-03-01T17:08:00Z

@holiman Is everything okay? How long will it take?

holiman · 2022-03-07T09:00:57Z

@Planxnx just came back from a vacation, we'll get this merged soon

chfast · 2022-03-07T09:25:39Z

uint256.go

+	p := umul(x, y)
+
+	// If the multiplication is within 256 bits use Div().
+	if (p[4] | p[5] | p[6] | p[7]) == 0 {


You don't have to do it. The udivrem() will skip leading zero words itself and Div() is using udivrem() internally. So this optimization does not improve it algorithmically. My preference is too leave such optimization to at least another PR where it can be shown it improves any particular use case.

This requires a fix to udivrem() to handle case when uLen < dLen (quick return).
Benchmarks (current PR vs simplified version):

name old time/op new time/op delta MulDivOverflow/small/uint256-8 2.23ns ± 0% 2.24ns ± 1% +0.66% (p=0.000 n=9+10) MulDivOverflow/div64/uint256-8 2.25ns ± 0% 2.25ns ± 0% -0.05% (p=0.008 n=8+8) MulDivOverflow/div128/uint256-8 2.37ns ± 0% 2.36ns ± 0% -0.51% (p=0.000 n=9+9) MulDivOverflow/div192/uint256-8 2.41ns ± 0% 2.39ns ± 0% -0.64% (p=0.000 n=8+9) MulDivOverflow/div256/uint256-8 2.56ns ± 0% 2.54ns ± 0% -0.66% (p=0.000 n=8+9) MulDivOverflow/small/big-8 18.4ns ± 0% 19.0ns ± 0% +3.16% (p=0.000 n=9+10) MulDivOverflow/div64/big-8 18.4ns ± 0% 19.0ns ± 1% +3.22% (p=0.000 n=9+10) MulDivOverflow/div128/big-8 22.2ns ± 1% 22.9ns ± 1% +3.10% (p=0.000 n=10+10) MulDivOverflow/div192/big-8 23.2ns ± 1% 23.8ns ± 1% +2.78% (p=0.000 n=9+9) MulDivOverflow/div256/big-8 26.7ns ± 1% 27.4ns ± 1% +2.69% (p=0.000 n=10+10)

I've removed Div() and added a handle case where the denominator is greater than the numerator instead.

My idea is to handle this case inside udivrem(). My attempt is in #111 but we need to figure out why one of the tests fails (help welcome).

The #111 looks to be ready. Can you try to rebase on top of it and completely remove this block?

done ✅
@chfast thanks !!

uint256.go

Planxnx · 2022-03-08T12:04:25Z

@chfast I've updated the code. Can you do another review?

holiman · 2022-03-08T19:08:08Z

The last change made the code coverage from the tests drop a bit - see https://app.codecov.io/gh/holiman/uint256/compare/110/diff .

Not sure if I think the pl.Eq(d) case warrants a separate check, I would rather just remove it personally.

readme: fix typo (holiman#109)

merge master

chfast

Looks good to me with some questions around testing.

chfast · 2022-03-22T12:35:32Z

fuzz.go

-	}
-	return -1
+	switch {
+	case len(data) < 64:


Why this change?

I figured it would be better to use the input we have, rather than be too picky about the input size...?

I'm not sure this is good idea because you have unused bytes in the end of the input. They will give you exactly the same coverage path and also for all inputs giving the same coverage fuzzers prefer the shortest one and should reduce corpus entries finally. So the end result should be the same but this may be just longer route to get there.

I will experiment with two versions to see which one is faster.

chfast · 2022-03-22T12:38:14Z

fuzz.go

+	return b1.Div(b1, b4)
+}
+
+func intMulDiv(f1, f2, f3, f4 *Int) *Int {


This may be upgraded to public function in future so maybe change it to func (z *Int) mulDiv(x, y, d *Int) *Int?

Let's do that later in that case

chfast · 2022-03-22T12:41:33Z

fuzz.go

+		return fuzzTernaryOp(data) // needs 96 byte
+	}
+	// Too large input
+	return 0


This should still return -1 I believe.

Yes, you're right

Planxnx added 4 commits February 15, 2022 01:28

Implement MulDivOverflow()

b7dd2c8

update document

f3e3e6f

update benchmark

9578ea7

update document

8104520

Planxnx changed the title ~~Add Muldiv~~ Add Muldiv() Feb 21, 2022

Planxnx and others added 3 commits February 22, 2022 06:41

update authors

a015ed9

optimize for case x or y == 0

d85c389

fuzzing: add muldiv fuzzing + fix fuzzer

0ec1c9c

Planxnx added 2 commits February 22, 2022 16:55

fix benchmark opt

b71ab44

fix typo

e54c03d

holiman reviewed Feb 22, 2022

View reviewed changes

fuzz.go Outdated Show resolved Hide resolved

holiman and others added 2 commits February 22, 2022 11:24

fuzzing: doc fix

ac71671

zero-check directly

2c337f7

chfast reviewed Mar 7, 2022

View reviewed changes

Planxnx added 3 commits March 7, 2022 22:24

remove wrong optimization

5378da7

handle case denominator is greater than numerator

2472813

update func description

325f81c

Planxnx and others added 5 commits March 10, 2022 00:48

remove rarely case code

93dcd40

Merge pull request #1 from holiman/master

5b68c11

readme: fix typo (holiman#109)

Merge pull request #2 from holiman/master

7271650

merge master

Merge remote-tracking branch 'origin/master' into muldiv

98fb0f8

handle this case in udivrem instead

4db6416

chfast reviewed Mar 22, 2022

View reviewed changes

fuzz: use correct return value

1c0d673

holiman merged commit 77643b2 into holiman:master Mar 24, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Add Muldiv() #110

Add Muldiv() #110

Planxnx commented Feb 21, 2022 •

edited

codecov bot commented Feb 21, 2022 •

edited

holiman commented Feb 22, 2022

Planxnx commented Feb 22, 2022 •

edited

holiman commented Feb 22, 2022

Planxnx commented Mar 1, 2022

holiman commented Mar 7, 2022

chfast Mar 7, 2022

chfast Mar 7, 2022

Planxnx Mar 7, 2022

chfast Mar 12, 2022

chfast Mar 17, 2022

Planxnx Mar 22, 2022

Planxnx commented Mar 8, 2022

holiman commented Mar 8, 2022

chfast left a comment

chfast Mar 22, 2022

holiman Mar 24, 2022

chfast Mar 24, 2022

chfast Mar 22, 2022

holiman Mar 24, 2022

chfast Mar 22, 2022

holiman Mar 24, 2022

Add Muldiv() #110

Add Muldiv() #110

Conversation

Planxnx commented Feb 21, 2022 • edited

codecov bot commented Feb 21, 2022 • edited

Codecov Report

holiman commented Feb 22, 2022

Planxnx commented Feb 22, 2022 • edited

holiman commented Feb 22, 2022

Planxnx commented Mar 1, 2022

holiman commented Mar 7, 2022

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Planxnx commented Mar 8, 2022

holiman commented Mar 8, 2022

chfast left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Planxnx commented Feb 21, 2022 •

edited

codecov bot commented Feb 21, 2022 •

edited

Planxnx commented Feb 22, 2022 •

edited