Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(190)

Issue 1004042: code review 1004042: big: implemented Karatsuba multiplication (Closed)

Can't Edit
Can't Publish+Mail
Start Review
Created:
9 years, 10 months ago by gri
Modified:
1 week, 3 days ago
Reviewers:
rsc1, adonovan
CC:
rsc, golang-dev
Visibility:
Public.

Description

big: implemented Karatsuba multiplication Plus: - basic Fact benchmark - extra multiplication tests - some unrelated cleanups This improves performance of 1e5! by almost a factor of 2 (largest multiply has > 500000bit operands) gotest -benchmarks=Fact big.BenchmarkFact 5 329760400 ns/op big.BenchmarkFact 5 651693600 ns/op (w/o Karatsuba) There's no impact on pidigits for -n=10000 or -n=20000 because the multiplies are too small. At the moment Karatsuba multiplies kick in if both operands have at least 256 words (16384bits on a 64bit machine); this can probably be improved quite a bit.

Patch Set 1 #

Patch Set 2 : code review 1004042: big: implemented Karatsuba multiplication #

Patch Set 3 : code review 1004042: big: implemented Karatsuba multiplication #

Total comments: 22

Patch Set 4 : code review 1004042: big: implemented Karatsuba multiplication #

Patch Set 5 : code review 1004042: big: implemented Karatsuba multiplication #

Total comments: 1

Patch Set 6 : code review 1004042: big: implemented Karatsuba multiplication #

Patch Set 7 : code review 1004042: big: implemented Karatsuba multiplication #

Patch Set 8 : code review 1004042: big: implemented Karatsuba multiplication #

Patch Set 9 : code review 1004042: big: implemented Karatsuba multiplication #

Patch Set 10 : code review 1004042: big: implemented Karatsuba multiplication #

Total comments: 10

Patch Set 11 : code review 1004042: big: implemented Karatsuba multiplication #

Patch Set 12 : code review 1004042: big: implemented Karatsuba multiplication #

Patch Set 13 : code review 1004042: big: implemented Karatsuba multiplication #

Patch Set 14 : code review 1004042: big: implemented Karatsuba multiplication #

Patch Set 15 : code review 1004042: big: implemented Karatsuba multiplication #

Total comments: 1

Patch Set 16 : code review 1004042: big: implemented Karatsuba multiplication #

Total comments: 2
Unified diffs Side-by-side diffs Delta from patch set Stats (+491 lines, -92 lines) Patch
A src/pkg/big/calibrate_test.go View 13 14 15 1 chunk +91 lines, -0 lines 0 comments Download
M src/pkg/big/int.go View 1 2 3 4 5 6 3 chunks +3 lines, -3 lines 0 comments Download
M src/pkg/big/int_test.go View 1 2 3 4 5 5 chunks +47 lines, -30 lines 0 comments Download
M src/pkg/big/nat.go View 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 26 chunks +292 lines, -59 lines 2 comments Download
M src/pkg/big/nat_test.go View 1 2 3 4 5 6 7 8 9 10 1 chunk +58 lines, -0 lines 0 comments Download

Messages

Total messages: 14
gri
Hello rsc (cc: golang-dev@googlegroups.com), I'd like you to review this change.
9 years, 10 months ago (2010-04-25 23:37:48 UTC) #1
rsc
Have you measured where the crossover is to sanity check the choice of 256? Does ...
9 years, 10 months ago (2010-04-25 23:44:29 UTC) #2
rsc
On Sun, Apr 25, 2010 at 16:44, Russ Cox <rsc@golang.org> wrote: > Have you measured ...
9 years, 10 months ago (2010-04-25 23:47:04 UTC) #3
rsc1
Very neat. http://codereview.appspot.com/1004042/diff/6001/7003 File src/pkg/big/nat.go (right): http://codereview.appspot.com/1004042/diff/6001/7003#newcode228 src/pkg/big/nat.go:228: const karatsubaThreshold = 245 CL desc says ...
9 years, 10 months ago (2010-04-26 04:40:07 UTC) #4
gri
On Sun, Apr 25, 2010 at 4:47 PM, Russ Cox <rsc@golang.org> wrote: > On Sun, ...
9 years, 10 months ago (2010-04-26 04:41:08 UTC) #5
gri
I also updated the CL description (removed Int.Fact). http://codereview.appspot.com/1004042/diff/6001/7001 File src/pkg/big/int.go (right): http://codereview.appspot.com/1004042/diff/6001/7001#newcode320 src/pkg/big/int.go:320: // ...
9 years, 10 months ago (2010-04-26 05:32:39 UTC) #6
gri
Hello rsc (cc: golang-dev@googlegroups.com), I'd like you to review this change.
9 years, 10 months ago (2010-04-27 03:41:02 UTC) #7
rsc1
LGTM http://codereview.appspot.com/1004042/diff/28001/29001 File src/pkg/big/calibrate.go (right): http://codereview.appspot.com/1004042/diff/28001/29001#newcode5 src/pkg/big/calibrate.go:5: // The calibrate package computes the Karatsuba threshold. ...
9 years, 10 months ago (2010-04-27 06:15:42 UTC) #8
gri
PTAL. http://codereview.appspot.com/1004042/diff/28001/29001 File src/pkg/big/calibrate.go (right): http://codereview.appspot.com/1004042/diff/28001/29001#newcode5 src/pkg/big/calibrate.go:5: // The calibrate package computes the Karatsuba threshold. ...
9 years, 10 months ago (2010-04-28 00:22:07 UTC) #9
rsc1
http://codereview.appspot.com/1004042/diff/25004/28002 File src/pkg/big/calibrate_test.go (right): http://codereview.appspot.com/1004042/diff/25004/28002#newcode53 src/pkg/big/calibrate_test.go:53: x[i] = makeNumber(n * (i + 1)) I still ...
9 years, 10 months ago (2010-04-28 02:08:12 UTC) #10
rsc1
LGTM
9 years, 10 months ago (2010-04-28 02:15:03 UTC) #11
gri
*** Submitted as http://code.google.com/p/go/source/detail?r=b75b37bee7ee *** big: implemented Karatsuba multiplication Plus: - calibration "test" - include ...
9 years, 10 months ago (2010-04-28 02:16:12 UTC) #12
adonovan
https://codereview.appspot.com/1004042/diff/23004/src/pkg/big/nat.go File src/pkg/big/nat.go (right): https://codereview.appspot.com/1004042/diff/23004/src/pkg/big/nat.go#newcode461 src/pkg/big/nat.go:461: func (z nat) mulRange(a, b uint64) nat { What's ...
2 weeks, 2 days ago (2020-02-12 14:46:30 UTC) #13
gri
1 week, 3 days ago (2020-02-19 00:51:25 UTC) #14
Message was sent while issue was closed.
https://codereview.appspot.com/1004042/diff/23004/src/pkg/big/nat.go
File src/pkg/big/nat.go (right):

https://codereview.appspot.com/1004042/diff/23004/src/pkg/big/nat.go#newcode461
src/pkg/big/nat.go:461: func (z nat) mulRange(a, b uint64) nat {
On 2020/02/12 14:46:30, adonovan wrote:
> What's the purpose of treating the sequence as leaves of a binary tree and
doing
> recursive pairwise additions, instead of using a simple loop? It's the same
> number of multiplications, but I would expect the loop to allocate much fewer
> temporary variables.

The recursive approach appears faster in practice - even w/o Karatsuba. I'm not
100% clear why (I found this empirically and accidentally), but I believe it it
because there is less "internal fragmentation": While the product is getting
bigger and bigger in a loop-based implementation, one factor slowly moves from a
to b and typically is "small" even for a 64bit int - i.e., in each
multiplication step only a few bits (of the 64 bits) of that factor contribute
to the multiplication in each iteration. In contrast, in a recursive approach,
all "inner" digits of a large operand are 64bits in width, thus requiring fewer
multiplications overall. One could probably measure this by counting the 64bit
multiplications required in either case.

If we have Karatsuba, the effect should become even bigger, because in each
multiplication we have two more or less equally sized factors which lend
themselves to Karatsuba multiplication (if they are big enough). In the
iterative approach, one factor is always small (at most 64bits) and thus
Karatsuba won't even kick in.
Sign in to reply to this message.

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b