Closed xwu closed 7 months ago
I updated dem issue with more of dem details:
Current status after this PR:
Test | Status | Comment |
---|---|---|
test_a | 🟢 Works | Test 1 from the original issue. |
test_b | 🔴 Incorrect quotient and remainder | Test 2 from the original issue. Still failing. |
test_c | 🔴 Assertion failure | New test. |
@LiarPrincess Thank you for providing more detail in the bug report regarding related edge cases!
All are now addressed in this PR.
@swift-ci test
Added test_d
and test_e
to the issue.
Current status:
Test | Status | Comment |
---|---|---|
test_a | 🟢 Works | |
test_b | 🟢 Works | |
test_c | 🟢 Works | |
test_d | 🔴 Assertion failure | New UInt256 test. |
test_e | 🔴 Assertion failure | New UInt256 test. |
EDIT:
Ooo… Interesting!
In the original issue I added the "hint" (the if self.leadingZeroBitCount == rhs.leadingZeroBitCount
thingie). Even pasting this code into DoubleWidth
will not solve test_d
and test_e
(the new tests). It seems that the error is somewhere else, but I have not debugged your code.
@LiarPrincess, have you provided all of the failing test cases in the bug report? It would be good to see all of them in one go instead of iteratively expanding the bug.
In the issue I mentioned:
Those tests come from Oh-my-decimal:
- UInt128Tests and UInt256Tests - you may need to modify them to compile with
DoubleWidth
- see "Tests" section below.- Python script to generate tests - the quality of the test cases is not that great - just some random numbers smashed together -> they will not excise edge cases for
min/max
etc. Only use unsigned types, so you have check any signed types yourself.
To run those tests on DoubleWidth
you need to:
add this inside every class:
typealias UInt128 = DoubleWidth<UInt64>
typealias UInt256 = DoubleWidth<UInt128>
typealias Word = UInt64
customize the create
method - copy from the test classes that I provided in the issue
comment the "multiply by half" section - compiler error, just comment the red squigglies.
EDIT:
I created gists, so you can just copy-paste them (note that the 2nd one is quite big):
@LiarPrincess, that's a lot of tests! Can you specifically list the failing ones in the bug report?
You can just run them: copy the code from the gist and run it. They should finish execution in ~1 second. If there is a failure then Xcode will point you to an exact line. If there is a crash then it will automatically jump into a debugger.
In the issue I added 2 examples: test_d and test_e. I hope that resolving them will make all tests pass, but since I have not debugged your code it may be possible that there is some other bug hiding in there.
Test | Status |
---|---|
UInt128 tests from gist |
🟢 Works |
UInt256 tests from gist |
🟢 Works |
I also tested DoubleWidth
in some of my projects (including the decimal thingie), and it seems to be working. Note that I only use unsigned types (UInt128/UInt256
), and I do not test edge cases (UInt128.max
= all bits 1 etc.), so some paths are still not tested. In terms of performance DoubleWidth
seems to be 25-35% slower than direct implementation.
Anyway, I confirm that this PR fully solves #272.
EDIT: CI says that if failed on Linux, but I tested it on both mac and Ubuntu, so this may be something related to CI, not to this PR. IDK.
Great, cleaned up the commit history; this is ready to go. Will update main apple/swift repo soon.
@swift-ci test
@swift-ci test
Linux test failure is a misconfiguration of CI, which I've notified Mishal of. We'll merge this as-is.
If
lhs
andrhs
have the same number of leading zero bits (and we knowrhs < lhs
), then we can't call_divide
to divide a triple-width magnitude by a double-width magnitude (this trips the assert on line 634), but rather we know that the quotient is one. Additionally, we must use>>
instead of&>>
when computing the high word because in this scenario the leading zero bits may be zero.Since it turns out there's more than one calling site for
_divide
that doesn't ensure the invariant asserted on line 634, we should actually deal with this in one place by replacing the assertion with aguard
that handles the special case.Additionally, fix a third think-o related to full-width multiplication where a carry isn't accounted for, causing unintended overflow with certain inputs.
This type now gives correct output verified for addition/subtraction/multiplication/nonzero-division-with-overflow for every pair of 16-bit unsigned integers using
DoubleWidth<DoubleWidth<UInt4>>
(with a customUInt4
implementation).Resolves https://github.com/apple/swift-numerics/issues/272