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

Division and modulo pass all tests #18

Merged
merged 158 commits into from
May 6, 2019
Merged

Conversation

stesser
Copy link
Contributor

@stesser stesser commented Apr 29, 2019

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).

stesser and others added 30 commits April 19, 2019 10:06
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)
A number of fixes and improvements ...
Gavin Howard and others added 29 commits April 30, 2019 08:00
…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.
@gavinhoward gavinhoward merged commit 914a7f6 into gavinhoward:master May 6, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

2 participants