| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | // ====================================================================== | ||
| 2 | // \title Algorithms.cpp | ||
| 3 | // \author sjsreehari | ||
| 4 | // \brief cpp file for general-purpose mathematical algorithms | ||
| 5 | // | ||
| 6 | // \copyright | ||
| 7 | // Copyright (C) 2026 California Institute of Technology. | ||
| 8 | // ALL RIGHTS RESERVED. United States Government Sponsorship | ||
| 9 | // acknowledged. | ||
| 10 | // ====================================================================== | ||
| 11 | |||
| 12 | #include <Fw/Types/Assert.hpp> | ||
| 13 | #include <Utils/Algorithms.hpp> | ||
| 14 | #include <limits> | ||
| 15 | |||
| 16 | namespace Utils { | ||
| 17 | namespace Algorithms { | ||
| 18 | |||
| 19 | 3 | FwSizeType gcd(FwSizeType a, FwSizeType b) { | |
| 20 | 3 | const FwSizeType maxIterations = static_cast<FwSizeType>(std::numeric_limits<FwSizeType>::digits) * 2; | |
| 21 |
3/4✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 5 times.
✓ Branch 3 taken 3 times.
|
8 | for (FwSizeType i = 0; (i < maxIterations) && (b != 0); i++) { |
| 22 | 5 | FwSizeType temp = b; | |
| 23 | 5 | b = a % b; | |
| 24 | 5 | a = temp; | |
| 25 | } | ||
| 26 | 3 | FW_ASSERT(b == 0); | |
| 27 | 3 | return a; | |
| 28 | } | ||
| 29 | |||
| 30 | 3 | FwSizeType lcm(FwSizeType a, FwSizeType b) { | |
| 31 | 3 | FW_ASSERT(a != 0); | |
| 32 | 3 | FW_ASSERT(b != 0); | |
| 33 | 3 | const FwSizeType g = gcd(a, b); | |
| 34 | 3 | const FwSizeType a_div_g = a / g; | |
| 35 | // Ensure that lcm will not overflow | ||
| 36 | 3 | FW_ASSERT((std::numeric_limits<FwSizeType>::max() / b) >= a_div_g, static_cast<FwAssertArgType>(a), | |
| 37 | static_cast<FwAssertArgType>(b)); | ||
| 38 | 3 | return a_div_g * b; | |
| 39 | } | ||
| 40 | |||
| 41 | } // namespace Algorithms | ||
| 42 | } // namespace Utils | ||
| 43 |