hamming.a68
1 COMMENT
2
3 @section Synopsis
4
5 Compute regular (or Hamming) numbers.
6
7 Regular numbers have prime factors 2, 3, and 5 only. These numbers appear in
8 several areas of mathematics and have different names in different areas of
9 study. They have for example a role in number theory and in computer science
10 where regular numbers are often called Hamming numbers, after Richard Hamming
11 who proposed the problem of finding algorithms for generating these numbers
12 in ascending order. This program is one such algorithm.
13
14 After the program published on Rosetta Code by Marcel van der Veer.
15
16 COMMENT
17
18 PR precision=100 PR
19
20 MODE SERIES = FLEX [0] UNT, # Initially, no elements #
21 UNT = LONG LONG INT; # A 100-digit unsigned integer #
22
23 PROC hamming number = (INT n) UNT: # The n-th Hamming number #
24 CASE n
25 IN 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 # First 10 in a table #
26 OUT # Additional operators #
27 OP MIN = (INT i, j) INT: (i < j | i | j), MIN = (UNT i, j) UNT: (i < j | i | j);
28 PRIO MIN = 9;
29 OP LAST = (SERIES h) UNT: h[UPB h]; # Last element of a series #
30 OP +:= = (REF SERIES s, UNT elem) VOID:
31 # Extend a series by one element, only keep the elements you need #
32 (INT lwb = (i MIN j) MIN k, upb = UPB s;
33 sweep heap;
34 REF SERIES new s = HEAP FLEX [lwb : upb + 1] UNT;
35 (new s[lwb : upb] := s[lwb : upb], new s[upb + 1] := elem);
36 s := new s
37 );
38 # Determine the n-th hamming number iteratively #
39 SERIES h := 1, # Series, initially one element #
40 UNT m2 := 2, m3 := 3, m5 := 5, # Multipliers #
41 INT i := 1, j := 1, k := 1; # Counters #
42 TO n - 1
43 DO h +:= (m2 MIN m3) MIN m5;
44 (LAST h = m2 | m2 := 2 * h[i +:= 1]);
45 (LAST h = m3 | m3 := 3 * h[j +:= 1]);
46 (LAST h = m5 | m5 := 5 * h[k +:= 1])
47 OD;
48 LAST h
49 ESAC;
50
51 FOR k FROM 10 BY 10 TO 90
52 DO print ((whole (k, 0), " = ", whole (hamming number (k), 0), new line))
53 OD
54
55 CO Only for machines with ample RAM!
56
57 FOR k FROM 100 BY 100 TO 900
58 DO print ((whole (k, 0), " = ", whole (hamming number (k), 0), new line))
59 OD;
60
61 FOR k FROM 1000 BY 1000 TO 3000
62 DO sweep heap;
63 print ((whole (k, 0), " = ", whole (hamming number (k), 0), new line))
64 OD;
65 CO
