apple / swift-numerics

Advanced mathematical types and functions for Swift
Apache License 2.0
1.69k stars 147 forks source link

GCD bug fix #222

Closed NevinBR closed 2 years ago

NevinBR commented 2 years ago

The standard-library documentation for trailingZeroBitCount states:

If the value is zero, then trailingZeroBitCount is equal to bitWidth.

Thus, if T is not a fixed-width integer type, and x == 0, and y has more trailing zeros than the representation of x, then the gcd calculation will be incorrect.

In particular, the left-shift by min(xtz, ytz) == xtz will not “undo” the earlier right-shift by ytz, so the final result will be incorrectly right-shifted by ytz - xtz.

To fix this I have added an early exit when x == 0. I am not sure if this is the optimal solution, and I’m open to alternatives.


This change ensures that x != 0 at the top of the loop, so I have also converted it from a while to a repeat-while loop, in order to eliminate a redundant extra comparison on the first iteration.

I don’t know if this actually affects performance, and I’m happy to change it back if that’s preferred.

stephentyrone commented 2 years ago

@swift-ci test

stephentyrone commented 2 years ago

@swift-ci test macOS

stephentyrone commented 2 years ago

@swift-ci test