MC: Closest Integer in a List

The Challenge

From: <danli97@ite.mh.se> (Daniel Lidstrom) Subject: Need subroutine Date: Thu, 05 Mar 1998 08:43:44 -0600I need a subroutine to find the closest integer in a list to a given number. For example, given { 1 4 9 6 } 2 we would get the 1. I need a small B*T. Daniel Lidström, danli97@ite.mh.se http://www.ite.mh.se/~danli97/

The Entries

Scroll down a few lines if you *really* want to see the entries

From: <avenar_j@epita.fr> (Jean-Yves Avenard) Subject: Re: Need subroutine Date: Fri, 6 Mar 1998 12:26:41 +1000Hello Please find here a small program than do that: I run the program in two steps: First, I check if the real you want to find is already in the list. If yes, then I just put the real you gave at the beginning, on the stack Otherwise, I do a LIST->, and parse the stack; here is the stack state: n: real1 ... 4: real n-1 3: real n 2: The last closest real 1: Last smallest difference Here is the program, I'm 100% sure, than someone will find a faster way to do it, (what about a MC ?) << -> X << DUP X POS IF THEN DROP X ELSE LIST-> 0 MAXR ->NUM 1 4 ROLL START 3 PICK X - ABS DUP2 IF > THEN SWAP DROP SWAP ELSE 4 ROLL DROP END DROP NEXT DROP END >> >> Hope this will help Jean-Yves

From: <boettcher@cmu.edu> (Peter W Boettcher) Subject: Re: Need subroutine Date: Fri, 6 Mar 1998 00:15:55 -0500How about: \<< OVER SWAP - ABS DUP SORT HEAD POS GET \>> #D816h 38.5 I didn't time it... the sort will make it slow. Here's a better way to find the minimum element of a list than SORT HEAD: \<< DUP2 < ROT ROT IFTE \>> STREAM So the new program looks like: \<< OVER SWAP - ABS DUP \<< DUP2 < ROT ROT IFTE \>> STREAM POS GET \>> # A6ECh 58 Much bigger, but I'm sure it runs much faster. Approximate time to run for a 200 element random list is 7.5s Pete Boettcher boettcher@cmu.edu

From: <boettcher@cmu.edu> (Peter W Boettcher) Subject: Re: Need subroutine Date: Fri, 6 Mar 1998 00:48:57 -0500Whoops! I somehow missed the builtin MIN. Now it's: \<< OVER SWAP - ABS DUP \<< MIN \>> STREAM POS GET \>> # 9A3h 48 It now takes ~5s on a 200 element random list. Pete Boettcher boettcher@cmu.edu