Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // algorithm from http://en.wikipedia.org/wiki/Least_common_multiple
- func lcm(a, b uint64) uint64 {
- return (a / gcd(a, b)) * b
- }
- // copied from C in http://en.wikipedia.org/wiki/Binary_GCD_algorithm
- func gcd(u, v uint64) uint64 {
- var shift uint
- switch {
- case u == 0:
- return v
- case v == 0:
- return u
- }
- for shift = 0; ((u | v) & 1) == 0; shift++ {
- u >>= 1
- v >>= 1
- }
- for (u & 1) == 0 {
- u >>= 1
- }
- for {
- for (v & 1) == 0 {
- v >>= 1
- }
- if u > v {
- t := v
- v = u
- u = t
- }
- v = v - u
- if v == 0 {
- break
- }
- }
- return u << shift
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement