summaryrefslogtreecommitdiff
path: root/src/pkg/big/nat.go
AgeCommit message (Collapse)AuthorFilesLines
2011-09-13Imported Upstream version 60upstream/60Ondřej Surý1-0/+1272
2011-09-13Imported Upstream version 60Ondřej Surý1-1320/+0
2011-08-03Imported Upstream version 59upstream/59Ondřej Surý1-2/+2
2011-06-30Imported Upstream version 58upstream/58Ondřej Surý1-76/+282
2011-04-28Imported Upstream version 2011.04.27upstream/2011.04.27Ondřej Surý1-5/+5
2011-04-26Imported Upstream version 2011.04.13upstream/2011.04.13Ondřej Surý1-0/+47
2011-01-17Imported Upstream version 2011.01.12upstream/2011.01.12Ondřej Surý1-13/+11
2010-05-24big: prevent errors in Exp in the face of aliasingAdam Langley1-0/+5
R=gri CC=golang-dev, golang-dev http://codereview.appspot.com/1244044
2010-05-21test/hilbert.go: convert to test case and benchmark for big.RatRobert Griesemer1-3/+0
R=rsc CC=golang-dev http://codereview.appspot.com/1231044 Committer: Robert Griesemer <gri@golang.org>
2010-05-21big: Add Rat typeEvan Shaw1-0/+2
Implementations are pretty rough and simple at this point, but it's a start. R=gri CC=golang-dev http://codereview.appspot.com/1250043 Committer: Robert Griesemer <gri@golang.org>
2010-05-21big: fix Int.SetString comment, simplify implementation,Robert Griesemer1-1/+1
always return z for nat.scan R=rsc CC=golang-dev http://codereview.appspot.com/1236043
2010-05-19big: potential bug fix, cleanupsRobert Griesemer1-13/+17
- implemented setWord, use it where setUint64 is wrong - divLarge: use fast mulWW, divWW; implemented mulWW, divWW - better assembly code for addMulVVW R=rsc CC=golang-dev http://codereview.appspot.com/1258042
2010-05-18big: bug fix for divisionRobert Griesemer1-2/+7
Fixes issue 784. R=rsc CC=golang-dev http://codereview.appspot.com/1196043
2010-05-15big: implemented format support for fmt library, MulRangeRobert Griesemer1-17/+20
- support for binary prefix 0b (to match fmt.Format) - renamed nat.new -> nat.setUint64 for consistency - more tests R=r CC=golang-dev http://codereview.appspot.com/1233041 Committer: Robert Griesemer <gri@golang.org>
2010-05-08big: cleanups and performance tuningRobert Griesemer1-60/+45
- removed last argument (n) from all core arithmetic routines; instead, use the length of the result - simplified nat.make implementation and chose a better capacity for new values, removed a TODO in the process Changing the constant e from 1 (old) to 4 (new) improved pidigits -s -n 10000 by ~9% (on a 3.06GHz Intel Core 2 Duo): user 0m3.882s (old) user 0m3.549s (new) R=rsc CC=golang-dev http://codereview.appspot.com/1133043
2010-05-07big: more cleanupRobert Griesemer1-28/+28
- pass []Word instead of *Word to core arithmetic functions - remove dead code R=rsc CC=golang-dev http://codereview.appspot.com/1154042
2010-05-06big: implemented overlap-tolerant shifts in assemblyRobert Griesemer1-78/+24
- no need to make copies in cases of aliases - removed deprecated internal shift functions - minor unrelated simplifications This change improves pidigits -s -n10000 by almost 20%: user 0m6.156s (old) user 0m4.999s (new) (pidigits -s -n20000 goes from ~25s to ~19s) R=rsc CC=golang-dev http://codereview.appspot.com/1149041
2010-05-03big: completed set of Int division routines & cleanupsRobert Griesemer1-4/+4
- renamed Len -> BitLen, simplified implementation - renamed old Div, Mod, DivMod -> Que, Rem, QuoRem - implemented Div, Mod, DivMod (Euclidian definition, more useful in a mathematical context) - fixed a bug in Exp (-0 was possible) - added extra tests to check normalized results everywhere - uniformly set Int.neg flag at the end of computations - minor cosmetic cleanups - ran all tests R=rsc CC=golang-dev http://codereview.appspot.com/1091041
2010-05-03big: fix memory corruption in nat.shrRuss Cox1-1/+1
R=gri CC=golang-dev http://codereview.appspot.com/1084041
2010-05-03big: Add bitwise methods for IntEvan Shaw1-1/+76
R=gri CC=golang-dev http://codereview.appspot.com/987041 Committer: Robert Griesemer <gri@golang.org>
2010-05-01big: cleanup and removal of redundant functionalityRobert Griesemer1-53/+10
R=rsc CC=golang-dev http://codereview.appspot.com/1048041
2010-04-30big: use fast shift routinesRobert Griesemer1-9/+53
- fixed a couple of bugs in the process (shift right was incorrect for negative numbers) - added more tests and made some tests more robust - changed pidigits back to using shifts to multiply by 2 instead of add This improves pidigit -s -n 10000 by approx. 5%: user 0m6.496s (old) user 0m6.156s (new) R=rsc CC=golang-dev http://codereview.appspot.com/963044
2010-04-30big: improved computation of "karatsuba length" for faster multipliesRobert Griesemer1-11/+19
This results in an improvement of > 35% for the existing Mul benchmark using the same karatsuba threshold, and an improvement of > 50% with a slightly higher threshold (32 instead of 30): big.BenchmarkMul 500 6731846 ns/op (old alg.) big.BenchmarkMul 500 4351122 ns/op (new alg.) big.BenchmarkMul 500 3133782 ns/op (new alg., new theshold) Also: - tweaked calibrate.go, use same benchmark as for Mul benchmark R=rsc CC=golang-dev http://codereview.appspot.com/1037041
2010-04-27big: implemented Karatsuba multiplicationRobert Griesemer1-59/+292
Plus: - calibration "test" - include in tests with gotest -calibrate - basic Mul benchmark - extra multiplication tests - various cleanups This change improves multiplication speed of numbers >= 30 words in length (current threshold; found empirically with calibrate): The multiplication benchmark (multiplication of a variety of long numbers) improves by ~35%, individual multiplies can be significantly faster. gotest -benchmarks=Mul big.BenchmarkMul 500 6829290 ns/op (w/ Karatsuba) big.BenchmarkMul 100 10600760 ns/op There's no impact on pidigits for -n=10000 or -n=20000 because the operands are are too small. R=rsc CC=golang-dev http://codereview.appspot.com/1004042 Committer: Robert Griesemer <gri@golang.org>
2010-04-22big: Create type natEvan Shaw1-132/+134
Changed most of the functions in nat.go to methods on nat. R=gri CC=golang-dev http://codereview.appspot.com/976041 Committer: Robert Griesemer <gri@golang.org>
2010-04-20big: fix build - start with zero in scanNRuss Cox1-1/+1
R=gri, eds CC=golang-dev http://codereview.appspot.com/947042
2010-04-20big: eliminate redundant array lookupsEvan Shaw1-5/+11
This gives about a 6% performance improvement to pidigits. Thanks to Russ for the suggestion. R=rsc, gri CC=golang-dev http://codereview.appspot.com/957041 Committer: Russ Cox <rsc@golang.org>
2010-04-20big: reduce the number of allocationsEvan Shaw1-4/+10
There was a bug in makeN that caused lots of unnecessary allocations. Fixing this exposed a few bugs in other functions which worked when makeN allocated a new slice, but failed when it simply resized an existing slice. The result is a pretty big performance improvement. When running pidigits, here were the numbers I got on amd64: Before this change: pidigits 10000 gcc -O2 pidigits.c -lgmp 2.09u 0.02s 2.11r gc pidigits 12.68u 0.04s 12.72r gc_B pidigits 12.71u 0.03s 12.75r After: pidigits 10000 gcc -O2 pidigits.c -lgmp 2.09u 0.00s 2.10r gc pidigits 6.82u 0.00s 6.85r gc_B pidigits 6.55u 0.01s 6.59r R=rsc, gri CC=golang-dev http://codereview.appspot.com/953042 Committer: Russ Cox <rsc@golang.org>
2010-04-20big: Add Lsh and Value; convert pidigits to use bigEvan Shaw1-12/+15
This yields a pretty significant performance boost to pidigits and there are still some improvements to be made. Here are my numbers: amd64 w/ bignum: pidigits 10000 gcc -O2 pidigits.c -lgmp 2.10u 0.00s 2.10r gc pidigits 22.92u 0.02s 22.97r gc_B pidigits 22.62u 0.00s 22.65r amd64 w/ big: pidigits 10000 gcc -O2 pidigits.c -lgmp 2.09u 0.02s 2.11r gc pidigits 12.68u 0.04s 12.72r gc_B pidigits 12.71u 0.03s 12.75r 386 w/ bignum: pidigits 10000 gcc -O2 pidigits.c -lgmp 2.09u 0.00s 2.09r gc pidigits 44.30u 0.01s 44.35r gc_B pidigits 44.29u 0.03s 44.35r 386 w/ big: pidigits 10000 gcc -O2 pidigits.c -lgmp 2.10u 0.00s 2.10r gc pidigits 22.70u 0.06s 22.79r gc_B pidigits 22.80u 0.09s 22.91r R=rsc, gri CC=golang-dev http://codereview.appspot.com/881050 Committer: Russ Cox <rsc@golang.org>
2010-03-05big: fix mistakes with probablyPrimeAdam Langley1-2/+7
probablyPrime would return false negatives in some cases. This code has now been tested against GMP for several million iterations without issues. Fixes issue 638. R=rsc CC=golang-dev http://codereview.appspot.com/252041
2010-01-05big: fix ProbablyPrime bug, commentsRuss Cox1-3/+6
(changes adopted from alc, agl) R=agl1, agl CC=golang-dev http://codereview.appspot.com/181137
2009-12-15 1) Change default gofmt default settings forRobert Griesemer1-176/+176
parsing and printing to new syntax. Use -oldparser to parse the old syntax, use -oldprinter to print the old syntax. 2) Change default gofmt formatting settings to use tabs for indentation only and to use spaces for alignment. This will make the code alignment insensitive to an editor's tabwidth. Use -spaces=false to use tabs for alignment. 3) Manually changed src/exp/parser/parser_test.go so that it doesn't try to parse the parser's source files using the old syntax (they have new syntax now). 4) gofmt -w src misc test/bench 1st set of files. R=rsc CC=agl, golang-dev, iant, ken2, r http://codereview.appspot.com/180047
2009-11-20gofmt -r 'α[β:len(α)] -> α[β:]' -w src/cmd src/pkgRuss Cox1-2/+2
R=r, gri CC=golang-dev http://codereview.appspot.com/156115
2009-11-18big: fix large division.Adam Langley1-13/+19
I missed a case. R=rsc, agl CC=golang-dev http://codereview.appspot.com/156092
2009-11-11Reland a112249da741, this time with missing file.Adam Langley1-11/+300
2009-11-11roll back 3985: build is brokenRuss Cox1-300/+11
TBR=agl1 CC=golang-dev http://codereview.appspot.com/154065
2009-11-11big:Adam Langley1-11/+300
Turn methods that don't store the result in their receiver into functions in order to preserve the convention. Re-jig Exp and Div by moving their guts into nat.go. Add ProbablyPrime to perform Miller-Rabin primality tests. crypto/rsa: reenable key generation since we now have ProbablyPrime. R=gri CC=go-dev http://codereview.prom.corp.google.com/1024038
2009-11-10minor adjustments to package comments for better synopsis.Robert Griesemer1-2/+2
R=rsc CC=r http://go/go-review/1026038
2009-11-09- replaced gofmt expression formatting algorithm withRobert Griesemer1-20/+20
rsc's algorithm - applied gofmt -w misc src - partial CL (remaining files in other CLs) R=rsc, r http://go/go-review/1024040
2009-11-09remove semis after statements in one-statement statement listsRobert Griesemer1-44/+44
R=rsc, r http://go/go-review/1025029
2009-11-06- fine-tuning of one-line func heuristic (nodes.go)Robert Griesemer1-3/+1
- enabled for function declarations (not just function literals) - applied gofmt -w $GOROOT/src (look for instance at src/pkg/debug/elf/elf.go) R=r, rsc CC=go-dev http://go/go-review/1026006
2009-11-05gofmt'ed bigRobert Griesemer1-4/+4
R=agl http://go/go-review/1022003
2009-11-05big: add Div, Mod, Exp, GcdExt and several other fixes.Adam Langley1-1/+118
R=gri, rsc CC=go-dev http://go/go-review/1017036
2009-10-06apply gofmt to the LGTM-marked files from 34501Russ Cox1-20/+28
that have not changed since I applied gofmt. R=gri DELTA=456 (77 added, 3 deleted, 376 changed) OCL=35378 CL=35383
2009-09-01added "Under construction" to package commentRobert Griesemer1-0/+2
R=rsc DELTA=2 (2 added, 0 deleted, 0 changed) OCL=34196 CL=34199
2009-08-26cleanups before making larger changesRobert Griesemer1-4/+13
R=rsc DELTA=113 (10 added, 30 deleted, 73 changed) OCL=33877 CL=33882
2009-08-18- fix performance bug (makeN always allocated a new vector)Robert Griesemer1-2/+6
- removed defs.go (moved declarations into arith.go where they belong) R=r DELTA=40 (16 added, 20 deleted, 4 changed) OCL=33464 CL=33464
2009-08-18- implemented MultiplicationRobert Griesemer1-24/+40
- changed Cmp to return -1, 0, +1 - added corresponding test cases R=rsc DELTA=173 (136 added, 3 deleted, 34 changed) OCL=33431 CL=33459
2009-08-17- rename files to match the data types they implement, adusted MakefileRobert Griesemer1-0/+331
- no other changes R=r DELTA=1248 (623 added, 623 deleted, 2 changed) OCL=33371 CL=33371
generated by cgit v1.2.3 (git 2.39.1) at 2025-07-27 23:52:13 +0000