Take the 2-minute tour ×
TeX - LaTeX Stack Exchange is a question and answer site for users of TeX, LaTeX, ConTeXt, and related typesetting systems. It's 100% free, no registration required.

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}
share|improve this question
    
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
    
Ok, thanks for the tip. –  Scott H. Feb 16 '13 at 23:01
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." –  Kundor 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
add comment

2 Answers 2

up vote 8 down vote accepted

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.

share|improve this answer
    
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
add comment

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".

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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