Changeset 283bb9f in mainline for common/include/adt/gcdlcm.h

Timestamp:

2025-09-18T13:50:14Z (2 weeks ago)

Author:

Martin Decky <martin@…>

Branches:

master

Children:

32ae27bb

Parents:

f9c4c433

Message:

Improve the GCD/LCM implementations

Use a faster variant of the Euclid's algorithm to compute the greatest
common divisor.

Use a better variant of the least common multiple computation that
implicitly avoids overflows.

File:

• common/include/adt/gcdlcm.h (modified) (2 diffs)

common/include/adt/gcdlcm.h

@@ -42 +42 @@
         static inline type name(type a, type b) \
         { \
-                if (a == 0) \
-                        return b; \
-                 \
                 while (b != 0) { \
-                        if (a > b) \
-                                a -= b; \
-                        else \
-                                b -= a; \
+                        type remainder = a % b; \
+                        a = b; \
+                        b = remainder; \
                 } \
                  \
@@ -58 +54 @@
         static inline type name(type a, type b) \
         { \
-                return (a * b) / gcd(a, b); \
+                return (a / gcd(a, b)) * b; \
         }