Asp Forum - Best search algorithm to find a condition within a range.

JT

4/7/2015 9:44:00 AM

I want todo faster baseconversion for very big bases like base 1 000 000, so instead of adding up digits i search it.

I need the fastest algorithm to find the relation to a decimal number.
Digmult is an instance of base at a digitplace (base^x) what i try to find is the digit for the below condition is true and the loop break.

*********************************
for (digit=0;digit<=base;digit++) {
if((digit+1)*digmult>decNumber)break;
}
*********************************

So i am looking for the digit where following condition true.

if((digit)*digmult<decNumber) AND if((digit+1)*digmult>decNumber) then BREAK;

One could start at half base searching, but then i Think i've read that using 1/3 closing in faster?

I Think also i remember that if the search space so big that at least 22 or 23 guesses, needed.A random Oracle may even faster?

Just pick up a number and get lucky, is it any truth to that?

Below the actual algorithm.

<SCRIPT LANGUAGE="Javascript">
//CONVERT A DECIMAL NUMBER INTO ANYBASE
function newbase(decNumber,base){
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;
}

var out= [];
base=256;
number=854544;
out=newbase(number,base);
out.reverse();
document.write("Number = ",out,"<BR>");
</script>

45 Answers

Evertjan.

4/7/2015 11:07:00 AM

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

> if((digit)*digmult<decNumber) AND if((digit+1)*digmult>decNumber) then
> BREAK;

"if ... and if ... then" what language???

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

if (digit*digmult<decNumber) && ((digit+1)*digmult>decNumber)) ....;

*** or [dividing both sides by digmult]

if ( (digit < decNumber / digmult) && (digit + 1 > decNumber / digmult) )
.....;

*** or [externalizing decNumber/digmult ]

temp = decNumber / digmult;
if ( (digit < temp) && (digit + 1 > temp) ) ....;

*** or [substracting digit from both sides]

temp = decNumber / digmult;
if ( (0 < temp-digit) && (0 + 1 > temp-digit) ) ....;

*** or [externalizing digit]

temp = decNumber / digmult - digit;
if ( (0 < temp) && (1 > temp) ) ....;

*** or [looks better]

temp = decNumber / digmult - digit;
if ( (temp > 0) && (temp < 1) ) ....;

*** or [using function instead of temp variable]

function between(v,a,b) {return (v>a) && (v<b);};

if ( between(decNumber/digmult-digit, 0, 1) ) ....;

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

JT

4/7/2015 11:39:00 AM

Den tisdag 7 april 2015 kl. 13:07:16 UTC+2 skrev Evertjan.:
> jonas.thornvall@gmail.com wrote on 07 apr 2015 in comp.lang.javascript:
>
> > if((digit)*digmult<decNumber) AND if((digit+1)*digmult>decNumber) then
> > BREAK;
>
> "if ... and if ... then" what language???
>
> =================
>
> if (digit*digmult<decNumber) && ((digit+1)*digmult>decNumber)) ....;
>
> *** or [dividing both sides by digmult]
>
> if ( (digit < decNumber / digmult) && (digit + 1 > decNumber / digmult) )
> ....;
>
> *** or [externalizing decNumber/digmult ]
>
> temp = decNumber / digmult;
> if ( (digit < temp) && (digit + 1 > temp) ) ....;
>
> *** or [substracting digit from both sides]
>
> temp = decNumber / digmult;
> if ( (0 < temp-digit) && (0 + 1 > temp-digit) ) ....;
>
> *** or [externalizing digit]
>
> temp = decNumber / digmult - digit;
> if ( (0 < temp) && (1 > temp) ) ....;
>
> *** or [looks better]
>
> temp = decNumber / digmult - digit;
> if ( (temp > 0) && (temp < 1) ) ....;
>
> *** or [using function instead of temp variable]
>
> function between(v,a,b) {return (v>a) && (v<b);};
>
> if ( between(decNumber/digmult-digit, 0, 1) ) ....;
>
> --
> Evertjan.
> The Netherlands.
> (Please change the x'es to dots in my emailaddress)

Sorry about that pseudocode, but what about the problem is really half interval/ binary search the fastest?

I Think that 1/3 flipping Evert second is faster 2/3 or?

And what if the numbers really big would using a random Oracle be faster?

JT

4/7/2015 11:48:00 AM

Den tisdag 7 april 2015 kl. 13:39:02 UTC+2 skrev jonas.t...@gmail.com:
> Den tisdag 7 april 2015 kl. 13:07:16 UTC+2 skrev Evertjan.:
> > jonas.thornvall@gmail.com wrote on 07 apr 2015 in comp.lang.javascript:
> >
> > > if((digit)*digmult<decNumber) AND if((digit+1)*digmult>decNumber) then
> > > BREAK;
> >
> > "if ... and if ... then" what language???
> >
> > =================
> >
> > if (digit*digmult<decNumber) && ((digit+1)*digmult>decNumber)) ....;
> >
> > *** or [dividing both sides by digmult]
> >
> > if ( (digit < decNumber / digmult) && (digit + 1 > decNumber / digmult) )
> > ....;
> >
> > *** or [externalizing decNumber/digmult ]
> >
> > temp = decNumber / digmult;
> > if ( (digit < temp) && (digit + 1 > temp) ) ....;
> >
> > *** or [substracting digit from both sides]
> >
> > temp = decNumber / digmult;
> > if ( (0 < temp-digit) && (0 + 1 > temp-digit) ) ....;
> >
> > *** or [externalizing digit]
> >
> > temp = decNumber / digmult - digit;
> > if ( (0 < temp) && (1 > temp) ) ....;
> >
> > *** or [looks better]
> >
> > temp = decNumber / digmult - digit;
> > if ( (temp > 0) && (temp < 1) ) ....;
> >
> > *** or [using function instead of temp variable]
> >
> > function between(v,a,b) {return (v>a) && (v<b);};
> >
> > if ( between(decNumber/digmult-digit, 0, 1) ) ....;
> >
> > --
> > Evertjan.
> > The Netherlands.
> > (Please change the x'es to dots in my emailaddress)
>
> Sorry about that pseudocode, but what about the problem is really half interval/ binary search the fastest?
>
> I Think that 1/3 flipping Evert second is faster 2/3 or?
>
> And what if the numbers really big would using a random Oracle be faster?

Sorry it seem i have some auto insert make funny choices, (__every__ second time).

Ben Bacarisse

4/7/2015 12:27:00 PM

jonas.thornvall@gmail.com writes:

> I want todo faster baseconversion for very big bases like base 1 000
> 000, so instead of adding up digits i search it.

The size of the base is immaterial, provided that it is in the range for
which arithmetic operations are exact. 1,000,000 is well within that
range.

<snip>
> <SCRIPT LANGUAGE="Javascript">
> //CONVERT A DECIMAL NUMBER INTO ANYBASE
> function newbase(decNumber,base){

Your terms are wrong, and I don't think this is just a trivial detail --
I think maybe it points to something you've misunderstood. The value in
"decNumber" is not decimal -- it's just a number. Internally it is
represented in a very well-defined format that uses binary for both a
fraction and an exponent, but you don't need to care about that. You
just want to do arithmetic on it. (Maybe one day you will write a
routine like this that takes a bignum in base X and converts it to
bignum in base Y, but for the moment, you don't seem to be doing that at
all.)

Anyway, the algorithm for representing a number in base B is the same
whatever the base is: the least significant digit is obtained by using
the remainder operation (%) and you can move on to the next one by
dividing the number by the base. I think you know this already.

<snip>
--
Ben.

Evertjan.

4/7/2015 12:49:00 PM

jonas.thornvall@gmail.com wrote on 07 apr 2015 in comp.lang.javascript:
> I wrote:
>> *** or [using function instead of temp variable]
>>
>> function between(v,a,b) {return (v>a) && (v<b);};
>>
>> if ( between(decNumber/digmult-digit, 0, 1) ) ....;
>
> Sorry about that pseudocode, but what about the problem is really half
> interval/ binary search the fastest?

Is division slower than twice nearly the same multiplication?

But more so about programming style,
"if ( between( decNumber/digmult-digit, 0, 1 ) )"
being visually more inspiring, imho, and [so?] less error prone.

> I Think that 1/3 flipping Evert second is faster 2/3 or?

Sorry, don't understand, is only part of my name.

> And what if the numbers really big would using a random Oracle be
> faster?

You would have to go to Delphi every time!

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

JT

4/7/2015 1:05:00 PM

Den tisdag 7 april 2015 kl. 14:27:36 UTC+2 skrev Ben Bacarisse:
> jonas.thornvall@gmail.com writes:
>
> > I want todo faster baseconversion for very big bases like base 1 000
> > 000, so instead of adding up digits i search it.
>
> The size of the base is immaterial, provided that it is in the range for
> which arithmetic operations are exact. 1,000,000 is well within that
> range.
>
> <snip>
> > <SCRIPT LANGUAGE="Javascript">
> > //CONVERT A DECIMAL NUMBER INTO ANYBASE
> > function newbase(decNumber,base){
>
> Your terms are wrong, and I don't think this is just a trivial detail --
> I think maybe it points to something you've misunderstood. The value in
> "decNumber" is not decimal -- it's just a number.

No you are wrong, the input is an integer and that is a number encoded in base 10, there is no such thing as just a number.

Internally it is
> represented in a very well-defined format that uses binary for both a
> fraction and an exponent, but you don't need to care about that.

>You
> just want to do arithmetic on it. (Maybe one day you will write a
> routine like this that takes a bignum in base X and converts it to
> bignum in base Y, but for the moment, you don't seem to be doing that at
> all.)

I will do very large base arithmetic once i changed the algorithms operations to use bignumb multiplication, division, add and subtraction.

> Anyway, the algorithm for representing a number in base B is the same
> whatever the base is: the least significant digit is obtained by using
> the remainder operation (%) and you can move on to the next one by
> dividing the number by the base. I think you know this already.

That is not base 8 it is base 256, the algorithm convert decimals into any base even into binary base, although not binary they are decimal values encoded into base 2.

You can try whatever base, and the encoding is correct.

I aim to replace the slow add when dealing with real big bases with a search.

> <snip>
> --
> Ben.

JT

4/7/2015 1:17:00 PM

Den tisdag 7 april 2015 kl. 14:27:36 UTC+2 skrev Ben Bacarisse:
> jonas.thornvall@gmail.com writes:
>
> > I want todo faster baseconversion for very big bases like base 1 000
> > 000, so instead of adding up digits i search it.
>
> The size of the base is immaterial, provided that it is in the range for
> which arithmetic operations are exact. 1,000,000 is well within that
> range.
>
> <snip>
> > <SCRIPT LANGUAGE="Javascript">
> > //CONVERT A DECIMAL NUMBER INTO ANYBASE
> > function newbase(decNumber,base){
>
> Your terms are wrong, and I don't think this is just a trivial detail --
> I think maybe it points to something you've misunderstood. The value in
> "decNumber" is not decimal -- it's just a number. Internally it is
> represented in a very well-defined format that uses binary for both a
> fraction and an exponent, but you don't need to care about that. You
> just want to do arithmetic on it. (Maybe one day you will write a
> routine like this that takes a bignum in base X and converts it to
> bignum in base Y, but for the moment, you don't seem to be doing that at
> all.)
>
> Anyway, the algorithm for representing a number in base B is the same
> whatever the base is: the least significant digit is obtained by using
> the remainder operation (%) and you can move on to the next one by
> dividing the number by the base. I think you know this already.
>
> <snip>
> --
> Ben.

Regarding the terms what terms is wrong?
There ain't no other name for decimal number then a decimal encoded number. Integers are just decimal encoded numbers. If you work in base 8 they are not integers. They are integers because they use 10 unique digits.

And a digit is just one of those unique digit 0-9.
I probably should named digits to digitplace but it was to long.

Digmult is a multiple of the exponent using a specific base at a specific digiplace, so i can hardly name it exponent.

I think i named my variable straightforward.

Ben Bacarisse

4/7/2015 1:24:00 PM

jonas.thornvall@gmail.com writes:

> Den tisdag 7 april 2015 kl. 14:27:36 UTC+2 skrev Ben Bacarisse:
>> jonas.thornvall@gmail.com writes:
>>
>> > I want todo faster baseconversion for very big bases like base 1 000
>> > 000, so instead of adding up digits i search it.
>>
>> The size of the base is immaterial, provided that it is in the range for
>> which arithmetic operations are exact. 1,000,000 is well within that
>> range.
>>
>> <snip>
>> > <SCRIPT LANGUAGE="Javascript">
>> > //CONVERT A DECIMAL NUMBER INTO ANYBASE
>> > function newbase(decNumber,base){
>>
>> Your terms are wrong, and I don't think this is just a trivial detail --
>> I think maybe it points to something you've misunderstood. The value in
>> "decNumber" is not decimal -- it's just a number.
>
> No you are wrong, the input is an integer and that is a number encoded
> in base 10, there is no such thing as just a number.

The input has happened. The number is now represent internally as
javascript represents numbers. It's not decimal and it's best to ignore
how it is represented.

You are right that, in a computer, there are no things that are "just
numbers" (they always have some sort of representation), but rather
misses the point of my post -- the algorithm to represent a number in
some base does not depend on how the number is represented. You can
simplify some cases, of course -- if you know a number is internally in
binary converting to base 16 can be made very simple, but these are
exceptions, not the general rule.

<snip>
> I aim to replace the slow add when dealing with real big bases with a
> search.

I thought your post was about converting between bases. If it wasn't,
just ignore my comments.

--
Ben.

Evertjan.

4/7/2015 1:28:00 PM

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

> Integers are just decimal encoded numbers. If you work in base 8 they
> are not integers.

Wrong.

An integer is a number without a fraction.

An integer can be written in any number base,
not just in base 10,
but also in base 2 and base 36,
and when the numeric value is the same,
the integers are the same,
independent of what base notation is used.

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

Ben Bacarisse

4/7/2015 1:34:00 PM

jonas.thornvall@gmail.com writes:

> Den tisdag 7 april 2015 kl. 14:27:36 UTC+2 skrev Ben Bacarisse:
>> jonas.thornvall@gmail.com writes:
<snip>
>> > <SCRIPT LANGUAGE="Javascript">
>> > //CONVERT A DECIMAL NUMBER INTO ANYBASE
>> > function newbase(decNumber,base){
>>
>> Your terms are wrong, and I don't think this is just a trivial detail --
>> I think maybe it points to something you've misunderstood. The value in
>> "decNumber" is not decimal -- it's just a number. Internally it is
>> represented in a very well-defined format that uses binary for both a
>> fraction and an exponent, but you don't need to care about that. You
>> just want to do arithmetic on it.
<snip>

> Regarding the terms what terms is wrong?
> There ain't no other name for decimal number then a decimal encoded
> number.

There was no hint in the code that the variable named decNumber held
anything other than an ECMAScript value of type Number. The code did
arithmetic on it using ECMAScript's built in operators that work on
Number values. In what sense do you think (or, more to the point, care)
that it is "decimal"?

<snip>
--
Ben.

comp.lang.javascript

Best search algorithm to find a condition within a range.

JT

Evertjan.

JT

JT

Ben Bacarisse

Evertjan.

JT

JT

Ben Bacarisse

Evertjan.

Ben Bacarisse

x Login to ForumsZone