GCD
This is a GCD, standard (Euclid's) algorithm:
$declareint number1 number2 gcd zero
$invar number1(3) number2(9)
$invar number1(125) number2(65)
$rinvar number1(1,10000) number2(1,10000)
$retvar gcd
$minimize lines off
$bes
while (number1!=zero) {
gcd=number2%number1;
number2=number1;
number1=gcd;
}
gcd=number2;
$ees
What we have got out of Critticall, is this:
// The algorithm has been enhanced for 49.8188%
$DECLAREINT number1 gcd number2
$INVAR number1(3) number2(9)
$INVAR number1(125) number2(65)
$MINIMIZE LINES 60
$RINVAR number1(1,10000) number2(1,10000)
$RETVAR gcd
// int number1=0;int gcd=0;int number2=0;
$BES
number1=number1%number2;
while (number1!=gcd) {
number2=number2%number1;
if (gcd==number2) {
break;
}
number1=number1%number2;
}
gcd=number1^number2;
$EES
Two times less steps for number pairs up to 1000, and even faster for larger numbers. It's conjectural algorithm, however.
And this is a standard GCD for three arguments. Based on the fact, that
GCD(number1,number2,number3) = GCD(GCD(number1,number2),number3)
$DECLAREINT number1 gcd number2 number3 zero
$rinvar number1(1,1000) number2(1,1000) number3(1,1000)
$retvar gcd
$minimize lines off
$bes
while (number1!=zero) {
gcd=number2%number1;
number2=number1;
number1=gcd;
}
while (number2!=zero) {
gcd=number3%number2;
number3=number2;
number2=gcd;
}
gcd = number3;
$ees
What we have got now, is this:
// The algorithm has been enhanced for 50.6078%
$DECLAREINT number1 gcd number2 number3
$MINIMIZE LINES 110
$RINVAR number1(1,1000) number2(1,1000) number3(1,1000)
$RETVAR gcd
// int number1=0;int gcd=0;int number2=0;int number3=0;
$BES
number1=number1%number3;
while (number1!=gcd) {
number2=number2%number1;
if (number2==gcd) {
number2=number1;
break;
}
number1=number1%number2;
}
number1=number3%number2;
while (number1!=gcd) {
number2=number2%number1;
if (number2==gcd) {
break;
}
number1=number1%number2;
}
gcd=number2number1;
$EES
This is as also twice as fast. And conjectural as well.
