January 26, 2021, 06:11:26 AM

### Author Topic: [bb] Binary GCD by Entity [ 1+ years ago ]  (Read 478 times)

#### BlitzBot

• Jr. Member
• Posts: 1
##### [bb] Binary GCD by Entity [ 1+ years ago ]
« on: June 29, 2017, 12:28:39 AM »
Title : Binary GCD
Author : Entity
Posted : 1+ years ago

Description : This is a GCD (greatest common divisor) algorithm.
It tells you what the largest number is that evenly divides both given values.
A 'simpler' GCD algorithm exists (the classic Euclidean algorithm), but this version is many, many times faster.

x = GCD( 25, 10 ) ; x = 5
x = GCD( 13, 17 ) ; x = 1

Code :
Code: BlitzBasic
1. ;
2. ; Binary GCD Algorithm
3. ;
4. ; Ported from C, original source at:
6. ;
7. ; This GCD algorithm is considerably faster than the classic Euclidean version
8. ;
9. Function gcd( a, b )
10.         Local t = 0
11.         If a<=0 Then If a = 0 Then Return b: Else a = -a
12.         If b<=0 Then If b = 0 Then Return a: Else b = -b
13.
14.         While( Not( ( a Or b )And 1 ) )
15.                 a = a Shr 1
16.                 b = b Shr 1
17.                 t = t + 1
18.         Wend
19.
20.         While( Not( a And 1 ) ): a = a Shr 1: Wend
21.         While( Not( b And 1 ) ): b = b Shr 1: Wend
22.
23.         While a <> b
24.                 If a>b
25.                         a = a - b
26.                         Repeat: a = a Shr 1: Until a And 1
27.                 Else
28.                         b = b - a
29.                         Repeat: b = b Shr 1: Until b And 1
30.                 EndIf
31.         Wend
32.         Return a Shl t
33. End Function