7

The following loop fails to terminate and I have no idea why. I've either violated some syntax rule, there's an issue with the self reference in n:= floor (n/2);, or I've missed something embarrassingly obvious.

\documentclass{article}
\usepackage{luamplib}
\begin{document}
\begin{mplibcode}

def divtwo(expr n)=
    forever: exitunless n>1;
        n:= floor (n/2);
    endfor;
enddef;

divtwo(5);

end;

\end{mplibcode}
\end{document}

Edit: Thanks for the answers! The actual use case was to find the binary digits of a number (order irrelevant). Corrected (probably still bad) code:

\documentclass{article}
\usepackage{luamplib}
\begin{document}
\begin{mplibcode}
numeric k[];

def divtwo(expr n)=
  save m;
  m:=n;
  j = 1;
  forever: exitunless m>0;
    b:= m mod 2;
    m:= floor (m/2);
    k[j]:=b;
    j:=j+1;
  endfor;
enddef;

divtwo(5);

end;

\end{mplibcode}
\end{document}
  • You don't want to say save m in a def. Either use a group (with vardef, probably) or a specific variable you don't use anywhere else. – egreg Feb 16 '13 at 22:52
  • 1
    You are asking for a solution to the halting problem, which Turing famously proved unanswerable, but apparently he forgot to add "except by egreg." – Nick Matteo Feb 17 '13 at 0:17
  • 1
    @kundor A couple of points (that I'm sure you know, but to clarify for future visitors): (1) the halting problem asks whether a program terminates, rather than why it does not. (2) had the question been "does this loop terminate" we would have a decidable instance of the halting problem rather than the halting problem itself. – Scott H. Feb 17 '13 at 1:11
8

The code is wrong because n in the body of the definition is just a placeholder that's substituted with the actual argument; in your case you get the meaningless statement

5:=floor(5/2)

A correct function that returns a value could be

vardef divtwo(expr n)=
  save m;
  m:=n;
  forever: exitunless m>1;
    show m;
    m:= floor (m/2);
  endfor;
m enddef;

x=divtwo(5);
show x;
show m;

end.

The show commands are just for debugging: you get

This is MetaPost, version 1.504 (kpathsea version 6.1.0)
(mpost.mp (/usr/local/texlive/2012/texmf-dist/metapost/base/plain.mp
Preloading the plain mem file, version 1.004)) (./scottloop.mp
>> 5
>> 2
>> 1
>> m )

so you see that m has regained its former value after the usage of deftwo (vardef has implicit begingroup and endgroup tokens).

Of course the result will always be 1.


Your idea of gathering the digits is almost correct; I'd prefer a variant:

numeric k[];

vardef divtwo(expr n)=
  save m; save j;
  m = n;
  j = 1;
  forever: exitunless m>0;
    k[j] = m mod 2;
    m:= floor (m/2);
    j:=j+1;
  endfor;
  k[0] = j-1;
enddef;

divtwo(257);
m=0;
forever: exitif m > k[0];
show k[m]; m:=m+1;
endfor;

end;

So in k[0] you store the number of digits. For instance, the input shows

This is MetaPost, version 1.504 (kpathsea version 6.1.0)
(mpost.mp (/usr/local/texlive/2012/texmf-dist/metapost/base/plain.mp
Preloading the plain mem file, version 1.004)) (./scottloop.mp
>> 9
>> 1
>> 0
>> 0
>> 0
>> 0
>> 0
>> 0
>> 0
>> 1 )

on the terminal.

  • Thanks egreg, this is just what I was looking for. I added the use case to the question. Do you happen to know whether metapost has anything built in to convert a number to binary? – Scott H. Feb 16 '13 at 22:50
  • Unfortunately, when using luamplib, the show command doesn't print anything to the terminal or the log, so I have to work quite blindly :( – Scott H. Feb 16 '13 at 22:55
  • @ScottH. Use directly mpost from the command line. I've added something about your edit. – egreg Feb 16 '13 at 22:59
  • Ah, that's a good idea to store the number of digits :) – Scott H. Feb 16 '13 at 23:07
5

Not sure about why your code doesn't work. You have clearly a typo (existunless should be exitunless) but it hangs even after fixing it. Also, your "function" does not "return" any result. You should use a vardef instead of def, and finish the function with the isolated expresion n before the enddef; (which would be the "returned" value).

However, I can see that you are trying to implement the operation "rest of the division by two", and you don't need to, because metapost provides the mod operator. So, instead of divtwo(5) you can simply write 5 mod 2.

The following code demonstrates that mod is a valid operator for metapost:

\documentclass{article}
\usepackage{luamplib}
\begin{document}
\begin{mplibcode}
beginfig(1);
 n := 5 mod 2;            % Compute n
 label(decimal n, (0,0)); % Show its value as part of the figure
endfig;
\end{mplibcode}
\end{document}

The resulting pdf shows "1".

  • The original function (assuming it worked) is just a complicated way to compute 1, I think, as floor(3/2)=floor(2/2)=1; if the argument is less than 2 the loop stops immediately. So the only way to get 0 is to use divtwo(0). – egreg Feb 16 '13 at 22:38
  • +1 Thanks for catching the typo and taking time to answer! – Scott H. Feb 16 '13 at 22:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.