SAS 101,
"Generating Ratinal Numbers in SAS 4GL - 101" :-D
Inspired by loopy walt answer I decided to make SAS 4GL version.
The code:
data;set;do while(n);t=d;if(n*d<0)then do;put"g"@;d=n;n=-t;end;else do;put"f"@;n=n-d;end;end;put;run;
SAS is quite "talkative" by all those if
s, then
s, do
s, end
s and else
s so, even tough I did my best to "boil" bytes down, I ended up on 101.
Explanation:
I don't like stack overflows so instead recursion I went with iterative approach.
It is SAS 4GL so the the standard input in form of a SAS dataset is expected (I added some extra test cases):
data i;
input n d;
cards;
1 3
3 1
16 4
8 2
4 1
1 -3
2 3
0 9
0 3
0 1
1 1
2 1
1 -2
-1 -2
6 4
-2 3
8 9
17 42
17 -42
17 303
42 303
99 100
990 1000
999 1002
999 -1002
1 11111
1 2
2 4
4 8
;
run;
Human readable code:
data _null_; /* 0) */
set i; /* expect input data set 1) */
put n= d= @; /* added just for printing */
do while(n); /* while numerator is not 0 */
x=d;
if (n*d<0)
then /* for negative print "g", then negate and flip fraction */
do;
put "g" @;
d = n;
n = -x;
end;
else /* for positive print "f", then substract 1 from fraction */
do;
put "f" @;
n = n-d;
end;
end;
put; /* add new line character at the end of printout 2) */
run;
Footnotes:
0) turn of production of output dataset
1) the set
statement takes as input the last created data set, so code generating dataset i
has to be executed just before.
2) the last put;
can be skipped if the input dataset has only 1 observation what reduces length by 4 bytes to 97.
Log output:
n=1 d=3 fgffgff
n=3 d=1 fff
n=16 d=4 ffff
n=8 d=2 ffff
n=4 d=1 ffff
n=1 d=-3 gfff
n=2 d=3 fgfff
n=0 d=9
n=0 d=3
n=0 d=1
n=1 d=1 f
n=2 d=1 ff
n=1 d=-2 gff
n=-1 d=-2 fgff
n=6 d=4 ffgff
n=-2 d=3 gffgff
n=8 d=9 fgfffffffff
n=17 d=42 fgffgffffgffgffgffgffgffgffgff
n=17 d=-42 gfffgffgfffffffff
n=17 d=303 fgffgffgffgffgffgffgffgffgffgffgffgffgffgffgffgffgfffgffgffgffgfffgff
n=42 d=303 fgffgffgffgffgffgffgffffffgfff
n=99 d=100 fgffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
n=990 d=1000 fgffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
n=999 d=1002 fgf[ 332 "f" hidden for readability ]f
n=999 d=-1002 gff[ 331 "gff" hidden for readability ]gff
n=1 d=11111 f[ 11109 "gff" hidden for readability ]gff
n=1 d=2 fgff
n=2 d=4 fgff
n=4 d=8 fgff
NOTE: There were 29 observations read from the data set WORK.I.
NOTE: DATA statement used (Total process time):
real time 0.02 seconds
cpu time 0.03 seconds
A small comment at the end:
We are in a group of functions with composition.
Function: \$ z(x) = g(f(g(f(g(x))))) = x{-}1 \$ is an inverse of \$f\$ (\$f(z(x))=x\$, \$z(f(x))=x\$) and \$g\$ is inverse of itself (\$g(g(x))=x\$)
So a path from \$0\$ to \$\frac{n}{d}\$ (assuming frac is reduced) of the form:
$$
\frac13 = f(g(f(f(g(f(f(0)))))))
$$
can be "walked back" using inverses of \$f\$ and \$g\$
$$
0 = z(z(g(z(z(g(z(\frac13)))))))
$$
Which is "base" for the algorithm:
"1) take a fraction, 2) if the fraction is negative "flip it"(negate and inverse) else subtract 1 from it, 4) if fraction is 0 stop else got to 1)"