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

math/big: replace the division with multiplicative inverse #41023

Closed
SparrowLii opened this issue Aug 25, 2020 · 10 comments
Closed

math/big: replace the division with multiplicative inverse #41023

SparrowLii opened this issue Aug 25, 2020 · 10 comments

Comments

@SparrowLii
Copy link
Contributor

SparrowLii commented Aug 25, 2020

Division is much slower than multiplication, as we know. The algorithm for dividing 128 digits by 64 digits in math/bits.go/Div64, which has a certain impact on the efficiency of nats division, requires two divisions. And the method of using multiplication by 2/1 (128bits divide 64bits )multiplicative inverse and replacing division with it can increase the speed of divWVW algorithm by three times, and at the same time increase the speed of nats division.

I have submitted a code change using 2/1 type multiplicative inverse and the corresponding benchmark data in gerrit. If possible, using a 3/2(192bits divide 128bits) type multiplicative inverse and changing the structure of nats division code will get a more obvious improvement.

@gopherbot gopherbot added this to the Proposal milestone Aug 25, 2020
@gopherbot
Copy link

Change https://golang.org/cl/250417 mentions this issue: math/big: treble the speed of divWVW and optimize the div of nats by replacing the division with multiplicative inverse

@SparrowLii SparrowLii changed the title proposal: math/bit: replace the division with multiplicative inverse proposal: math/big: replace the division with multiplicative inverse Aug 25, 2020
@randall77
Copy link
Contributor

This issue doesn't need to be a proposal. It's just an optimization - go for it.
That said, it looks like your CL is adding API to math/bits (GetInvert and DivByInv). That change would require a proposal.
Is there any way to do your change without adding API?

@SparrowLii SparrowLii changed the title proposal: math/big: replace the division with multiplicative inverse math/big: replace the division with multiplicative inverse Aug 25, 2020
@SparrowLii
Copy link
Contributor Author

This issue doesn't need to be a proposal. It's just an optimization - go for it.
That said, it looks like your CL is adding API to math/bits (GetInvert and DivByInv). That change would require a proposal.
Is there any way to do your change without adding API?

Yes there is. I added the API because I am not sure if I should completely replace the original division method. If we want to think of it as an optimization, we can use a more sophisticated method without adding an API. I will make the corresponding changes in my CL.

@SparrowLii
Copy link
Contributor Author

@randall77 Im sry that I don't know how to remove the proposal tag. I replaced the original division function, deleted the modification to the bits package and changed getInvert to internal interface so that there's no new API in bits package.

@bmkessler
Copy link
Contributor

Note that this is also the same as issue #9246 math/big: avoid DIVQ I'm not sure if the two issues should be merged or one closed.

@randall77
Copy link
Contributor

I believe they are the same issue.
(Other than the claim that it can be made faster even for a single division, which is manifestly not true for the implementation as it currently stands, as it uses a division to compute the inverse.)

@SparrowLii
Copy link
Contributor Author

@randall77 Yes, I think so. Should I close this issue?

@randall77
Copy link
Contributor

No, probably easier just put a "Fixes #9246" line in your CL description (so both will be closed when this CL lands).

@andig
Copy link
Contributor

andig commented Oct 14, 2021

CL looks done and Trybots are happy. Merge?

@ALTree
Copy link
Member

ALTree commented Oct 14, 2021

It's already merged, it just didn't have the Fixes #XXXXX line that makes the bot autoclose the issue.

@ALTree ALTree closed this as completed Oct 14, 2021
@golang golang locked and limited conversation to collaborators Jun 23, 2023
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

6 participants