[lnkForumImage]
TotalShareware - Download Free Software

Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.javascript

binary search gcd / half interval search

JT

6/9/2015 11:05:00 AM

I try to implement a half interval search as i remember it but i am not sure i remember correct.

if(looptwo == true && mymax!=mymin+1) {mymin=myval; myval=mymin+((mymax-mymin)/2); myval=parseInt(myval);}
else {if (mymin+1==mymax){looptwo=false;} else {looptwo=true; mymax=myval; myval=mymax-((mymax-mymin)/2);myval=parseInt(myval);}}

Beware the bugs...

<html lang="en"><head>
<meta http-equiv="content-type" content="text/html; charset=UTF-8"><script language="Javascript">

/* CONVERT A DECIMAL NUMBER INTO ANYBASE */

function newbase(decArr, base)
{
tempBase = base.toString();
baseArr = tempBase.split("").reverse();
digRes = [];
resultmult = [];
digit = 0;
oldigmult = [];
resultmult[0] = 1;
convArr = []
digits = 0;
decbase = 10;
for(i = 0; i < baseArr.length; i ++ )
{
baseArr[i] = parseInt(baseArr[i]);
}
for(i = 0; i < decArr.length; i ++ )
{
decArr[i] = parseInt(decArr[i]);
}

loop = true;

while(loop == true)
{
oldigmult[digits] = resultmult;
olddigits = digits;
orderArrayMult(10, baseArr, resultmult);
loop = arrCompareTwo(resultmult, decArr);
digits ++ ;
}

while(olddigits >= 0)
{
resultmult = [];
counterArr = [];
myDig=[0];
looptwo = true;

mymin=0;
mymax=base;
myval=parseInt(base/2);
//document.write(myval);
x=1;
document.calc.trash.value+="\nNEW DECARR ="+decArr+"\n";
while (looptwo == true)
{


tOne=myval.toString();
for(y=0;y<tOne.length;y++){ tTwo=tOne.charAt(y); myDig[y] = parseInt(tTwo);}
document.calc.trash.value+="My value "+myDig+"\n";
myDig.reverse();
orderArrayMult(10, myDig, oldigmult[olddigits]);
document.calc.trash.value+=multresult+"="+myDig+"*"+oldigmult[olddigits]+"\n";

multarr = resultmult.slice();



looptwo = arrCompareTwo(resultmult, decArr);
document.calc.trash.value+="MyVal="+myDig+" ->MIN="+mymin+" ->MAX="+mymax+"\n";
if(looptwo == true && mymax!=mymin+1) {mymin=myval; myval=mymin+((mymax-mymin)/2); myval=parseInt(myval);}
else {if (mymin+1==mymax){looptwo=false;} else {looptwo=true; mymax=myval; myval=mymax-((mymax-mymin)/2);myval=parseInt(myval);}}
// x++;
// if(x>20)p.stop();
}


// document.calc.trash.value=+"<BR>NEW DIG = "+myDig;
//p.stop();

convArr[olddigits] = myDig;
olddigits -- ;
document.calc.trash.value+="decArr- multarr ->"+ decArr+" - "+multarr;
decArr = naiveSub(10, decArr, multarr);
document.calc.trash.value+=" = "+decArr+"\n";
checkifzero = decArr.join("");
testValZero = parseInt(checkifzero);
if(testValZero <= 0) break;

}
for(j = olddigits; j >= 0; j -- )
{
convArr[j] = 0;
}
return convArr;
}


/* COMPARE SIZE OF TWO ARRAYS, IF A < B RETURN TRUE, IF B >= A RETURN FALSE */

function arrCompareTwo(A, B)
{
var AA = A.length;
var BB = B.length;
if(AA > BB) return false;
if(AA < BB) return true;
// AA = BB, compare indexes from biggest to smallest.
for(i = AA - 1; i >= 0; i -- )
{
if(A[i] < B[i]) return true;
if(A[i] > B[i]) return false;
}
return true;
}

/* COMPARE SIZE OF TWO ARRAYS, IF A < B RETURN TRUE, IF B >= A RETURN FALSE */

function lessThan(A, B)
{
var AA = A.length;
var BB = B.length;
if(AA > BB) return false;
if(AA < BB) return true;
// AA = BB, compare indexes from biggest to smallest.
for(i = AA - 1; i >= 0; i -- )
{
if(A[i] < B[i]) return true;
if(A[i] > B[i]) return false;
}
return false;
}



function prepMult(multOne, multTwo)
{
if(multOne.length > multTwo.length)
{
mbigArr = multOne.length;
msmallArr = multTwo.length
}
else
{
mbigArr = multTwo.length;
msmallArr = multOne.length;
}
// Parse with zeros to get same length, and make sure they are integers.
// for (i = 0; i < bigArr; i ++ )
// {
// multOne[i] = parseInt(multOne[i]);
// multTwo[i] = parseInt(multTwo[i]);
// if (isNaN(multOne[i])) multOne[i] = 0;
// if (isNaN(multTwo[i])) multTwo[i] = 0;
// }
}

/* MULTIPLY THE TWO VARIABLES STORED IN MULTONE AND MULTTWO USING THE CHOSEN BASE */

function naiveMult(base, multOne, multTwo)
{
prepMult(multOne, multTwo);
var total = [];
var addResult = [];
total[0] = 0;
for (var i = 0; i < msmallArr; i ++ )
{
multresult = [];
remainder = 0;
tempVal = 0;
tempDig = 0;
j = 0;
if(i > 0)
{
for(zero = 0; zero < i; zero ++ ) multresult[zero] = 0;
}

while(j < mbigArr)
{
intMult ++ ;
tempVal = (multOne[j] * multTwo[i]) + remainder;
remainder = 0;
if (tempVal >= base)
{
tempDig = tempVal % base;
remainder = (tempVal - tempDig) / base;
multresult[j + i] = tempDig;
}
else
{
multresult[j + i] = tempVal;
}
j ++ ;
}

if(remainder != 0)
{
// Remainder after last digit multiplication
multresult[j + i] = remainder;
}
smallAddArr = multresult.length;
bigAddArr = total.length;
addResult = naiveAdd(base, multresult, total, smallAddArr, bigAddArr);
total = addResult;
}

while (total[total.length - 1] == 0 && total.length - 1 > 0)
{
total.splice(total.length - 1, 1)
}
return total;
}


/* ADD TWO THE TWO VARIABLES STORED IN ADDONE AND ADDTWO USING CHOSEN BASE */

function naiveAdd(base, addOne, addTwo)
{
prepAdd(addOne, addTwo);
addResult = [];
remainder = 0;

for (i = 0; i < asmallArr; i ++ )
{
intAdd ++ ;
addOne[i] = parseInt(addOne[i]);
addTwo[i] = parseInt(addTwo[i]);
if (isNaN(addOne[i])) addOne[i] = 0;
if (isNaN(addTwo[i])) addTwo[i] = 0;
addResult[i] = addOne[i] + addTwo[i] + remainder;
if (addResult[i] >= base)
{
addResult[i] = addResult[i] - base;
remainder = 1;
intCarry ++ ;
}
else
{
remainder = 0;
}
}
// Copying values from the shorter string
while(i < abigArr)
{
addOne[i] = parseInt(addOne[i]);
addResult[i] = addOne[i] + remainder;
remainder = 0;
i ++ ;
}
// If strings of equal length but there is a remainder;
if (remainder == 1) addResult[i ++ ] = 1;
else addResult.splice(i, 1);
return addResult;
}

function prepAdd(addOne, addTwo)
{
if(addOne.length > addTwo.length)
{
abigArr = addOne.length;
asmallArr = addTwo.length
}
else
{
abigArr = addTwo.length;
asmallArr = addOne.length;
}
// Parse with zeros to get same length, and make sure they are integers.
// for (i = 0; i < bigArr; i ++ )
// {
// multOne[i] = parseInt(multOne[i]);
// multTwo[i] = parseInt(multTwo[i]);
// if (isNaN(multOne[i])) multOne[i] = 0;
// if (isNaN(multTwo[i])) multTwo[i] = 0;
// }
}

/* FIX THIS LATER */

function prepSubt(subOne, subTwo)
{
if(subOne.length > subTwo.length)
{
bigArr = subOne.length;
smallArr = subTwo.length
}
else
{
bigArr = subTwo.length;
smallArr = subOne.length;
}
// Parse with zeros to get same length, and make sure they are integers.
for (i = 0; i < bigArr; i ++ )
{
subOne[i] = parseInt(subOne[i]);
subTwo[i] = parseInt(subTwo[i]);
if (isNaN(subOne[i])) subOne[i] = 0;
if (isNaN(subTwo[i])) subTwo[i] = 0;
}
}

/* SUBTRACT THE TWO VARIABLES STORED IN SUBONE AND SUBTWO USING THE CHOSEN BASE */

function naiveSub(base, subOne, subTwo)
{
prepSubt(subOne, subTwo);
result = [];
for (i = 0; i < smallArr; i ++ )
{
j = 0;

if (subOne[i] < subTwo[i])
{

intBorrow ++ ;
subOne[i] += base;
j = i;
while (subOne[j + 1] == 0)
{
subOne[j + 1] += base - 1;

j ++ ;
}
subOne[j + 1] += - 1;

}

j = 0;
result[i] = subOne[i] - subTwo[i];
intSub ++ ;
}
while(i < bigArr)
{
result[i] = subOne[i];
i ++ ;
}

while (result[result.length - 1] == 0 && result.length - 1 > 0)
{
result.splice(result.length - 1, 1)
}
return result;
}

/* RESET FORM FIELDS, FETCH BASE AND STRING TO EVALUATE */

function fetchVal()
{
document.calc.stats.value = "";
strEval = document.calc.eval.value;
genArr[0] = strEval;
base = document.calc.formbase.value;
base = parseInt(base);
}

/* DO CONVERSION OF OPERANDS TO BASE OF CHOICE */

function baseConversion()
{
arrOne = genArr[0].split("").reverse();
arrOne = newbase(arrOne, base);
arrOne.reverse();
if (base < 11)
{
bout = arrOne.join("");
}
else
{
bout = arrOne
}
document.calc.stats.value += "Converted base digits = " + bout.length + "\n";
document.calc.stats.value += "Converted arrOne " + bout + "\n";
}

function orderArrayMult(Abase, A, B)
{
return lessThan(A, B) ? resultmult = naiveMult(Abase, B, A) : resultmult = naiveMult(Abase, A, B);
}

function orderArraySubt(Abase, A, B)
{
return lessThan(A, B) ? resultmult = naiveSub(Abase, B, A) : resultmult = naiveSub(Abase, A, B);
}


/* GLOBAL VARIABLES AND ARRAY FORMAT */
/* THE NOTATION OF NUMERALS USE BASE TEN, SO FOR INDEX VALUES IN ARRAY IF BASE 2000, DIGITVALUE IN INDEX RANGE = (0 - 1999) */
/* VARIABLES ARE STORED REVERSED IN ARRAY */
/* WITH A SINGLE "DIGITPLACE/VALUE" OF THE CHOSEN BASE, HOLD AT EACH INDEX */

function MAIN()
{

/* INIT GLOBAL VARIABLES START */
genArr = [];
baseArr = [];
resultmult = [];
plusOne = [];
plusOne[0] = 1;
arrOne = [];
arrTwo = [];
tempA = [];
tempB = [];
// Counters, adds, subtraction, multiplications
intMult = 0;
intAdd = 0;
intSub = 0;
intBorrow = 0;
intCarry = 0;
// Length of the operands
bigArr = 0;
smallArr = 0;
addBigLength = 0;
addSmallLength = 0;
baseStr = "";
// Reset variables from form
base = 0;
strEval = "";
document.calc.stats.value = "";
fetchVal();
// Get stringsvalues from form

/* INIT END */
/* MAIN FUNCTION */
document.calc.stats.value += "Operand A decimal digits = " + strEval.length + "\n";
// Do base conversion into the base fetched from form
baseConversion();

}
</script>



<meta charset="utf-8"></head>
<body onload="MAIN()" bgcolor="gold">
<h3>BIG NUMBERS BASE CONVERTER (anybase) version 0.00000000000001 ;)</h3><p>
</p><form name="calc" onsubmit="MAIN(); return false;"><b>
<input name="calc" value="Calc" type="submit"> *use radiX* <input name="formbase" value="1000" size="10" type="text"><br><br>
Trash print<br>
<textarea name="trash" rows="20" cols="120"></textarea><br>

Base 10 value to convert<br>
<textarea name="eval" rows="2" cols="120">21000</textarea><br>

New base out<br>
<textarea name="stats" rows="40" cols="120"></textarea>




</b></form></body></html>