77 lines
2.7 KiB
Text
77 lines
2.7 KiB
Text
note
|
|
description : "Initial part, in order, of the sequence of Hamming numbers"
|
|
math : "[
|
|
Hamming numbers, also known as regular numbers and 5-smooth numbers, are natural integers
|
|
that have 2, 3 and 5 as their only prime factors.
|
|
]"
|
|
computer_arithmetic :
|
|
"[
|
|
This version avoids integer overflow and stops at the last representable number in the sequence.
|
|
]"
|
|
output : "[
|
|
Per requirements of the RosettaCode example, execution will produce items of indexes 1 to 20 and 1691.
|
|
The algorithm (procedure `hamming') is more general and will produce the first `n' Hamming numbers
|
|
for any `n'.
|
|
]"
|
|
source : "This problem was posed in Edsger W. Dijkstra, A Discipline of Programming, Prentice Hall, 1978"
|
|
date : "8 August 2012"
|
|
authors : "Bertrand Meyer", "Emmanuel Stapf"
|
|
revision : "1.0"
|
|
libraries : "Relies on SORTED_TWO_WAY_LIST from EiffelBase"
|
|
implementation : "[
|
|
Using SORTED_TWO_WAY_LIST provides an elegant illustration of how to implement
|
|
a lazy scheme in Eiffel through the use of object-oriented data structures.
|
|
]"
|
|
warning : "[
|
|
The formatting (<lang>) specifications for Eiffel in RosettaCode are slightly obsolete:
|
|
`note' and other newer keywords not supported, red color for manifest strings.
|
|
This should be fixed soon.
|
|
]"
|
|
|
|
class
|
|
APPLICATION
|
|
|
|
create
|
|
make
|
|
|
|
feature {NONE} -- Initialization
|
|
|
|
make
|
|
-- Print first 20 Hamming numbers, in order, and the 1691-st one.
|
|
local
|
|
Hammings: like hamming
|
|
-- List of Hamming numbers, up to 1691-st one.
|
|
do
|
|
Hammings := hamming (1691)
|
|
across 1 |..| 20 as i loop
|
|
io.put_natural (Hammings.i_th (i.item)); io.put_string (" ")
|
|
end
|
|
io.put_new_line; io.put_natural (Hammings.i_th (1691)); io.put_new_line
|
|
end
|
|
|
|
feature -- Basic operations
|
|
|
|
hamming (n: INTEGER): ARRAYED_LIST [NATURAL]
|
|
-- First `n' elements (in order) of the Hamming sequence,
|
|
-- or as many of them as will not produce overflow.
|
|
local
|
|
sl: SORTED_TWO_WAY_LIST [NATURAL]
|
|
overflow: BOOLEAN
|
|
first, next: NATURAL
|
|
do
|
|
create Result.make (n); create sl.make
|
|
sl.extend (1); sl.start
|
|
across 1 |..| n as i invariant
|
|
-- "The numbers output so far are the first `i' - 1 Hamming numbers, in order".
|
|
-- "Result.first is the `i'-th Hamming number."
|
|
until sl.is_empty loop
|
|
first := sl.first; sl.start
|
|
Result.extend (first); sl.remove
|
|
across << 2, 3, 5 >> as multiplier loop
|
|
next := multiplier.item * first
|
|
overflow := overflow or next <= first
|
|
if not overflow and then not sl.has (next) then sl.extend (next) end
|
|
end
|
|
end
|
|
end
|
|
end
|