tag:blogger.com,1999:blog-8288194986820249216.post863094976496990282..comments2024-02-04T15:47:25.088-08:00Comments on Abstract Heresies: Another little puzzleJoe Marshallhttp://www.blogger.com/profile/03233353484280456977noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-8288194986820249216.post-17656766016715695452012-05-15T23:27:06.971-07:002012-05-15T23:27:06.971-07:00Two Common Lisp solutions. (They work nicely when...Two Common Lisp solutions. (They work nicely when both arguments are negative, but not when they're of different sign, since in CL negative numbers are represented with an infinite sequence of 1 bits on the left).<br /><br /><br />(defun interleave (l r)<br /> (when (minusp (* l r))<br /> (error "No can do."))<br /> (loop<br /> :until (and (zerop l) (zerop r))<br /> :for pow = 1 :then (* pow 4)<br /> :sum (* pow (+ (* 2 (rem l 2)) (rem r 2)))<br /> :do (setf l (truncate l 2)<br /> r (truncate r 2))))<br /><br />(defun interleave (l r)<br /> (multiple-value-bind (lq lb) (truncate l 2)<br /> (multiple-value-bind (rq rb) (truncate r 2)<br /> (+ lb lb rb (if (and (zerop lq) (zerop rq))<br /> 0<br /> (* 4 (interleave lq rq)))))))<br /><br />(progn (format t "~B ~:* ~D~%" (interleave 23 13))<br /> (format t "~B ~:* ~D~%" (interleave -23 -13)))<br />1001111011 635<br />-1001111011 -635<br />nilpjbhttps://www.blogger.com/profile/09065388232282458321noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-11505112075148521742012-04-26T15:29:41.927-07:002012-04-26T15:29:41.927-07:00A fast (int32, int32) => int64 solution in Kawa...A fast (int32, int32) => int64 solution in Kawa Scheme:<br /><br />(define (mingle (l ::int) (r ::int)) ::long<br /> (let loop ((a ::int r) (b ::int l) (res ::long 0) (i ::int 0))<br /> (cond ((or (and (= a 0) (= b 0))<br /> (= i 64)) res)<br /> (else (loop b (bitwise-arithmetic-shift-right a 1)<br /> (bitwise-ior res<br /> (bitwise-arithmetic-shift-left<br /> (bitwise-and a 1) i))<br /> (+ i 1))))))<br /><br />Here's one which works on arbitrary-precision integers. As kbob says, passing one negative argument and one non-negative argument will lead to a prefix of …101010101, which has a limit of positive infinity, so I check for that first. Is it cheating that +inf.0 isn't actually an integer?<br /><br />(define (mingle2 (l ::integer) (r ::integer))<br /> (if (or (and (< l 0) (>= r 0))<br /> (and (< r 0) (>= l 0)))<br /> +inf.0<br /> (let loop ((a ::integer r) (b ::integer l)<br /> (res ::integer 0) (i ::integer 0))<br /> (cond ((and (= 0 a) (= 0 b)) res)<br /> ((and (= -1 a) (= -1 b))<br /> (bitwise-ior res (bitwise-arithmetic-shift-left -1 i)))<br /> (else (loop b (bitwise-arithmetic-shift-right a 1)<br /> (bitwise-ior res<br /> (bitwise-arithmetic-shift-left<br /> (bitwise-and a 1) i)) (+ i 1)))))))JRHhttps://www.blogger.com/profile/11913030468311931700noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-60822145176790707072012-04-24T17:33:26.349-07:002012-04-24T17:33:26.349-07:00I don't have a solution for negative numbers o...I don't have a solution for negative numbers of arbitrary precision. mingle(0, -1) is the infinite bit pattern ...010101010101010101...kbobhttps://www.blogger.com/profile/11512820963025257647noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-26881507769203644412012-04-24T15:59:59.994-07:002012-04-24T15:59:59.994-07:00Well, this sounded like a fun challenge! My inexpe...Well, this sounded like a fun challenge! My inexpert, probably rather inelegant, attempt:<br /><br />(define divmod2 (lambda (n)<br /> (cons (quotient n 2) (modulo n 2))))<br /><br />(define interleave (lambda (L R)<br /> (letrec ((interleave-place (lambda (L R place sum)<br /> (cond ((and (= L 0) (= R 0))<br /> sum)<br /> (else<br /> (let ((dm2 (divmod2 R)))<br /> (interleave-place (car dm2)<br /> L<br /> (+ place 1)<br /> (+ sum (* (cdr dm2) (expt 2 place))))))))))<br /> (interleave-place L R 0 0))))<br /><br />(display (interleave 23 13))Josh Ballancohttps://www.blogger.com/profile/12329219199206937539noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-39460245571780146572012-04-24T15:44:48.234-07:002012-04-24T15:44:48.234-07:00A two-line routine probably shouldn't have a P...A two-line routine probably shouldn't have a PLEASE, lest it cause E099 PROGRAMMER IS OVERLY POLITE.<br /><br />Haskell is not as concise as INTERCAL ;) but here's a solution in terms of the <a href="http://oeis.org/A000695" rel="nofollow">Moser-de Bruijn sequence</a>:<br /><br />interleave l r = mdb l * 2 + mdb r where<br />mdb 0 = 0<br />mdb n = b + 4 * mdb r where (r, b) = divMod n 2<br /><br />Is there a similarly concise definition of mdb that avoids the boring explicit recursion?Arcane Sentimenthttps://www.blogger.com/profile/04144052171693893368noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-73444942346590636552012-04-24T13:23:32.712-07:002012-04-24T13:23:32.712-07:00Why, yes, it is.
And you didn't say PLEASE.Why, yes, it is.<br /><br /><br />And you didn't say PLEASE.Joe Marshallhttps://www.blogger.com/profile/03233353484280456977noreply@blogger.comtag:blogger.com,1999:blog-8288194986820249216.post-44273270608343509242012-04-24T12:39:06.261-07:002012-04-24T12:39:06.261-07:00This is the INTERCAL mingle operator, so #23 $ #13...This is the INTERCAL mingle operator, so #23 $ #13, which can also be written using any other currency symbol. More generally:<br /><br />(4000) DO :1 <- .1 $ .2<br />DO RESUME #1<br /><br />is a routine invoked by "DO (4000) NEXT" that mingles the values of the 16-bit registers 1 and 2 and puts the result in the 32-bit register 1 (which is unrelated to the 16-bit register 1). That is, provided that no operand overloading [sic] is in effect. See <a href="http://catb.org/~esr/intercal/ick.htm" rel="nofollow"><i>C-INTERCAL 0.29 Revamped Instruction Manual</i></a> for details.John Cowanhttps://www.blogger.com/profile/11452247999156925669noreply@blogger.com