G'day all.
On Fri, Apr 26, 2002 at 09:45:24AM -0700, Larry Wall wrote:
> Gee, maybe I should patent this.
Actually, you're binary searching the Stern-Brocot tree representation
of rational numbers. In fact, if you have arbitrary precision integers,
you can convert these strings into rational numbers which preserve
ordering:
my @precedence = qw(1 2 2 1 1 2 1 2);
($m1,$n1,$m2,$n2) = (0, 1, 1, 0);
foreach (@precedence) {
($m,$n) = ($m1+$m2, $n1+$n2);
if (/2/) {
($m1,$n1) = ($m,$n);
}
else {
($m2,$n2) = ($m,$n);
}
}
($m,$n) = ($m1+$m2, $n1+$n2);
Then $m/$n is the number.
I think this was covered in Graham, Knuth & Patashnik, "Concrete
Mathematics". Still, you might be able to patent its application to
operator precedences.
Cheers,
Andrew Bromage
