summaryrefslogtreecommitdiff
path: root/src/pkg/big
AgeCommit message (Collapse)AuthorFilesLines
2011-06-30Imported Upstream version 58upstream/58Ondřej Surý12-177/+1260
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ý3-52/+138
2011-01-17Imported Upstream version 2011.01.12upstream/2011.01.12Ondřej Surý10-738/+1041
2010-06-21big, bytes: move assembly externs to separate fileRuss Cox3-11/+19
to make it easier to build package without assembly. R=r, r2 CC=golang-dev http://codereview.appspot.com/1680045
2010-06-02big: fix spelling of EuclideanRuss Cox1-2/+2
R=gri CC=golang-dev http://codereview.appspot.com/1372042
2010-06-01big: bug fix for Quo aliasing problemRobert Griesemer2-3/+31
Fixes issue 820. R=rsc CC=golang-dev http://codereview.appspot.com/1453041
2010-05-26big: add ModInverse.Adam Langley2-0/+41
ModInverse is just a small wrapper around GcdInt, but it's nice to have in order to be clear about what one is doing in other code. R=gri, agl1 CC=golang-dev http://codereview.appspot.com/1244045
2010-05-24big: Rat test improvementsEvan Shaw1-80/+72
R=gri CC=golang-dev http://codereview.appspot.com/1270041 Committer: Robert Griesemer <gri@golang.org>
2010-05-24big: prevent errors in Exp in the face of aliasingAdam Langley3-2/+8
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 Griesemer2-3/+173
R=rsc CC=golang-dev http://codereview.appspot.com/1231044 Committer: Robert Griesemer <gri@golang.org>
2010-05-21big: Add Rat typeEvan Shaw4-1/+459
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 Griesemer2-18/+14
always return z for nat.scan R=rsc CC=golang-dev http://codereview.appspot.com/1236043
2010-05-20big: implemented Int.Binomial (to be used in test/hilbert.go with theRobert Griesemer1-9/+18
forthcoming implementation of big.Rat) R=rsc CC=golang-dev http://codereview.appspot.com/1229047 Committer: Robert Griesemer <gri@golang.org>
2010-05-19big: potential bug fix, cleanupsRobert Griesemer4-19/+61
- 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 Griesemer4-79/+234
- 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 Griesemer5-161/+142
- 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 Griesemer6-216/+183
- pass []Word instead of *Word to core arithmetic functions - remove dead code R=rsc CC=golang-dev http://codereview.appspot.com/1154042
2010-05-06fix build (typo in arith_386.s)Robert Griesemer1-1/+1
R=rsc CC=golang-dev http://codereview.appspot.com/1139042
2010-05-06big: implemented overlap-tolerant shifts in assemblyRobert Griesemer5-164/+188
- 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 Griesemer3-159/+319
- 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 Shaw4-12/+355
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 Griesemer3-63/+33
R=rsc CC=golang-dev http://codereview.appspot.com/1048041
2010-04-30big: use fast shift routinesRobert Griesemer4-44/+93
- 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/arith: assembly routines for 386 long shifts (2nd round)Robert Griesemer1-19/+16
R=rsc CC=golang-dev http://codereview.appspot.com/986044
2010-04-30fix buildRobert Griesemer1-0/+6
R=rsc CC=golang-dev http://codereview.appspot.com/1044041
2010-04-30big: improved computation of "karatsuba length" for faster multipliesRobert Griesemer3-64/+77
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-30big: assembly routines for 386 long shiftsRobert Griesemer1-32/+67
R=rsc CC=golang-dev http://codereview.appspot.com/974043
2010-04-30big: implemented core shift routines in arith.go andRobert Griesemer5-0/+134
provide assembly versions (for x86-64 for now) (Not yet used - waiting for previous CL to clear) R=rsc CC=golang-dev http://codereview.appspot.com/1040041
2010-04-27big: implemented Karatsuba multiplicationRobert Griesemer5-92/+491
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 Shaw5-310/+312
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-21big: Add some testsEvan Shaw2-6/+49
R=rsc, gri CC=golang-dev http://codereview.appspot.com/967041 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 Shaw4-56/+211
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-04-19big: Get rid of function pointers and init functionEvan Shaw4-89/+43
R=rsc, gri CC=golang-dev http://codereview.appspot.com/929041 Committer: Robert Griesemer <gri@golang.org>
2010-03-29comment typosAndrew Gerrand1-3/+3
Fixes issue 698. Fixes issue 699. R=rsc CC=golang-dev http://codereview.appspot.com/824041
2010-03-05big: fix mistakes with probablyPrimeAdam Langley2-4/+12
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-03-02gofmt: experiment: align values in map composites where possibleRobert Griesemer1-3/+3
- gofmt -w src misc - looking for feedback R=rsc, r CC=golang-dev http://codereview.appspot.com/223076
2010-01-25in C and asm, replace pkg·name with ·nameRuss Cox3-28/+28
(eliminate assumption of package global name space, make code easier to move between packages). R=r CC=golang-dev http://codereview.appspot.com/194072
2010-01-05big: fix ProbablyPrime bug, commentsRuss Cox3-4/+14
(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 Griesemer6-664/+664
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-12-09remove uses of string concatenation from src and misc directoryRobert Griesemer1-2/+2
R=rsc http://codereview.appspot.com/172041
2009-11-23go: makes it build for the case $GOROOT has whitespacesSergio Luis O. B. Correia1-2/+2
the bash scripts and makefiles for building go didn't take into account the fact $GOROOT / $GOBIN could both be directories containing whitespaces, and was not possible to build it in such a situation. this commit adjusts the various makefiles/scripts to make it aware of that possibility, and now it builds successfully when using a path with whitespaces as well. Fixes issue 115. R=rsc, dsymonds1 http://codereview.appspot.com/157067 Committer: Russ Cox <rsc@golang.org>
2009-11-20gofmt -r 'α[β:len(α)] -> α[β:]' -w src/cmd src/pkgRuss Cox2-5/+5
R=r, gri CC=golang-dev http://codereview.appspot.com/156115
2009-11-19big: fix arm build - forgot how to spell JMPRuss Cox1-7/+7
Fixes issue 269. TBR=kaib http://codereview.appspot.com/156107
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
generated by cgit v1.2.3 (git 2.39.1) at 2025-07-29 17:47:02 +0000