⍝ Greatest Common Divisor:

    105 gcd 330
15

    factors (3×5×7) gcd 5×7×11      ⍝ gcd: intersection of factors.
5 7

    lcm←{⍺×⍵÷⍺ gcd ⍵}               ⍝ least common multiple.

    factors (3×5×7) lcm 5×7×11      ⍝ lcm: union of factors.
3 5 7 11

    norm ← , ÷ gcd                  ⍝ simplify
    24 norm 36                      ⍝ 24/36 → 2/3.
2 3

    ¯1 0 1∘.gcd ¯1 0 1              ⍝ gcd: negative args.
1 1 1
1 0 1
1 1 1

    ¯1 0 1∘.lcm ¯1 0 1              ⍝ lcm: negative args.
 1 0 ¯1
 0 0  0
¯1 0  1

    ∧/{(1÷⍵)≡(2÷⍵)gcd 3÷⍵}¨⍳10      ⍝ gcd: non-integral args.
1
    ∧/{(6÷⍵)≡(2÷⍵)lcm 3÷⍵}¨⍳10      ⍝ lcm: non-integral args.
1

    gcds←{                          ⍝ Array-GCD.
        ⍺≡⍺+⍺:|⍵                    ⍝ all 0s: done.
        (⍺⌊⍵)∇(⍺⌊⍵)|⍺⌈⍵             ⍝ min ∇ min | max.
    }

    numbs←0 ¯1{↓4 5⍴⍺⌽⍵}¨⊂×/¨3,/sieve 2 to 80

    ↑¨numbs
┌──────────────────────────────────┬──────────────────────────────────┐
│    30    105    385   1001   2431│409457     30    105    385   1001│
│  4199   7429  12673  20677  33263│  2431   4199   7429  12673  20677│
│ 47027  65231  82861 107113 146969│ 33263  47027  65231  82861 107113│
│190747 241133 290177 347261 409457│146969 190747 241133 290177 347261│
└──────────────────────────────────┴──────────────────────────────────┘

    ↑↑gcds/numbs
   1   15   35   77  143
 221  323  437  667  899
1147 1517 1763 2021 2491
3127 3599 4087 4757 5183

    4217293152016490 gcd 1746860020068409   ⍝ largest number of iterations.
1

    bgcd←{                  ⍝ Binary gcd.
        0∊⍵:+/⍵             ⍝ either is 0:      m ? m : n
        0 0≡2|⍵:2×∇ ⍵÷2     ⍝ even even:       (∇ (m >> 1) (n >> 1)) << 1
        0 1≡2|⍵:∇ ⍵÷2 1     ⍝ even odd:         ∇ (m >> 1) n
        1 0≡2|⍵:∇ ⍵÷1 2     ⍝ odd  even:        ∇ m (n >> 1)
        ≤/⍵:∇(-\⍵)÷1 ¯2     ⍝ odd  odd: m≤n:    ∇ m (n-m >> 1)
        ∇(⌽-\⌽⍵)÷¯2 1       ⍝ odd  odd: m>n:    ∇ (m-n >> 1) n
    }

    bgcd 105 330            ⍝ takes a pair of non-negative whole numbers.
15

    bgcd¨⍉↓⍉↑↑¨numbs
   1   15   35   77  143
 221  323  437  667  899
1147 1517 1763 2021 2491
3127 3599 4087 4757 5183

⍝ This version does a better job with non-integral arguments:

    ggcd←{                          ⍝ General gcd.
        (a b)(c d)←rational¨⍺ ⍵     ⍝ rational approximations.
        lcm←{⍺×⍵÷⍺ gcd ⍵}           ⍝ least common multiple
        (a gcd c)÷b lcm d           ⍝ (see notes.rats).
    }

    (0 to 20)∘.ggcd +\10*¯1 to ¯6       ⍝ Gianluigi's example
0.1 0.11 0.111 0.1111 0.11111 0.111111
0.1 0.01 0.001 0.0001 0.00001 0.000001
0.1 0.01 0.001 0.0001 0.00001 0.000001
0.1 0.01 0.003 0.0001 0.00001 0.000003
0.1 0.01 0.001 0.0001 0.00001 0.000001
0.1 0.01 0.001 0.0001 0.00001 0.000001
0.1 0.01 0.003 0.0001 0.00001 0.000003
0.1 0.01 0.001 0.0001 0.00001 0.000007
0.1 0.01 0.001 0.0001 0.00001 0.000001
0.1 0.01 0.003 0.0001 0.00001 0.000003
0.1 0.01 0.001 0.0001 0.00001 0.000001
0.1 0.11 0.001 0.0011 0.00001 0.000011
0.1 0.01 0.003 0.0001 0.00001 0.000003
0.1 0.01 0.001 0.0001 0.00001 0.000013
0.1 0.01 0.001 0.0001 0.00001 0.000007
0.1 0.01 0.003 0.0001 0.00001 0.000003
0.1 0.01 0.001 0.0001 0.00001 0.000001
0.1 0.01 0.001 0.0001 0.00001 0.000001
0.1 0.01 0.003 0.0001 0.00001 0.000003
0.1 0.01 0.001 0.0001 0.00001 0.000001
0.1 0.01 0.001 0.0001 0.00001 0.000001

⍝∇ gcd factors rational sieve to

Back to: code

Back to: Workspaces