January 26, 2021, 06:11:26 AM

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

Offline 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:
  5. ; http://remus.rutgers.edu/~rhoads/Code/int_gcd.c
  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


Comments : none...

 

SimplePortal 2.3.6 © 2008-2014, SimplePortal