Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.javascript > #27216 > unrolled thread

Best search algorithm to find a condition within a range.

Back to article view | Back to comp.lang.javascript

Contents

  Best search algorithm to find a condition within a range. jonas.thornvall@gmail.com - 2015-04-07 02:43 -0700
    Re: Best search algorithm to find a condition within a range. "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2015-04-07 13:07 +0200
      Re: Best search algorithm to find a condition within a range. jonas.thornvall@gmail.com - 2015-04-07 04:38 -0700
        Re: Best search algorithm to find a condition within a range. jonas.thornvall@gmail.com - 2015-04-07 04:48 -0700
        Re: Best search algorithm to find a condition within a range. "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2015-04-07 14:49 +0200
    Re: Best search algorithm to find a condition within a range. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-04-07 13:27 +0100
      Re: Best search algorithm to find a condition within a range. jonas.thornvall@gmail.com - 2015-04-07 06:04 -0700
        Re: Best search algorithm to find a condition within a range. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-04-07 14:23 +0100
          Re: Best search algorithm to find a condition within a range. jonas.thornvall@gmail.com - 2015-04-07 06:54 -0700
            Re: Best search algorithm to find a condition within a range. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-04-07 16:31 +0100
              Re: Best search algorithm to find a condition within a range. jonas.thornvall@gmail.com - 2015-04-07 08:59 -0700
                Re: Best search algorithm to find a condition within a range. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-04-07 19:58 +0100
                  Re: Best search algorithm to find a condition within a range. Dr J R Stockton <reply1500@merlyn.demon.co.uk.invalid> - 2015-04-09 23:08 +0100
                    Re: Best search algorithm to find a condition within a range. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-04-10 00:02 +0100
              Re: Best search algorithm to find a condition within a range. Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2015-04-07 18:37 +0200
                Re: Best search algorithm to find a condition within a range. jonas.thornvall@gmail.com - 2015-04-07 09:55 -0700
                  Re: Best search algorithm to find a condition within a range. "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2015-04-07 20:30 +0200
                    Re: Best search algorithm to find a condition within a range. Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2015-04-07 20:58 +0200
                      Re: Best search algorithm to find a condition within a range. "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2015-04-07 22:19 +0200
                        Re: Best search algorithm to find a condition within a range. jonas.thornvall@gmail.com - 2015-04-08 00:14 -0700
                          Re: Best search algorithm to find a condition within a range. "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2015-04-08 10:55 +0200
                        Re: Best search algorithm to find a condition within a range. Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2015-04-09 13:03 +0200
                        Re: Best search algorithm to find a condition within a range. "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2015-04-09 14:11 +0200
                          Re: Best search algorithm to find a condition within a range. "Christoph M. Becker" <cmbecker69@arcor.de> - 2015-04-09 14:55 +0200
                            Re: Best search algorithm to find a condition within a range. "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2015-04-09 15:20 +0200
                              Re: Best search algorithm to find a condition within a range. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-04-09 14:49 +0100
                                Re: Best search algorithm to find a condition within a range. Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2015-04-09 16:10 +0200
                                Re: Best search algorithm to find a condition within a range. "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2015-04-09 16:17 +0200
                              Re: Best search algorithm to find a condition within a range. jonas.thornvall@gmail.com - 2015-04-09 07:22 -0700
                                Re: Best search algorithm to find a condition within a range. "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2015-04-09 16:44 +0200
                                  Re: Best search algorithm to find a condition within a range. jonas.thornvall@gmail.com - 2015-04-09 07:57 -0700
                                    Re: Best search algorithm to find a condition within a range. jonas.thornvall@gmail.com - 2015-04-09 08:05 -0700
                                      Re: Best search algorithm to find a condition within a range. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-04-09 17:04 +0100
                            Re: Best search algorithm to find a condition within a range. Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2015-04-09 16:14 +0200
                              Re: Best search algorithm to find a condition within a range. "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2015-04-09 16:34 +0200
                                Re: Best search algorithm to find a condition within a range. Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2015-04-09 17:39 +0200
                                  Re: Best search algorithm to find a condition within a range. "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2015-04-09 18:04 +0200
                                    Re: Best search algorithm to find a condition within a range. Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2015-04-09 18:26 +0200
                                      Re: Best search algorithm to find a condition within a range. "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2015-04-09 22:13 +0200
                Re: Best search algorithm to find a condition within a range. jonas.thornvall@gmail.com - 2015-04-07 10:00 -0700
      Re: Best search algorithm to find a condition within a range. jonas.thornvall@gmail.com - 2015-04-07 06:16 -0700
        Re: Best search algorithm to find a condition within a range. "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2015-04-07 15:28 +0200
          Re: Best search algorithm to find a condition within a range. jonas.thornvall@gmail.com - 2015-04-07 06:58 -0700
            Re: Best search algorithm to find a condition within a range. "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2015-04-07 20:25 +0200
        Re: Best search algorithm to find a condition within a range. Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-04-07 14:33 +0100

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

#27248

jonas.thornvall@gmail.com wrote on 08 apr 2015 in comp.lang.javascript:

>> Numbers are not "shorter" or "longer", 
>> just their string representations are.
>> 
>> Even so, it is probable faster to compare the "length" of such 
>> representations, and just in case of equality, compare the contents. 

[please do not quote signatures, 
any good newsreaders strips them automagically]

> Good idea

This is just the way internal floating point comparison 
usually works:

First both values are normalized to the binary 0.---
then the resulting exponents are compared, 
then only if these are equal the matissae are compared.

==============

If you want to do this in [base 10] integer arythmetic,
the nice thing is that you can compare the above "content",
left-to-right only as long as the characters are the same,
promissing enormous performance gain.

-- 
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)

[toc] | [prev] | [next] | [standalone]

#27259

Evertjan. wrote:

> Thomas 'PointedEars' Lahn […] wrote:
>>> How come?
>>> Integer comparison [1 's'] is just substraction
>>> followed by testing for zero, positive or negative.
>> I would simply pad the shorter number with zeroes on the left and compare
>> the strings instead.  After all, "0" < "9" < "A" < "Z".
> 
> Numbers are not "shorter" or "longer",
> just their string representations are.

You know what I mean.  It is not possible to have arbitrary 
precision without deferring to string values at some point.

> Even so, it is probable faster to compare the "length" of such
> representations, and just in case of equality, compare the contents.

It *might* be faster to compare the length first.  The problem is that it is 
implementation-dependent.  ECMAScript String values do not have a 
*specified* length byte such as strings in e.g., Pascal, and the “length” 
property is one of String *instances*, not primitive string values.  So 
unless the implementation optimizes access, during instantiation of the 
String instance the entire string value needs to be read in order to 
determine its length.  However, in the worst case, the entire string value 
also needs to be read in order to compare it against another string.  In the 
worst case, both strings will be read twice if you compare their lengths 
first.

In V8 in Chromium “41.0.2272.118 Built on 8.0, running on Debian 8.0 (64-
bit)” comparing the length first is slower than not comparing it.

-- 
PointedEars
FAQ: <http://PointedEars.de/faq> | SVN: <http://PointedEars.de/wsvn/>
Twitter: @PointedEars2 | ES Matrix: <http://PointedEars.de/es-matrix>
Please do not cc me. / Bitte keine Kopien per E-Mail.

[toc] | [prev] | [next] | [standalone]

#27260

Thomas 'PointedEars' Lahn <PointedEars@web.de> wrote on 09 apr 2015 in
comp.lang.javascript: 

> Evertjan. wrote:
> 
>> Thomas 'PointedEars' Lahn […] wrote:
>>>> How come?
>>>> Integer comparison [1 's'] is just substraction
>>>> followed by testing for zero, positive or negative.
>>> I would simply pad the shorter number with zeroes on the left and
>>> compare the strings instead.  After all, "0" < "9" < "A" < "Z".
>> 
>> Numbers are not "shorter" or "longer",
>> just their string representations are.
> 
> You know what I mean. 

I don't know what you mean, 
also because numbers "are" not their notation.

> It is not possible to have arbitrary 
> precision without deferring to string values at some point.

This is not about arbitrary precision.
 
>> Even so, it is probable faster to compare the "length" of such
>> representations, and just in case of equality, compare the contents.
> 
> It *might* be faster to compare the length first.  The problem is that
> it is implementation-dependent. 

It is not implementation-dependent, see below.

> ECMAScript String values do not have a 
> *specified* length byte such as strings in e.g., Pascal, and the
> “length” property is one of String *instances*, not primitive string
> values.  So unless the implementation optimizes access, the during
> instantiation of the String instance the entire string value needs to be
> read in order to determine its length.  However, in the worst case, the
> entire string value also needs to be read in order to compare it against
> another string.  In the worst case, both strings will be read twice if
> you compare their lengths first.
> 
> In V8 in Chromium “41.0.2272.118 Built on 8.0, running on Debian 8.0
> (64- bit)” comparing the length first is slower than not comparing it.

You are missing the point again. 

The advice given was to add zero's in front of the "shortest" stringified 
number.

There is no way to do that without first retrieving the "length" of both
and assessing the difference to know how many zerows to add.

So the length difference so already there, and there is no need to add the 
zero characters when this difference != 0, since that value already answers 
the comparison. And there is no need to add them when they are equal too, 
btw.


-- 
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)

[toc] | [prev] | [next] | [standalone]

#27262

Evertjan. wrote:

> The advice given was to add zero's in front of the "shortest" stringified 
> number.
> 
> There is no way to do that without first retrieving the "length" of both
> and assessing the difference to know how many zerows to add.
> 
> So the length difference so already there, and there is no need to add the 
> zero characters when this difference != 0, since that value already answers 
> the comparison. And there is no need to add them when they are equal too, 
> btw.

Why would someone try to do integer arithmetic on strings?  I would
suggest to use a large base, where each digit is an element of an array.
 IIRC Ben (Bacarisse) has already suggest this.

-- 
Christoph M. Becker

[toc] | [prev] | [next] | [standalone]

#27263

"Christoph M. Becker" <cmbecker69@arcor.de> wrote on 09 apr 2015 in 
comp.lang.javascript:

> Why would someone try to do integer arithmetic on strings?  I would
> suggest to use a large base, where each digit is an element of an array.
>  IIRC Ben (Bacarisse) has already suggest this.

Quite, but that was the premisse of the OP, I seem to remember.

-- 
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)

[toc] | [prev] | [next] | [standalone]

#27264

"Evertjan." <exxjxw.hannivoort@inter.nl.net> writes:

> "Christoph M. Becker" <cmbecker69@arcor.de> wrote on 09 apr 2015 in 
> comp.lang.javascript:
>
>> Why would someone try to do integer arithmetic on strings?  I would
>> suggest to use a large base, where each digit is an element of an array.
>>  IIRC Ben (Bacarisse) has already suggest this.
>
> Quite, but that was the premisse of the OP, I seem to remember.

No, the OP was talking about arbitrary bases using an array to store the
"digits".  I'm not sure when strings got in on the act.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#27265

Ben Bacarisse wrote:

> "Evertjan." <exxjxw.hannivoort@inter.nl.net> writes:
>> "Christoph M. Becker" <cmbecker69@arcor.de> wrote on 09 apr 2015 in
>> comp.lang.javascript:
>>> Why would someone try to do integer arithmetic on strings?  I would
>>> suggest to use a large base, where each digit is an element of an array.
>>>  IIRC Ben (Bacarisse) has already suggest this.
>> Quite, but that was the premisse of the OP, I seem to remember.
> 
> No, the OP was talking about arbitrary bases using an array to store the
> "digits".  I'm not sure when strings got in on the act.

It is actually a bit of both, cf. the OP of the previous thread started by 
them: <news:22e81bec-1e4d-4022-9e14-f72074c17015@googlegroups.com>

-- 
PointedEars
FAQ: <http://PointedEars.de/faq> | SVN: <http://PointedEars.de/wsvn/>
Twitter: @PointedEars2 | ES Matrix: <http://PointedEars.de/es-matrix>
Please do not cc me. / Bitte keine Kopien per E-Mail.

[toc] | [prev] | [next] | [standalone]

#27267

Ben Bacarisse <ben.usenet@bsb.me.uk> wrote on 09 apr 2015 in 
comp.lang.javascript:

> "Evertjan." <exxjxw.hannivoort@inter.nl.net> writes:
> 
>> "Christoph M. Becker" <cmbecker69@arcor.de> wrote on 09 apr 2015 in 
>> comp.lang.javascript:
>>
>>> Why would someone try to do integer arithmetic on strings?  I would
>>> suggest to use a large base, where each digit is an element of an array.
>>>  IIRC Ben (Bacarisse) has already suggest this.
>>
>> Quite, but that was the premisse of the OP, I seem to remember.
> 
> No, the OP was talking about arbitrary bases using an array to store the
> "digits".  I'm not sure when strings got in on the act.

Okay.

Even there comparing the length [= number of array items] of two integer 
value arrays is faster than adding zero filled items for the same reasons. 

So my point stands.

-- 
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)

[toc] | [prev] | [next] | [standalone]

#27269

Den torsdag 9 april 2015 kl. 15:21:10 UTC+2 skrev Evertjan.:
> "Christoph M. Becker" <cmbecker69@arcor.de> wrote on 09 apr 2015 in 
> comp.lang.javascript:
> 
> > Why would someone try to do integer arithmetic on strings?  I would
> > suggest to use a large base, where each digit is an element of an array.
> >  IIRC Ben (Bacarisse) has already suggest this.
> 
> Quite, but that was the premisse of the OP, I seem to remember.
> 
> -- 
> Evertjan.
> The Netherlands.
> (Please change the x'es to dots in my emailaddress)

No every digit(multidigit) is an Array element. I am not sure though howto make a patch work for bases bigger then 32-bit.

[toc] | [prev] | [next] | [standalone]

#27273

jonas.thornvall@gmail.com wrote on 09 apr 2015 in comp.lang.javascript:

> Den torsdag 9 april 2015 kl. 15:21:10 UTC+2 skrev Evertjan.:
>> Quite, but that was the premisse of the OP, I seem to remember.

[please do not quote signatures]

> No every digit(multidigit) is an Array element. I am not sure though
> howto make a patch work for bases bigger then 32-bit. 

Why 32-bit?
What patch? 
Why a patch?

Surely each member of the array just contains an integer 
between 0 and base-1 ?

Oh, perhaps you mean base number 
of more than the Javascript resolution?

Couldn't you then simply do re-entry recursion,
having an array of arrays of arrays ...?

;-)

-- 
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)

[toc] | [prev] | [next] | [standalone]

#27274

Den torsdag 9 april 2015 kl. 16:44:57 UTC+2 skrev Evertjan.:
> jonas.thornvall@gmail.com wrote on 09 apr 2015 in comp.lang.javascript:
> 
> > Den torsdag 9 april 2015 kl. 15:21:10 UTC+2 skrev Evertjan.:
> >> Quite, but that was the premisse of the OP, I seem to remember.
> 
> [please do not quote signatures]
> 
> > No every digit(multidigit) is an Array element. I am not sure though
> > howto make a patch work for bases bigger then 32-bit. 
> 
> Why 32-bit?
> What patch? 
> Why a patch?
> 
> Surely each member of the array just contains an integer 
> between 0 and base-1 ?
> 
> Oh, perhaps you mean base number 
> of more than the Javascript resolution?
> 
> Couldn't you then simply do re-entry recursion,
> having an array of arrays of arrays ...?
> 
> ;-)
> 
> -- 
> Evertjan.
> The Netherlands.
> (Please change the x'es to dots in my emailaddress)

Well i do not read the digits of base into an array right now, i guess if i do that i am of the hook and can use arbitrary sized bases.

[toc] | [prev] | [next] | [standalone]

#27275

Den torsdag 9 april 2015 kl. 16:57:38 UTC+2 skrev jonas.t...@gmail.com:
> Den torsdag 9 april 2015 kl. 16:44:57 UTC+2 skrev Evertjan.:
> > jonas.thornvall@gmail.com wrote on 09 apr 2015 in comp.lang.javascript:
> > 
> > > Den torsdag 9 april 2015 kl. 15:21:10 UTC+2 skrev Evertjan.:
> > >> Quite, but that was the premisse of the OP, I seem to remember.
> > 
> > [please do not quote signatures]
> > 
> > > No every digit(multidigit) is an Array element. I am not sure though
> > > howto make a patch work for bases bigger then 32-bit. 
> > 
> > Why 32-bit?
> > What patch? 
> > Why a patch?
> > 
> > Surely each member of the array just contains an integer 
> > between 0 and base-1 ?
> > 
> > Oh, perhaps you mean base number 
> > of more than the Javascript resolution?
> > 
> > Couldn't you then simply do re-entry recursion,
> > having an array of arrays of arrays ...?
> > 
> > ;-)
> > 
> > -- 
> > Evertjan.
> > The Netherlands.
> > (Please change the x'es to dots in my emailaddress)
> 
> Well i do not read the digits of base into an array right now, i guess if i do that i am of the hook and can use arbitrary sized bases.

Well with the condition i can get the bignumb arithmetic fully working, i am on my way. I think this will be the first implementation ever to use arithmetic in the base of your choice. And i know for a fact that 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 integer it will save operations at high level as well as lowlevel.

That said highbase arithmetic will work alot faster than binary.
And using modular arithmetic you may find out that some 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>

[toc] | [prev] | [next] | [standalone]

#27278

jonas.thornvall@gmail.com writes:
<snip>
> [...] I think this will be the first implementation ever to use
> arithmetic in the base of your choice.

What makes you think that?  I had to do it as a student exercise and I,
in turn sometimes *set* it as an exercise.  I imagine it's been done
hundreds of thousands of times.  When arbitrary-precision arithmetic is
implemented "seriously", the base is usually fixed (at compile time at
least) because for any particular environment there will be a fastest
base, and there is little point in using anything else.

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#27266

Christoph M. Becker wrote:

> Evertjan. wrote:
>> The advice given was to add zero's in front of the "shortest" stringified
>> number.
>> 
>> There is no way to do that without first retrieving the "length" of both
>> and assessing the difference to know how many zerows to add.
>> 
>> So the length difference so already there, and there is no need to add
>> the zero characters when this difference != 0, since that value already
>> answers the comparison. And there is no need to add them when they are
>> equal too, btw.
> 
> Why would someone try to do integer arithmetic on strings?  I would
> suggest to use a large base, where each digit is an element of an array.
>  IIRC Ben (Bacarisse) has already suggest this.

The problem with this approach is that there is no *simple* comparison, 
which was the issue here.

The advantage of it certainly is that you can have bases (with easily 
readable and writeable digits) greater than 36 without too much additional 
effort.  The disadvantages are, in addition to the one on top, that this 
approach requires more memory, and you are also limited by ECMAScript 
integer limits in two ways: one, unless you are using a BigArray 
implementation (which again requires even more memory and runtime) the 
number of digits is limited to the maximum Array length (currently, 2³²−1; 
you can still use properties with numeric names, but .length does not 
change, which makes comparison harder); two, bases cannot be greater than 
the ECMAScript integer *precision* limit (currently, 2⁵³−1).

-- 
PointedEars
FAQ: <http://PointedEars.de/faq> | SVN: <http://PointedEars.de/wsvn/>
Twitter: @PointedEars2 | ES Matrix: <http://PointedEars.de/es-matrix>
Please do not cc me. / Bitte keine Kopien per E-Mail

[toc] | [prev] | [next] | [standalone]

#27271

Thomas 'PointedEars' Lahn <PointedEars@web.de> wrote on 09 apr 2015 in 
comp.lang.javascript:

> The problem with this approach ...

Special trivial cases:

What about base-1, where the array members can only have
the value one and is just like a pack of beans?

Here the comparison is just comparison of the array length
A.length-B.length.

==================

... and base-infinite, where the array only has one member
filled with the actual number? Just like a pack of beans.

Here the comparison is just A[0]-B[0].

==================

... and base-0 where the only available number is zero itself 
and the array is always empty? Just like no pack of beans.

Here the comparison is always (A.length-B.length) = (0-0) [= equal]

===================

Yet to be defined:

... and non-integer bases?

... and negative bases?

-- 
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)

[toc] | [prev] | [next] | [standalone]

#27276

Evertjan. wrote:

> What about base-1

It is not logical to assume that in this newsgroup and in this context 
without further qualification the subject “numeral system” means anything 
but “*positional* numeral system” …

> […]
> [base-0]
> […]
> ... and non-integer bases?
> 
> ... and negative bases?

… with a *positive* *integer* base greater than 1.  Base-1 is not.

Non-integer bases are possible of course (such as base √2), but subject to 
IEEE 754 precision limits to an even greater extent.  They are not practical 
in ECMAScript.

Negative bases are an interesting idea, but their usefulness appears to be 
rather limited:

    (1)₋₂ =                     1 × −2⁰ =  1
    (2)₋₂ =                     2 × −2⁰ =  2
   (10)₋₂ =           1 × −2¹           = −2
   (13)₋₂ =           1 × −2¹ + 3 × −2⁰ =  1
  (100)₋₂ = 1 × −2²                     =  4
  (130)₋₂ = 1 × −2² + 3 × −2¹           = −2

Since you have not quoted a coherent part of what you have been referring 
to, the point you were trying to make, if any, remains in obscurity.

Please skip the attribution novels.

-- 
PointedEars
FAQ: <http://PointedEars.de/faq> | SVN: <http://PointedEars.de/wsvn/>
Twitter: @PointedEars2 | ES Matrix: <http://PointedEars.de/es-matrix>
Please do not cc me. / Bitte keine Kopien per E-Mail.

[toc] | [prev] | [next] | [standalone]

#27277

Thomas 'PointedEars' Lahn <PointedEars@web.de> wrote on 09 apr 2015 in
comp.lang.javascript: 

> It is not logical to assume that in this newsgroup

Don't expand your logical limits to the group.

-- 
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)

[toc] | [prev] | [next] | [standalone]

#27279

Evertjan. wrote:

> Thomas 'PointedEars' Lahn […] wrote […]:
>> It is not logical to assume that in this newsgroup
> 
> Don't expand your logical limits to the group.

I can see now that you are currently not interested in a rational 
discussion, so I will stop discussing with you here.

-- 
PointedEars
FAQ: <http://PointedEars.de/faq> | SVN: <http://PointedEars.de/wsvn/>
Twitter: @PointedEars2 | ES Matrix: <http://PointedEars.de/es-matrix>
Please do not cc me. / Bitte keine Kopien per E-Mail.

[toc] | [prev] | [next] | [standalone]

#27282

Thomas 'PointedEars' Lahn <PointedEars@web.de> wrote on 09 apr 2015 in 
comp.lang.javascript:

> Evertjan. wrote:
> 
>> Thomas 'PointedEars' Lahn […] wrote […]:
>>> It is not logical to assume that in this newsgroup
>> 
>> Don't expand your logical limits to the group.
> 
> I can see now that you are currently not interested in a rational 
> discussion, so I will stop discussing with you here.

If you state you are the ultimate standard of logic and ration,
discussing with you will be futile anyway.

-- 
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)

[toc] | [prev] | [next] | [standalone]

#27241

Den tisdag 7 april 2015 kl. 18:40:03 UTC+2 skrev Thomas 'PointedEars' Lahn:
> Ben Bacarisse wrote:
> 
> > jonas.thornvall@gmail.com writes:
> >> It is about converting bases as fast as possible in a general way that
> >> work for anybase no matter how ***big***. That mean you cannot add up
> >> digits, it is to slow you have to search the digit, doing a binary
> >> search or something better.
> > 
> > Then my point stands.  Why are you "searching" for a digit rather than
> > simply calculating it?  Have you determined that the usual method is too
> > slow and you have some alternative in mind?
> 
> As much as I enjoy a good show, I have to tell you now that you are wasting 
> your time.  Here we have the classical case of overconfidence as pointed out 
> by Richard Cornford: Someone who evidentially has not even mastered the 
> basics of ECMAScript, but is attempting to write an arbitrary precision 
> numeric base converter in and for implementations of ECMAScript.
> 
> -- 
> PointedEars
> FAQ: <http://PointedEars.de/faq> | SVN: <http://PointedEars.de/wsvn/>
> Twitter: @PointedEars2 | ES Matrix: <http://PointedEars.de/es-matrix>
> Please do not cc me. / Bitte keine Kopien per E-Mail.

This worry me...
while(digmult*base<=decNumber){

But i think i solved it beautiful a little further down without need for bignumb.

No digit and base will not cause any overflow...
for (digit=0;digit<=base;digit++) {

And the rest is just arrays in function calls, to bignumb subtractions, multiplicaton and division. Ok division do worry me a bit, but i had a change of strategy today, it will be quite a different kind of division.

[toc] | [prev] | [next] | [standalone]

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.lang.javascript

csiph-web