Best search algorithm to find condition within a range

[jonas.thornvall at gmail.com]

Den torsdag 9 april 2015 kl. 16:08:48 UTC+2 skrev Chris Angelico:
> On Thu, Apr 9, 2015 at 11:57 PM, Alain Ketterlin
> <alain at dpt-info.u-strasbg.fr> wrote:
> > Because, in:
> >
> >     z = x+y; // all signed ints
> >     if ( z < x )
> >         ...
> >
> > either there was no overflow (and the condition is false), or there was,
> > and the result is undefined, i.e., "z<x" can be considered false also.
> 
> Do you mean "all unsigned ints" here? Because if y is negative, the
> condition will be true without overflow. If you didn't, then I'm
> puzzled as to where the undefined behaviour is coming from.
> 
> ChrisA

Aside from the base changer i've written a bignumb anybase generic multiplication, addition and subtraction routine. My goal is to make the arithmetic in the base of choice whatever size.

And i think i can do it, i already have mult, add , subt working in anybase but not bignumb.

Does this mult work for arbitrary size?
Or will it but out at some point?


<SCRIPT LANGUAGE="Javascript">
/* MULTIPLY TWO VARIABLES */

//CONVERT A DECIMAL NUMBER INTO ANYBASE
function newbase(decNumber,base){
var out =[];
digits=1;
digmult=1;
while(digmult*base<=decNumber){
	digmult=digmult*base
        digits++;
}
digsave=digmult;
while(decNumber>0 || digits>0){
        loop=1;
        digit=0;
       	for (digit=0;digit<=base;digit++) {
        if((digit+1)*digmult>decNumber)break;
       	}
        out[digits]=digit;
        digmult=digmult*digit;
        decNumber=decNumber-digmult;
        digsave=digsave/base;
        digmult=digsave;
        digits--;
	}

return out;

}

function naiveMult(base, multOne, multTwo)
{  
   var total = [];
   var addResult = [];
   total[0] = 0;

   //Check which array bigger minimize multiplications
   if (multOne.length>multTwo.length){ mshort=multOne.length; mlong=multTwo.length;}
       else { mshort=multOne.length; mlong=multTwo.length;}

   for (var i = 0; i < mshort; i ++ )
   {
      multresult = [];
      remainder = 0;
      tempVal = 0;
      tempDig = 0;
      j = 0;

      if(i > 0)
      {
         for(zero = 0; zero < i; zero ++ ) multresult[zero] = 0;
      }

      while(j < mlong)
      {
         intMult++;
           
         tempVal = (multOne[i] * multTwo[j]) + 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)
      {
         multresult[j + i] = remainder;
      }
      addResult=naiveAdd(base, total, multresult);
      total=addResult; 
   }
   return total;
}

/* ADD TWO VARIABLES */

function naiveAdd(base, arrOne, arrTwo)
{
   
   shortArr=[];
   longArr=[];
   addResult = [];
   remainder = 0;
   //Find shortest and longest array
   if (arrOne.length >= arrTwo.length) {shortArr = arrTwo; longArr = arrOne;}
            else  {shortArr = arrOne;longArr = arrTwo;}
   for (i = 0; i < shortArr.length; i ++ )
   {
      intAdd ++ ;
      arrOne[i] = parseInt(arrOne[i]);
      arrTwo[i] = parseInt(arrTwo[i]);
      if (isNaN(arrOne[i])) arrOne[i] = 0;
      if (isNaN(arrTwo[i])) arrTwo[i] = 0;
      addResult[i] = arrOne[i] + arrTwo[i] + remainder;
     
      if (addResult[i] >= base)
      {
         addResult[i] = addResult[i] - base;
         remainder = 1;
      }
      else
      {
         remainder = 0;
      }
   }
   //Copying values from the shorter string
   while(i<longArr.length) {longArr[i]=parseInt(longArr[i]);addResult[i]=longArr[i]+remainder; remainder=0; i++;}
   //If strings of equal lenght but there is a remainder;
   if (remainder == 1) addResult[i++] = 1;
   else addResult.splice(i, 1);
   return addResult;
}

/* MAIN */
function fetchValues()
{
intMult=0;
intAdd=0;
base=10;
x=1;
y=1;
document.calc.result.value="";
document.calc.stats.value="";
document.calc.outbase.value="";
strEval = document.calc.eval.value;
genArr = strEval.split("*");
//fONE=newbase(genArr[0],base);
//document.write(fONE[2]);
//document.calc.outbase.value +=fONE+" + \n";
//fTWO=newbase(genArr[1],base);
//document.calc.outbase.value +=fTWO+"\n";

arrOne=genArr[0].split("").reverse();
arrTwo=genArr[1].split("").reverse();
base = document.calc.formbase.value;
out=naiveMult(base,arrOne,arrTwo);
document.calc.stats.value +="Multiplications = "+intMult+"\n";
document.calc.result.value +=" Product = " + out.reverse()+"\n";
}
</SCRIPT>
<!DOCTYPE html>
<html lang="en">
<head><meta charset="utf-8"/></head>
<body bgcolor="gold" onload="fetchValues()">
<H1>Big numbers</H1><P>
<FORM name=calc onSubmit="fetchValues(); return false;">
<B>INPUT DEC-><input type=submit name="calc" value="Calc"> <input type="text" name="eval" value="32432439*12" size="300"><br>
BASE <input type="text" name="formbase" value="10" size="10"><br>
This calculation<input type="text" name="outbase" value="" size="60"><br>
<FONT COLOR="white">
RESULT<br>
<textarea name="result" rows="20" cols="120"></textarea><br>
STATUS</B><br>
<textarea name="stats" cols="120" rows="40" value=""></textarea>
</FORM>
</body>
</html>