Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

proposal: math/bits: add average of two integers #49303

Closed
jfcg opened this issue Nov 2, 2021 · 10 comments
Closed

proposal: math/bits: add average of two integers #49303

jfcg opened this issue Nov 2, 2021 · 10 comments

Comments

@jfcg
Copy link

jfcg commented Nov 2, 2021

Hi,
I am proposing to add efficient, low-level "average" functions for two signed / unsigned integers. In x86 assembly unsigned version could be written as:

add eax,ebx
rcr eax,1

Thanks..

@gopherbot gopherbot added this to the Proposal milestone Nov 2, 2021
@ianlancetaylor
Copy link
Contributor

What will these functions be called? What will their documentation be? Thanks.

@ianlancetaylor ianlancetaylor added this to Incoming in Proposals (old) Nov 2, 2021
@ianlancetaylor
Copy link
Contributor

Also, who would use them? And why not just use bits.RotateLeft?

@jfcg
Copy link
Author

jfcg commented Nov 2, 2021

They could be called Avg or Mean, and documented mathematically equivalent to floor( (a+b)/2 ). They should work for the "whole" range of signed / unsigned inputs. They can be useful to anyone who needs a mid-point basically.

@jfcg
Copy link
Author

jfcg commented Nov 2, 2021

I am not sure how to use RotateLeft for mean, can you give an example?

@ianlancetaylor
Copy link
Contributor

I mentioned RotateLeft because you mentioned the rcr instruction. But now I'm not sure why.

Doesn't the compiler already generate perfectly good code for (a+b) / 2? What do we gain by putting it in math/bits?

@jfcg
Copy link
Author

jfcg commented Nov 2, 2021

See:

package main

import "fmt"

func main() {
    var x, y int32 = 2_000_000_000, 2_100_000_000
    fmt.Println(x, y, (x+y)/2)
}

@jfcg
Copy link
Author

jfcg commented Nov 2, 2021

Btw, rcr is rotate with carry to right.

@randall77
Copy link
Contributor

We actually have an instruction like this in SSA, as it is useful for strength reducing constant division to multiplication. See Avg64u in cmd/compile/internal/ssa/gen/genericOps.go.
That said, I'm not sure how globally useful this operation is.

@jfcg
Copy link
Author

jfcg commented Nov 2, 2021

Another example:

var a, b uint32 = 4_000_000_000, 4_100_000_000
fmt.Println(a, b, (a+b)/2)

@jfcg
Copy link
Author

jfcg commented Nov 3, 2021

It seems there is a non-trivial formula for averaging two signed/unsigned integers properly. I've added them to sixb v1.3.0. Please close this issue if you dont think math/bits needs them.
Cheers..

@ianlancetaylor ianlancetaylor removed this from Incoming in Proposals (old) Nov 3, 2021
@golang golang locked and limited conversation to collaborators Nov 3, 2022
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

4 participants