math/big: recognize z.Mul(x, x) as squaring of x

[griesemer]

Squaring x*x of a number x can be implemented more efficiently than general multiplication x*y. Instead of providing an additional Sqr function, recognize calls of the form z.Mul(x, x) and internally use squaring code. This will boost squaring code independent of whether an explicit square function was used or not.

[odeke-em]

Am excited to see how this will be implemented as I haven't found the internal squaring code. If am making too much noise on this thread, please let me know and I'll email you.

[gopherbot]

Change https://golang.org/cl/53638 mentions this issue: math/big: recognize z.Mul(x, x) as squaring of x

[bmkessler]

I had just had a quick go at getting this started with the above CL. I added a routine to the nat multiplication that does the schoolbook squaring with about half the multiplications, but additional bookkeeping overhead to collect, shift and add the cross products. There is some improvement for intermediate range (I'm sure the basic squaring routine I wrote could be optimized) before karatsuba multiplication is better, but there is also a hit because of the costly equality check on the arguments. I chose to put the code in nat directly so that all downstream calls would benefit, but an alternative is to push the check to recognize squaring to the types embedding nats (Int, Rat, Float) where it would just be a pointer comparison at very small cost with the necessary complication of catching and checking each instance of mul for nats.

[griesemer]

@bmkessler Thanks. Please let's do the latter: introduce a new method nat.sqr and then use a pointer comparison in Int.Mul/Rat/Float as needed. Start with Int for now (separate CLs for the others). It's a bit more code but it will not make nat.mul slower in the general case and it will make squaring faster because many additional checks can be simplified or avoided. See also my comments on the CL.

[gopherbot]

Change https://golang.org/cl/56774 mentions this issue: math/big: recognize squaring for Floats

[gopherbot]

Change https://golang.org/cl/56776 mentions this issue: math/big: use internal square for Rat

[odeke-em]

Gentle ping here, @griesemer what's left to do for this issue?

I ask because it seems like all the exported arithmetic types seem to have this recognition in as tabulated below:

Type	Done	CL	Code
Float	Yes	https://go-review.googlesource.com/c/go/+/56774	go/src/math/big/float.go Lines 1314 to 1318 in 60be6f8 if x == y { z.mant = z.mant.sqr(x.mant) } else { z.mant = z.mant.mul(x.mant, y.mant) }
Rat	Yes	https://go-review.googlesource.com/#/c/56776/	go/src/math/big/rat.go Lines 493 to 498 in 60be6f8 if x == y { // a squared Rat is positive and can't be reduced z.a.neg = false z.a.abs = z.a.abs.sqr(x.a.abs) z.b.abs = z.b.abs.sqr(x.b.abs) return z
Int	Yes	https://go-review.googlesource.com/53638	go/src/math/big/int.go Lines 156 to 160 in 60be6f8 if x == y { z.abs = z.abs.sqr(x.abs) z.neg = false return z }

[griesemer]

Thanks, @odeke-em, for looking into this. I believe Karatsuba multiplication can also be made faster if we know that we are squaring, but that's arguably a lower-level issue. I will file another issue for that and close this.