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

Open
SparrowLii opened this issue Aug 25, 2020 · 8 comments
Open

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

SparrowLii opened this issue Aug 25, 2020 · 8 comments
Assignees
Milestone

Comments

@SparrowLii
Copy link
Contributor

@SparrowLii 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

@gopherbot gopherbot commented Aug 25, 2020

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

@randall77 randall77 commented Aug 25, 2020

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

@SparrowLii SparrowLii commented Aug 25, 2020

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 SparrowLii closed this Aug 26, 2020
@SparrowLii SparrowLii reopened this Aug 26, 2020
@SparrowLii
Copy link
Contributor Author

@SparrowLii SparrowLii commented Aug 26, 2020

@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

@bmkessler bmkessler commented Sep 1, 2020

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

@randall77 randall77 commented Sep 1, 2020

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

@SparrowLii SparrowLii commented Sep 2, 2020

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

@randall77
Copy link
Contributor

@randall77 randall77 commented Sep 2, 2020

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
4 participants