Best search algorithm to find condition within a range

[jonas.thornvall at gmail.com]

Den torsdag 9 april 2015 kl. 17:04:53 UTC+2 skrev Ian:
> On Thu, Apr 9, 2015 at 8:54 AM,  <jonas.thornvall at gmail.com> wrote:
> > 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?
> 
> Dunno, I have no interest in verifying your code for you. Especially
> since this is a Python list and said code is not Python.
> 
> If you want to build confidence that your code works, I suggest
> writing some unit tests for it. (I'd also suggest keeping it separate
> from your html in a .js file, which would make it a lot easier to test
> and reuse.)

Well with the condition i can get the bignumb arithmetic fully working, i am on my way of working bignumb arithmetic in anybase. 

I think this will be the first implementation ever to use arithmetic in the base of your choice. 

And i know for a fact (i've factored RSA in the 200 digit range on a 486 in a couple of hours 98-) 

So there is more to this than fancy overlay, it is about the digit representation at the binary level, and how the binary groups interpretated.

So in the end, even with none optimised type like Javascript integer it will save operations at high level as well as lowlevel.

That said highlevel and highbase arithmetic will work alot faster than binary.
And using modular arithmetic you may find out that some operations requiering exponential work like factoring will turn out to be done in polynomial time.

<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>