-
Notifications
You must be signed in to change notification settings - Fork 34
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
Division and modulo pass all tests #18
Merged
Merged
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
The output has been verified to be identical to that of the C language version for all files in this project by comparing the resulting .o files.
Anyway, I'm no native speaker of English and therefore the change is only a crude example for what might be added ... ;-)
…esent numbers This code has been tested with add/sub, multiplicaton and power of integer values. No tests have been performed for division and square root, yet. Numbers with fractional parts are not supported due to the missing scaling of the "scale" parameter.
This patch starts a branch exploring the possibility of using a more packed representation of digits in BcNum's. I am not sure this will work out, but it can't hurt to try, especially since Stefan was so kind to come up with a patch and send it. As of right now, the things that are known to be broken: * Printing decimal numbers * Power (seg fault)
…ctions for use in vector.c
A number of fixes and improvements ...
…results. The implementation can be changed back to a macro that accesses the array without any further computation, if the function should take non-negligible time. But the function will be inlined or optimized away in most cases and thus should not have a significant impact on the run-time ...
"shift" operations are used within all arithmetic operations "print" is a pre-requisite of generating the results file for the "parse" test
The correction is derived from the difference of the input parameter times it inverse. This value could be used for a final Newton-Raphson step (at the cost of an additional multiplication), but since we can assume that the input parameter was very near to 1.0, the multiplication would only add non-zero digits beyond the current scale range. The Goldschmidt algorithm is an infinite series of ever smaller positive values and if the series is cut off at some point, the result is known to be exact or smaller than the exact value. The correction applied is meant to compensate for the neglected series elements. If it is found that there are boundary cases where we over-compensate, then the Newton-Raphson step could be used to apply a slightly smaller correction.
After a correction is applied to the returned reciprocal to account for the finite number of elements used in teh Goldschmidt algorithm, the result should be correct without the final rounding step. While here also remove the assignment of 1 to a variable that is not used for the specific case anymore, anyway ...
It has been found to be too low e.g. when calculating l(256)/l(16) with scale=40. The result is exact with this increased correction applied.
The locations with these markers should be checked, although the tests seem to succeed wíthiut them. Currently test succeed until "reference.bc2", which returns zeroes for some of the test arrays. But these marked locations are probably not related to that test failing.
This change has been performed due to a source code analysis. No tests failed with the old code (i.e., no test covered this case).
… crashing The cut-off value is arbitrary, a significantly lower limit could be applied.
The Goldschmidt algorithm needs larger arguments than supported by the array. A larger array could be used, but a disassembly showed, that the array access was converted to an inlined and rolled out chain of comparisons and assignments.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
All division and modulo test cases pass with this version.
Maybe the scale could be reduced (for better performance) in parts of the algorithm, but for now the functionality is there. I have optimized the pow10 function by use of a look-up table. This table will be cached and the indexing faster than repetitive multiplication, IMHO. (Should be tested, but will not be significant in the overall picture, I guess.)
I have introduced a function that rounds to a given precision. This was necessary to get the division match previous results to the last relevant digit. Just cutting off excess digits gives small errors in division and modulo results.
Another new function normalizes its argument to make len == rdx (i.e. to give a value strictly less than 1 but without 0 in the uppermost BcDig of num[]). This was required for the division, which operates on "normalized" values and adjusts the position of the decimal point as a final step.
Neither of these functions has been added to num.h, since I was not sure about your policy with regard to having all static functions in num.c declared therein).