Algol 68 Genie

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
Deze website is gearchiveerd door de KB, nationale bibliotheek.

This website is archived by the National Library of the Netherlands.