This week only. Pastebin PRO Accounts Christmas Special! Don't miss out!Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Sep 20th, 2012  |  syntax: Go  |  size: 0.75 KB  |  views: 37  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. // algorithm from http://en.wikipedia.org/wiki/Least_common_multiple
  2. func lcm(a, b uint64) uint64 {
  3.     return (a / gcd(a, b)) * b
  4. }
  5.  
  6. // copied from C in http://en.wikipedia.org/wiki/Binary_GCD_algorithm
  7. func gcd(u, v uint64) uint64 {
  8.     var shift uint
  9.  
  10.     switch {
  11.     case u == 0:
  12.         return v
  13.     case v == 0:
  14.         return u
  15.     }
  16.  
  17.     for shift = 0; ((u | v) & 1) == 0; shift++ {
  18.         u >>= 1
  19.         v >>= 1
  20.     }
  21.  
  22.     for (u & 1) == 0 {
  23.         u >>= 1
  24.     }
  25.  
  26.     for {
  27.         for (v & 1) == 0 {
  28.             v >>= 1
  29.         }
  30.         if u > v {
  31.             t := v
  32.             v = u
  33.             u = t
  34.         }
  35.         v = v - u
  36.  
  37.         if v == 0 {
  38.             break
  39.         }
  40.     }
  41.  
  42.     return u << shift
  43. }
clone this paste RAW Paste Data