Steve Wampler wrote:
> Bruce & Breeanna Rennie wrote:
>> I have written the following test code to determine the Hamming numbers
>> (from a discussion on Lambda the Ultimate)
...
> Adapting a lazy evaluation scheme (using co-expressions, perhaps)
> might reduce the need for so much recursion more easily than simple
> recursion elimination. Anyone want to try? (I'd like to, but
> am a bit swamped at the moment. Maybe later... it sounds like a
> fun problem to work on!
I couldn't resist. I've attached a solution that avoids the recursion
using lazy evaluation.
While it uses co-expressions (lots of them, in fact), I'm pretty sure
it wouldn't be hard to rewrite it to remove the co-expressions also.
That would probably reduce the memory footprint significantly.
It behaves a little differently than the original. Instead of
iterating across the solution space, adding new hamming numbers
as the iteration produces them, this solution outputs a single
stream of hamming numbers, in order from lowest up. The default is
to generate the first 30 numbers, but you can give it an argument to
produce any number of numbers.
-Steve
--
Steve Wampler -- [EMAIL PROTECTED]
The gods that smiled on your birth are now laughing out loud.
# Lazily generate the three hamming numbers that can be derived directly
# from a known hamming number h
class Triplet : Class (h, ce)
method curval()
return h
end
method nextVal()
if h := @ce then {
suspend h
}
end
initially (baseNum)
h := 2*baseNum
ce := create (3|5)*baseNum
end
# Generate hamming numbers, in order. Default is first 30
# But an optional argument can be used to generate more (or less)
# e.g. hamming2 5000 generates the first 5000.
procedure main(args)
limit := integer(args[1]) | 30
every write("\t", generateHamming(triples) \ limit)
end
# Do the work. Start with known hamming number 1 and maintain
# a set of triplet hamming numbers as they get derived from that
# one. Most of the code here is to figure out which hamming
# number is next in sequence (while removing duplicates)
procedure generateHamming()
triplers := set()
insert(triplers, Triplet(1))
suspend 1
repeat {
# Pick a hamming triplet to *may* have the next smallest number
t1 := !triplers # any will do to start
every t2 := !triplers do {
if t1 === t2 then next
if t1.curval() > t2.curval() then {
# oops we were wrong, switch assumption
t1 := t2
}
else if t1.curval() = t2.curval() then {
# t2's value is a duplicate, so
# advance triplet t2, if none left in t2, remove it
if not t2.nextVal() then delete(triplers, t2)
}
}
# Ok, t1 has the next hamming number, grab it
nextHamming := t1.curval()
# Advance triplet t1, if none left in t1, remove it
if not t1.nextVal() then delete(triplers, t1)
insert(triplers, Triplet(nextHamming))
suspend nextHamming
}
end
-------------------------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
_______________________________________________
Unicon-group mailing list
Unicon-group@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/unicon-group
