img/home.png

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=number2|number1;
$EES
This is as also twice as fast. And conjectural as well.