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 1 of 3  [1] 2 3  Next page →

#27216 — Best search algorithm to find a condition within a range.

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> 

 












 

[toc] | [next] | [standalone]

#27218

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)

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

#27219

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?

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

#27220

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

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

#27222

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)

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

#27221

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.

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

#27224

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.

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

#27227

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.

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

#27231

Den tisdag 7 april 2015 kl. 15:23:47 UTC+2 skrev Ben Bacarisse:
> 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.

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.

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

#27235

jonas.thornvall@gmail.com writes:

> Den tisdag 7 april 2015 kl. 15:23:47 UTC+2 skrev Ben Bacarisse:
>> jonas.thornvall@gmail.com writes:
<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.
>
> 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?

-- 
Ben.

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

#27238

Den tisdag 7 april 2015 kl. 17:31:49 UTC+2 skrev Ben Bacarisse:
> jonas.thornvall@gmail.com writes:
> 
> > Den tisdag 7 april 2015 kl. 15:23:47 UTC+2 skrev Ben Bacarisse:
> >> jonas.thornvall@gmail.com writes:
> <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.
> >
> > 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?
> 
> -- 
> Ben.

Yes the binary search have better time than linear add.

Example base 4294967295

number = 3243787983738733984329847327432738783449058438543890486865659065465474857454395

Find value of first digitplace (higest), using commaseparated notation it will be a value between 1 and (4294967295-1)

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

#27244

jonas.thornvall@gmail.com writes:

> Den tisdag 7 april 2015 kl. 17:31:49 UTC+2 skrev Ben Bacarisse:
>> jonas.thornvall@gmail.com writes:
>> 
>> > Den tisdag 7 april 2015 kl. 15:23:47 UTC+2 skrev Ben Bacarisse:
>> >> jonas.thornvall@gmail.com writes:
>> <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.
>> >
>> > 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?
>
> Yes the binary search have better time than linear add.
>
> Example base 4294967295

That's a very odd base to use.  4294967296 would, on the other hand, be
quite a reasonable choice in some contexts.  Not for ECMAScript, though,
because, in general, the best base to use is the largest one where you
can get an exact product of two digits from the underlying programming
environment.

> number =
> 3243787983738733984329847327432738783449058438543890486865659065465474857454395
>
> Find value of first digitplace (higest), using commaseparated notation
> it will be a value between 1 and (4294967295-1)

It's 28.

If you want to represent that number in the specified base, you should
just generate the digits as normal -- taking the remainder and
dividing.  You have invented a problem that can be avoided altogether if
you choose not to find the most significant digit first.

If, however, you only want to find the leading digit, there may be a
better way, but it's likely to use logarithms:

  log(3243787...54395)/log(4294967295) = 8.15..
  floor(3243787...54395 / 4294967295^8) = 28

-- 
Ben.

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

#27286

In comp.lang.javascript message <878ue3zrws.fsf@bsb.me.uk>, Tue, 7 Apr
2015 19:58:59, Ben Bacarisse <ben.usenet@bsb.me.uk> posted:

>If, however, you only want to find the leading digit, there may be a
>better way, but it's likely to use logarithms:
>
>  log(3243787...54395)/log(4294967295) = 8.15..
>  floor(3243787...54395 / 4294967295^8) = 28


It seems probable that, with real rather than integer arithmetic, there
will be at least one case in which the small errors in the division and
logarithms will put the value on the wrong side of an integer, in the
opinion of float.

So either one must test all possible cases or do some rather difficult
reasoning to prove that it always works correctly, or accept the risk of
occasional error.


In another post, you (IIRC) rightly implied that it is sufficiently easy
to do multi-length arithmetic to a base up to the integer part of the
square root of the natural largest integer that the computing engine can
handle.

But, having implemented that engine, one has the calculating part of an
arithmetic unit which can handle much larger numbers, and which can
therefore be made to calculate to a base up to floor(sqrt(those
numbers)).  And so on.

I have made a system, albeit not in JavaScript, which will calculate in
any base B in 2..15, using integers up to B^65000 or B^1e8 ... ...

-- 
 (c) John Stockton, Surrey, UK.  ¬@merlyn.demon.co.uk   Turnpike v6.05   MIME.
   Web  <http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links.
 Proper <= 4-line sig. separator as above, a line exactly "-- " (SonOfRFC1036)
 Do not Mail News to me. Before a reply, quote with ">" or "> " (SonOfRFC1036)

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

#27288

Dr J R Stockton <reply1500@merlyn.demon.co.uk.invalid> writes:

> In comp.lang.javascript message <878ue3zrws.fsf@bsb.me.uk>, Tue, 7 Apr
> 2015 19:58:59, Ben Bacarisse <ben.usenet@bsb.me.uk> posted:
>
>>If, however, you only want to find the leading digit, there may be a
>>better way, but it's likely to use logarithms:
>>
>>  log(3243787...54395)/log(4294967295) = 8.15..
>>  floor(3243787...54395 / 4294967295^8) = 28
>
>
> It seems probable that, with real rather than integer arithmetic, there
> will be at least one case in which the small errors in the division and
> logarithms will put the value on the wrong side of an integer, in the
> opinion of float.
>
> So either one must test all possible cases or do some rather difficult
> reasoning to prove that it always works correctly, or accept the risk of
> occasional error.

Yes, it's not hard to test both possible powers so the occasional error
hardly matters.  In fact, one might even use a very crude log function
(maybe just take the digit length?), accept the ensuing errors, and test
the possible powers.

BTW, I make not claim that this is of any value (I can't see how it
could be, really) just that it's a way to do what the OP (incorrectly,
in my option) claimed to want.

<snip>
-- 
Ben.

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

#27239

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.

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

#27240

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.

Well i do not even worry about the multiplications divisions subtractions and additions. Because it is already implemented i worry about the comparissons, because there is no straightforward way to make them bignum.

The opereations is simply done on arrays without hazzle, but the comparissons is what worries me. And there is no real good way to see what happens, because when something overflow it is not supported.

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

#27243

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

> Well i do not even worry about the multiplications divisions
> subtractions and additions. Because it is already implemented i worry
> about the comparissons, because there is no straightforward way to make
> them bignum. 

How come?

Integer comparison [1 's'] is just substraction 
followed by testing for zero, positive or negative.

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

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

#27245

Evertjan. wrote:

> jonas.thornvall@gmail.com wrote on 07 apr 2015 in comp.lang.javascript:
>> Well i do not even worry about the multiplications divisions
>> subtractions and additions. Because it is already implemented i worry
>> about the comparissons, because there is no straightforward way to make
>> them bignum.

Q.E.D.

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

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

#27246

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

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

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

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

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

#27247

Den tisdag 7 april 2015 kl. 22:19:54 UTC+2 skrev Evertjan.:
> Thomas 'PointedEars' Lahn <PointedEars@web.de> wrote on 07 apr 2015 in 
> comp.lang.javascript:
> 
> >> 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.
> 
> Even so, it is probable faster to compare the "length" of such 
> representations, and just in case of equality, compare the contents. 
> 
> -- 
> Evertjan.
> The Netherlands.
> (Please change the x'es to dots in my emailaddress)

Good idea

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

Page 1 of 3  [1] 2 3  Next page →

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

csiph-web