Commit Graph
37 Commits
Author SHA1 Message Date
Stephen Canon b3867a9155 Replace some BinaryInteger with an explicit generic parameter.
For compatibility with pre-Swift-5.7 language versions.
2023-09-28 15:31:25 -04:00
Stephen Canon 35e15a381f Additional comment fixes from Guillaume 2023-04-28 22:31:31 -04:00
Stephen CanonandGuillaume Lessard bc9f6e7368 Update Sources/IntegerUtilities/ShiftWithRounding.swift
Co-authored-by: Guillaume Lessard <glessard@users.noreply.github.com>
2023-04-28 22:29:25 -04:00
Stephen CanonandGuillaume Lessard ef6dbc6e78 Update Sources/IntegerUtilities/ShiftWithRounding.swift
Co-authored-by: Guillaume Lessard <glessard@users.noreply.github.com>
2023-04-28 22:29:13 -04:00
Stephen Canon a118de9878 Polish README.md 2023-04-28 13:58:37 -04:00
Stephen Canon 58f4e72d8a Documentation improvements. 2023-04-28 13:34:53 -04:00
Stephen Canon 8680be387b Update README.md 2023-04-27 16:30:31 -04:00
Stephen Canon f7075cc79a Add a link to BinaryInteger.init(clamping:) in the section on new saturating arithmetic API. 2023-04-27 16:27:37 -04:00
Stephen Canon fe151134b0 Further saturating arithmetic test and implementation cleanups 2023-04-27 16:19:40 -04:00
Stephen Canon f00824e9fa More tests for saturating arithmetic -- exhaustive sampling of [U]Int8 arguments. 2023-04-26 21:50:23 -04:00
Stephen Canon 4779aef990 Test coverage for saturating shift + fix the bug that it turned up. 2023-04-26 21:20:57 -04:00
Stephen Canon dbffff1ea5 Add some basic documentation. 2023-04-26 18:34:48 -04:00
Stephen Canon 7953ef315a First pass. 2023-04-26 16:43:50 -04:00
NevinBR 7f2d022d3d GCD bug fix
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.
2022-02-22 11:46:06 -05:00
Stephen Canon bfd905c9e4 Minor cleanups in integer utilities. 2021-11-03 13:53:38 -04:00
Stephen Canon f956c239e1 Merge pull request #203 from stephentyrone/rounding
Right shift and division with rounding.
2021-10-15 11:40:53 -04:00
Stephen Canon af5393445b Add note that integer utilities isn't stable yet. 2021-10-14 15:00:00 -04:00
Stephen Canon 3eaa0b3b77 Additional documentation for division/shift with rounding
Also simplifies check logic for divide with rounding, which is a modest speedup for testing.
2021-10-13 16:44:52 -04:00
Stephen Canon 710ca088d5 Renamed shifted(right:) to shifted(rightBy:). 2021-10-13 11:08:09 -04:00
Stephen Canon 501f58252a Added division with rounding operations. 2021-10-12 17:16:57 -04:00
Stephen Canon dec7339db4 Renamed RoundingMode.trap to .requireExact
Also implemented some basic statistical tests for .stochastic and reorganized code a little bit. The statistical justification of the thresholds for these tests should be explained a bit more, and we should decide on a policy in general for statistical tests that may fail sporadically, but these shouldn't be very noisy for now.
2021-09-28 11:29:10 -04:00
Stephen Canon cddd5e626d Re-arrange some things. 2021-09-26 21:54:32 -04:00
Stephen Canon 92eb76200d Cursory documentation for shifted(right:). 2021-09-26 21:43:02 -04:00
Stephen Canon eeaf9e384a More rounding mode documentation. 2021-09-26 21:24:30 -04:00
Stephen Canon d78c067765 Some documentation work. 2021-09-26 17:05:12 -04:00
Stephen Canon c124585c19 Skeleton of integer shift with rounding.
Fairly correct implementation of right-shift with rounding. Also fairly efficient, though I'm sure I'll find some cases where we're generating uncessary overflow checks upon further inspection. Nonetheless, a decent enough start.
2021-09-26 16:23:58 -04:00
Stephen Canon e22ff866a4 Add GCD files to CMake build. 2021-09-20 12:35:22 -04:00
Stephen Canon abb899865e resolve warnings in 5.5 tools build, add skeleton readme for integer utilities 2021-09-20 09:53:38 -04:00
Stephen Canon 9d84cefefa Merge pull request #189 from NevinBR/patch-6
GCD function for BinaryInteger
2021-09-10 11:04:07 -04:00
NevinBR 85264c808c Reworded doc comment for gcd 2021-09-09 23:05:45 -04:00
NevinBR 8552becf91 Documented overflow behavior of gcd 2021-08-31 11:19:22 -04:00
NevinBR 67af2fe0d9 Simplified gcd implementation 2021-08-30 17:32:03 -04:00
NevinBR b8f452189b Made gcd a free function 2021-08-30 17:28:44 -04:00
NevinBR 4fbcb11f03 Improved GCD documentation 2021-08-26 19:49:13 -04:00
Stephen Canon 996cf7f5b9 CMake build support for the IntegerUtilities module. 2021-08-26 15:18:40 -04:00
NevinBR 909a77c3d9 Create GCD.swift
Binary GCD algorithm
2021-08-26 14:51:05 -04:00
Stephen Canon 84474a3410 Initial setup of IntegerUtilities module.
Seeded with rotate(right:) and rotate(left:) on FixedWidthInteger. These implementations are basically sane, but need documentation written for users who are not already familiar with bitwise rotation.
2021-08-25 15:36:24 -04:00