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

Groups > comp.lang.python > #88572 > unrolled thread

Best search algorithm to find condition within a range

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

Contents

  Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 02:44 -0700
    Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-07 09:29 -0400
      Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 07:10 -0700
        Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-07 10:26 -0400
        Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-08 00:34 +1000
      Re: Best search algorithm to find condition within a range Denis McMahon <denismfmcmahon@gmail.com> - 2015-04-07 14:29 +0000
        Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 07:36 -0700
          Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-08 00:49 +1000
            Re: Best search algorithm to find condition within a range Grant Edwards <invalid@invalid.invalid> - 2015-04-07 15:05 +0000
              Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-07 11:23 -0400
              Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-08 01:37 +1000
              Re: Best search algorithm to find condition within a range MRAB <python@mrabarnett.plus.com> - 2015-04-07 17:02 +0100
          Re: Best search algorithm to find condition within a range MRAB <python@mrabarnett.plus.com> - 2015-04-07 16:00 +0100
            Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 08:43 -0700
              Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-08 08:51 +1000
                Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-08 11:46 +1000
          Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-07 11:04 -0400
          Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 09:06 -0600
            Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 08:47 -0700
              Re: Best search algorithm to find condition within a range Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2015-04-07 20:06 -0400
              Re: Best search algorithm to find condition within a range Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-04-08 12:49 +1200
          Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-08 08:36 +1000
            Re: Best search algorithm to find condition within a range Cameron Simpson <cs@zip.com.au> - 2015-04-08 08:51 +1000
          Re: Best search algorithm to find condition within a range Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2015-04-07 20:01 -0400
          Re: Best search algorithm to find condition within a range albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-18 18:08 +0000
            Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-19 23:02 +1000
              Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-19 17:56 +0300
                Re: Best search algorithm to find condition within a range Gene Heskett <gheskett@wdtv.com> - 2015-04-19 11:17 -0400
                Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-20 12:53 +1000
              Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-19 14:52 -0400
              Re: Best search algorithm to find condition within a range Paul Rubin <no.email@nospam.invalid> - 2015-04-19 13:44 -0700
              Re: Best search algorithm to find condition within a range albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-25 14:49 +0000
        Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 09:18 -0700
    Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 08:32 -0600
      Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 08:40 -0700
        Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-07 12:33 -0400
          Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 10:07 -0700
            Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 11:44 -0600
              Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-08 10:38 +1000
                Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-08 11:18 +1000
                  Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-08 08:37 -0600
                Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 23:19 -0700
                  Re: Best search algorithm to find condition within a range Mel Wilson <mwilson@the-wire.com> - 2015-04-08 13:39 +0000
                    Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-08 07:56 -0700
                      Re: Best search algorithm to find condition within a range Mel Wilson <mwilson@the-wire.com> - 2015-04-08 17:33 +0000
                        Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-08 12:28 -0700
                          Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-08 12:36 -0700
                            Re: Best search algorithm to find condition within a range Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-04-08 21:28 +0100
                          Re: Best search algorithm to find condition within a range Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-04-08 21:29 +0100
            Re: Best search algorithm to find condition within a range Terry Reedy <tjreedy@udel.edu> - 2015-04-07 14:55 -0400
            Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 13:19 -0600
              Re: Best search algorithm to find condition within a range Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-04-07 20:27 +0100
                Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 15:35 -0700
                  Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-07 20:38 -0400
                  Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 17:35 -0600
                    Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-08 00:28 -0700
                      Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-08 08:35 -0600
                    Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-08 00:35 -0700
            Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-08 05:25 +1000
            Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 13:28 -0600
            Re: Best search algorithm to find condition within a range Serhiy Storchaka <storchaka@gmail.com> - 2015-04-07 23:57 +0300
            Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-08 10:18 +1000
              Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-08 07:31 +0300
        Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 14:15 -0600
        Re: Best search algorithm to find condition within a range Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-04-07 21:42 +0100
      Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-08 08:55 +1000
        Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-07 17:30 -0600
    Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-08 08:57 +1000
      Re: Best search algorithm to find condition within a range Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2015-04-08 12:59 +1200
        Re: Best search algorithm to find condition within a range Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-04-08 02:39 +0100
        Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 23:12 -0700
      Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-08 11:49 +1000
        Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-09 12:32 +1000
          Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-09 12:39 +1000
            Re: Best search algorithm to find condition within a range wxjmfauth@gmail.com - 2015-04-08 23:14 -0700
      Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-07 22:50 -0700
      Re: Best search algorithm to find condition within a range wxjmfauth@gmail.com - 2015-04-07 23:07 -0700
        Re: Best search algorithm to find condition within a range wxjmfauth@gmail.com - 2015-04-07 23:18 -0700
          Re: Best search algorithm to find condition within a range Denis McMahon <denismfmcmahon@gmail.com> - 2015-04-08 17:27 +0000
            Re: Best search algorithm to find condition within a range wxjmfauth@gmail.com - 2015-04-08 10:50 -0700
      Re: Best search algorithm to find condition within a range BartC <bc@freeuk.com> - 2015-04-08 22:22 +0100
        Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 01:06 +0300
          Re: Best search algorithm to find condition within a range Chris Kaynor <ckaynor@zindagigames.com> - 2015-04-08 17:01 -0700
          Re: Best search algorithm to find condition within a range BartC <bc@freeuk.com> - 2015-04-09 10:19 +0100
            Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 13:00 +0300
              Re: Best search algorithm to find condition within a range Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2015-04-09 13:57 +0200
                Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 15:45 +0300
                  Re: Best search algorithm to find condition within a range Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2015-04-09 14:56 +0200
                    Re: Best search algorithm to find condition within a range Dave Angel <davea@davea.name> - 2015-04-09 09:19 -0400
                      Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 16:33 +0300
                        Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 16:49 +0300
                        Re: Best search algorithm to find condition within a range Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2015-04-09 15:57 +0200
                          Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 00:08 +1000
                            Re: Best search algorithm to find condition within a range Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2015-04-09 16:53 +0200
                              Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 01:02 +1000
                                Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-09 08:12 -0700
                                Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-10 01:21 +1000
                                  Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 01:36 +1000
                                  Re: Best search algorithm to find condition within a range MRAB <python@mrabarnett.plus.com> - 2015-04-09 17:40 +0100
                            Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-09 07:54 -0700
                              Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-09 09:03 -0600
                                Re: Best search algorithm to find condition within a range jonas.thornvall@gmail.com - 2015-04-09 08:21 -0700
                                  Re: Best search algorithm to find condition within a range Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-09 10:23 -0600
                        Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-10 01:11 +1000
                          Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 01:34 +1000
                            Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-10 02:15 +1000
                              Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 02:36 +1000
                                Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-10 03:49 +1000
                            Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 19:25 +0300
                              Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 02:43 +1000
                                Re: Best search algorithm to find condition within a range Grant Edwards <invalid@invalid.invalid> - 2015-04-09 16:53 +0000
                                  Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 03:00 +1000
                                    Re: Best search algorithm to find condition within a range Grant Edwards <invalid@invalid.invalid> - 2015-04-09 17:44 +0000
                                Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-10 03:41 +1000
                                  Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 04:07 +1000
                                    Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 21:14 +0300
                                  Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 21:11 +0300
                                Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 20:43 +0300
                              Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-10 03:35 +1000
                                Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 03:56 +1000
                                  Re: Best search algorithm to find condition within a range Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-10 23:18 +1000
                                    Re: Best search algorithm to find condition within a range Chris Angelico <rosuav@gmail.com> - 2015-04-10 23:41 +1000
                                Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 21:15 +0300
                                Re: Best search algorithm to find condition within a range Rustom Mody <rustompmody@gmail.com> - 2015-04-10 09:39 -0700
                    Re: Best search algorithm to find condition within a range Marko Rauhamaa <marko@pacujo.net> - 2015-04-09 16:28 +0300

Page 1 of 7  [1] 2 3 4 5 6 7  Next page →

#88572 — Best search algorithm to find 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]

#88575

On 04/07/2015 05:44 AM, jonas.thornvall@gmail.com wrote:
>
>
> I want todo faster baseconversion for very big bases like base 1 000 000, so instead of adding up digits i search it.

For this and most of the following statements:  I can almost guess what 
you're trying to say.  However, I cannot.  No idea why you're adding up 
digits, that sounds like casting out nines.  And in base-N, that would 
be casting out (N-1)'s.

What's the it you're trying to search?

How do you know the baseconversion is the bottleneck, if you haven't 
written any Python code yet?


>
> I need the fastest algorithm to find the relation to a decimal number.

What relation would that be?  Between what and what?

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

You haven't defined a class "Base" yet.  In fact, I don't see any Python 
code in the whole message.

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

You could try integer divide.  That's just something like
      digit = decNumber // digmult
But if you think hard enough you'd realize that


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

If that code were in Python, I could be more motivated to critique it. 
The whole algorithm could be much simpler.  But perhaps there is some 
limitation of javascript that's crippling the code.

How would you do it if you were converting the base by hand?  I 
certainly wouldn't be doing any trial and error.  For each pass, I'd 
calculate quotient and remainder, where remainder is the digit, and 
quotient is the next value you work on.


-- 
DaveA

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

#88576

Den tisdag 7 april 2015 kl. 15:30:36 UTC+2 skrev Dave Angel:
> On 04/07/2015 05:44 AM, jonas.thornvall@gmail.com wrote:
> >
> >
> > I want todo faster baseconversion for very big bases like base 1 000 000, so instead of adding up digits i search it.
> 
> For this and most of the following statements:  I can almost guess what 
> you're trying to say.  However, I cannot.  No idea why you're adding up 
> digits, that sounds like casting out nines.  And in base-N, that would 
> be casting out (N-1)'s.
> 
> What's the it you're trying to search?
> 
> How do you know the baseconversion is the bottleneck, if you haven't 
> written any Python code yet?
> 
> 
> >
> > I need the fastest algorithm to find the relation to a decimal number.
> 
> What relation would that be?  Between what and what?
> 
> > 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.
> >
> 
> You haven't defined a class "Base" yet.  In fact, I don't see any Python 
> code in the whole message.
> 
> >
> > *********************************
> > 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;
> 
> You could try integer divide.  That's just something like
>       digit = decNumber // digmult
> But if you think hard enough you'd realize that
> 
> 
> >
> > 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>
> >
> 
> If that code were in Python, I could be more motivated to critique it. 
> The whole algorithm could be much simpler.  But perhaps there is some 
> limitation of javascript that's crippling the code.
> 
> How would you do it if you were converting the base by hand?  I 
> certainly wouldn't be doing any trial and error.  For each pass, I'd 
> calculate quotient and remainder, where remainder is the digit, and 
> quotient is the next value you work on.
> 
> 
> -- 
> DaveA

I am doing it just like i would do it by hand finding the biggest digit first. To do that i need to know nearest base^exp that is less than the actual number. Add up the digit (multiply) it to the nearest smaller multiple. Subtract that number (base^exp*multiple). 

Divide / Scale down the exponent with base. And record the digit.
And start looking for next digit doing same manipulation until remainder = 0.

And that is what i am doing.

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

#88578

On 04/07/2015 10:10 AM, jonas.thornvall@gmail.com wrote:
> Den tisdag 7 april 2015 kl. 15:30:36 UTC+2 skrev Dave Angel:

    <snip>
>>
>> If that code were in Python, I could be more motivated to critique it.
>> The whole algorithm could be much simpler.  But perhaps there is some
>> limitation of javascript that's crippling the code.
>>
>> How would you do it if you were converting the base by hand?  I
>> certainly wouldn't be doing any trial and error.  For each pass, I'd
>> calculate quotient and remainder, where remainder is the digit, and
>> quotient is the next value you work on.
>>
>>
>> --
>> DaveA
>
> I am doing it just like i would do it by hand finding the biggest digit first. To do that i need to know nearest base^exp that is less than the actual number. Add up the digit (multiply) it to the nearest smaller multiple. Subtract that number (base^exp*multiple).
>
> Divide / Scale down the exponent with base. And record the digit.
> And start looking for next digit doing same manipulation until remainder = 0.
>
> And that is what i am doing.
>

Then I don't know why you do the call to reverse() in the top-level code.

If I were doing it, I'd have no trial and error in the code at all. 
Generate the digits right to left, then reverse them before returning.

For example, if you want to convert 378 to base 10 (it's binary 
internally), you'd divide by 10 to get 37, remainder 8.  Save the 8, and 
loop again.  Divide 37 by 10 and get 3, remainder 7.  Save the 7. Divide 
again by 10 and get 0, remainder 3.  Save the 3

Now you have '8', '7', '3'   So you reverse the list, and get
      '3', '7', '8'



-- 
DaveA

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

#88582

On Wed, Apr 8, 2015 at 12:26 AM, Dave Angel <davea@davea.name> wrote:
> For example, if you want to convert 378 to base 10 (it's binary internally),
> you'd divide by 10 to get 37, remainder 8.  Save the 8, and loop again.
> Divide 37 by 10 and get 3, remainder 7.  Save the 7. Divide again by 10 and
> get 0, remainder 3.  Save the 3
>
> Now you have '8', '7', '3'   So you reverse the list, and get
>      '3', '7', '8'

Technically, it doesn't matter that it's stored in binary. All that
matters is that it's stored in some way that you can perform division
on. I used to do this kind of thing in assembly language, pushing
digits onto the stack, then popping them off afterward. (It's actually
easier to make a column of numbers right-justified, as you can simply
create a buffer of the right size - assuming you're working with a
machine word and can know the maximum size - and populate it from the
far end.) But yes, this is the standard way to do base conversions.

ChrisA

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

#88579

On Tue, 07 Apr 2015 09:29:59 -0400, Dave Angel wrote:

> On 04/07/2015 05:44 AM, jonas.thornvall@gmail.com wrote:

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

> How do you know the baseconversion is the bottleneck, if you haven't
> written any Python code yet?

He doesn't. He doesn't comprehend that as far as a computer is concerned 
an integer has no specific 'base', it's only when presented in a form for 
humans to read that it gets base information added in the representation.

He's making these and other similar errors in the javascript groups too.

I suspect he's one of those people that spends his time thinking up 
elaborate solutions that he has no idea how to implement as a response to 
dreamt up non existent problems.

-- 
Denis McMahon, denismfmcmahon@gmail.com

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

#88584

Den tisdag 7 april 2015 kl. 16:30:15 UTC+2 skrev Denis McMahon:
> On Tue, 07 Apr 2015 09:29:59 -0400, Dave Angel wrote:
> 
> > On 04/07/2015 05:44 AM, jonas.thornvall@gmail.com wrote:
> 
> >> I want todo faster baseconversion for very big bases like base 1 000
> >> 000, so instead of adding up digits i search it.
> 
> > How do you know the baseconversion is the bottleneck, if you haven't
> > written any Python code yet?
> 
> He doesn't. He doesn't comprehend that as far as a computer is concerned 
> an integer has no specific 'base', it's only when presented in a form for 
> humans to read that it gets base information added in the representation.
> 
> He's making these and other similar errors in the javascript groups too.
> 
> I suspect he's one of those people that spends his time thinking up 
> elaborate solutions that he has no idea how to implement as a response to 
> dreamt up non existent problems.
> 
> -- 
> Denis McMahon, denismfmcmahon@gmail.com

Bullshit declare two integers in any language one 7 and one 4 and then write x=7+4; if you find a programming language where that does not yield 11 tell me.

Integers are internally assumed to be base 10 otherwise you could not calculate without giving the base.

All operations on integers addition, subtraction, multiplication and division assume base 10.

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

#88585

On Wed, Apr 8, 2015 at 12:36 AM,  <jonas.thornvall@gmail.com> wrote:
> Bullshit declare two integers in any language one 7 and one 4 and then write x=7+4; if you find a programming language where that does not yield 11 tell me.
>
> Integers are internally assumed to be base 10 otherwise you could not calculate without giving the base.
>
> All operations on integers addition, subtraction, multiplication and division assume base 10.

You misunderstand how computers and programming languages work. What
you're seeing there is that *integer literals* are usually in base 10;
and actually, I can point to plenty of assembly languages where the
default isn't base 10 (it's usually base 16 (hexadecimal) on IBM PCs,
and probably base 8 (octal) on big iron). This is nothing to do with
the internal representation, and all to do with source code.

ChrisA

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

#88589

On 2015-04-07, Chris Angelico <rosuav@gmail.com> wrote:
> On Wed, Apr 8, 2015 at 12:36 AM,  <jonas.thornvall@gmail.com> wrote:
>
>> Integers are internally assumed to be base 10 otherwise you could not
>> calculate without giving the base.
>>
>> All operations on integers addition, subtraction, multiplication and
>> division assume base 10.
>
> You misunderstand how computers and programming languages work. What
> you're seeing there is that *integer literals* are usually in base
> 10; and actually, I can point to plenty of assembly languages where
> the default isn't base 10 (it's usually base 16 (hexadecimal) on IBM
> PCs, and probably base 8 (octal) on big iron).

I'd be curious to see some of those assemblers. I've used dozens of
assemblers over the years for everything from microprocessors with a
few hundred bytes of memory to mini-computers and mainframes.  I've
never seen one that didn't default to base 10 for integer literals.

I'm not saying they don't exist, just that it would be interesting to
see an example of one.

-- 
Grant Edwards               grant.b.edwards        Yow! I'm a fuschia bowling
                                  at               ball somewhere in Brittany
                              gmail.com            

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

#88592

On 04/07/2015 11:05 AM, Grant Edwards wrote:
> On 2015-04-07, Chris Angelico <rosuav@gmail.com> wrote:
>> On Wed, Apr 8, 2015 at 12:36 AM,  <jonas.thornvall@gmail.com> wrote:
>>
>>> Integers are internally assumed to be base 10 otherwise you could not
>>> calculate without giving the base.
>>>
>>> All operations on integers addition, subtraction, multiplication and
>>> division assume base 10.
>>
>> You misunderstand how computers and programming languages work. What
>> you're seeing there is that *integer literals* are usually in base
>> 10; and actually, I can point to plenty of assembly languages where
>> the default isn't base 10 (it's usually base 16 (hexadecimal) on IBM
>> PCs, and probably base 8 (octal) on big iron).
>
> I'd be curious to see some of those assemblers. I've used dozens of
> assemblers over the years for everything from microprocessors with a
> few hundred bytes of memory to mini-computers and mainframes.  I've
> never seen one that didn't default to base 10 for integer literals.
>
> I'm not saying they don't exist, just that it would be interesting to
> see an example of one.
>

I can't "show" it to you, but the assembler used to write microcode on 
the Wang labs 200VP and 2200MVP used hex for all its literals.  I wrote 
the assembler (and matching debugger-assembler), and if we had needed 
other bases I would have taken an extra day to add them in.

That assembler was not available to our customers, as the machine 
shipped with the microcode in readonly form.  Not quite as readonly as 
the Intel processors of today, of course.


Additionally, the MSDOS DEBUG program used hex to enter in its literals, 
if i recall correctly.  Certainly when it disassembled code, it was in hex.


-- 
DaveA

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

#88594

On Wed, Apr 8, 2015 at 1:23 AM, Dave Angel <davea@davea.name> wrote:
> Additionally, the MSDOS DEBUG program used hex to enter in its literals, if
> i recall correctly.  Certainly when it disassembled code, it was in hex.

Indeed, and that's where I learned 80x86 assembly coding (I didn't
have an actual assembler at the time). DEBUG didn't even have the
option of using other bases; other assemblers might give you "decimal
by default, or adorn them for other bases" (eg MASM's &H notation),
but DEBUG forced you to convert to hex manually.

Although, to be fair, DEBUG was said to have a "mini-assembler" built
in. It was never designed to replace actual assemblers, AFAIK. I just
happened to use it that way. :)

ChrisA

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

#88601

On 2015-04-07 16:05, Grant Edwards wrote:
> On 2015-04-07, Chris Angelico <rosuav@gmail.com> wrote:
>> On Wed, Apr 8, 2015 at 12:36 AM,  <jonas.thornvall@gmail.com> wrote:
>>
>>> Integers are internally assumed to be base 10 otherwise you could not
>>> calculate without giving the base.
>>>
>>> All operations on integers addition, subtraction, multiplication and
>>> division assume base 10.
>>
>> You misunderstand how computers and programming languages work. What
>> you're seeing there is that *integer literals* are usually in base
>> 10; and actually, I can point to plenty of assembly languages where
>> the default isn't base 10 (it's usually base 16 (hexadecimal) on IBM
>> PCs, and probably base 8 (octal) on big iron).
>
> I'd be curious to see some of those assemblers. I've used dozens of
> assemblers over the years for everything from microprocessors with a
> few hundred bytes of memory to mini-computers and mainframes.  I've
> never seen one that didn't default to base 10 for integer literals.
>
> I'm not saying they don't exist, just that it would be interesting to
> see an example of one.
>
I have a book called "Choosing and using 4 Bit Microcontrollers" by
Philip McDowell. In it is an example assembly listing for an OKI 6351
microcontroller that uses unadorned hexadecimal literals.

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

#88587

On 2015-04-07 15:36, jonas.thornvall@gmail.com wrote:
> Den tisdag 7 april 2015 kl. 16:30:15 UTC+2 skrev Denis McMahon:
>> On Tue, 07 Apr 2015 09:29:59 -0400, Dave Angel wrote:
>>
>>> On 04/07/2015 05:44 AM, jonas.thornvall@gmail.com wrote:
>>
>>>> I want todo faster baseconversion for very big bases like base
>>>> 1 000 000, so instead of adding up digits i search it.
>>
>>> How do you know the baseconversion is the bottleneck, if you
>>> haven't written any Python code yet?
>>
>> He doesn't. He doesn't comprehend that as far as a computer is
>> concerned an integer has no specific 'base', it's only when
>> presented in a form for humans to read that it gets base
>> information added in the representation.
>>
>> He's making these and other similar errors in the javascript groups
>> too.
>>
>> I suspect he's one of those people that spends his time thinking
>> up elaborate solutions that he has no idea how to implement as a
>> response to dreamt up non existent problems.
>>
> Bullshit declare two integers in any language one 7 and one 4 and
> then write x=7+4; if you find a programming language where that does
> not yield 11 tell me.
>
> Integers are internally assumed to be base 10 otherwise you could not
> calculate without giving the base.
>
> All operations on integers addition, subtraction, multiplication and
> division assume base 10.
>
Sorry to say this, but that's nonsense.

It doesn't matter what base it's working in internally; usually it's
base 2 (binary), because that's simpler to implement.

It's only when you're converting from or to text that you need specify
a base. Humans prefer base 10, so they've make that the default.

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

#88598

Den tisdag 7 april 2015 kl. 17:00:53 UTC+2 skrev MRAB:
> On 2015-04-07 15:36, jonas.thornvall@gmail.com wrote:
> > Den tisdag 7 april 2015 kl. 16:30:15 UTC+2 skrev Denis McMahon:
> >> On Tue, 07 Apr 2015 09:29:59 -0400, Dave Angel wrote:
> >>
> >>> On 04/07/2015 05:44 AM, jonas.thornvall@gmail.com wrote:
> >>
> >>>> I want todo faster baseconversion for very big bases like base
> >>>> 1 000 000, so instead of adding up digits i search it.
> >>
> >>> How do you know the baseconversion is the bottleneck, if you
> >>> haven't written any Python code yet?
> >>
> >> He doesn't. He doesn't comprehend that as far as a computer is
> >> concerned an integer has no specific 'base', it's only when
> >> presented in a form for humans to read that it gets base
> >> information added in the representation.
> >>
> >> He's making these and other similar errors in the javascript groups
> >> too.
> >>
> >> I suspect he's one of those people that spends his time thinking
> >> up elaborate solutions that he has no idea how to implement as a
> >> response to dreamt up non existent problems.
> >>
> > Bullshit declare two integers in any language one 7 and one 4 and
> > then write x=7+4; if you find a programming language where that does
> > not yield 11 tell me.
> >
> > Integers are internally assumed to be base 10 otherwise you could not
> > calculate without giving the base.
> >
> > All operations on integers addition, subtraction, multiplication and
> > division assume base 10.
> >
> Sorry to say this, but that's nonsense.
> 
> It doesn't matter what base it's working in internally; usually it's
> base 2 (binary), because that's simpler to implement.
> 
> It's only when you're converting from or to text that you need specify
> a base. Humans prefer base 10, so they've make that the default.

No that is not what i am saying, i am saying if you do operations on two integers the machine will assume base 10.

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

#88625

On Wed, 8 Apr 2015 01:43 am, jonas.thornvall@gmail.com wrote:

> No that is not what i am saying, i am saying if you do operations on two
> integers the machine will assume base 10.


We understand what you are saying. You are simply WRONG.

There hasn't been a machine in common use that used other than binary for
integers for probably forty years now, and there has *never* been a PC that
has used other than binary for integers. When you write 12345 as an integer
in a programming language, it is NOT stored internally as five decimal
digits 1 2 3 4 5 in *nearly all languages*. There might be one or two
exceptions, e.g. Hypertalk would store it as a string of bytes 0x3132333435
in hexadecimal, or in binary 0011000100110010001100110011010000110101.

(As you can guess, Hypertalk is not the most efficient of languages.)

But most languages will store the decimal int 12345 in binary:

0011000000111001  # 16 bit word size

00000000000000000011000000111001  # 32 bit word size

(Ignoring Big Endian/Little Endian issues -- some machines store the bytes
the other way around.)

The fact is computer languages automatically convert source code from
(usually) decimal base to whatever their internal storage format uses,
which is normally base 2. They don't work in decimal, using the same
decimal routines you learned in school.



-- 
Steven

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

#88645

On Wed, Apr 8, 2015 at 8:51 AM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> There hasn't been a machine in common use that used other than binary for
> integers for probably forty years now, and there has *never* been a PC that
> has used other than binary for integers. When you write 12345 as an integer
> in a programming language, it is NOT stored internally as five decimal
> digits 1 2 3 4 5 in *nearly all languages*. There might be one or two
> exceptions, e.g. Hypertalk would store it as a string of bytes 0x3132333435
> in hexadecimal, or in binary 0011000100110010001100110011010000110101.
>
> (As you can guess, Hypertalk is not the most efficient of languages.)

FWIW, REXX does the same thing as Hypertalk - the integer 12345 and
the string "12345" are identical. If you add the string "1" and the
string "12345", you get the string "12346". (Concatenation is a
separate operation, and would result in the string "112345".) However,
Steven is still correct in that it is not stored as five decimal
digits; it's stored as five bytes in your system encoding. On my
systems, those were all ASCII-compatible, so it'd be 0x3132333435
(plus some metadata about string length and stuff, not germane to the
discussion), though I suspect that an EBCDIC system would store it as
0xF1F2F3F4F5 instead.

ChrisA

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

#88588

On 04/07/2015 10:36 AM, jonas.thornvall@gmail.com wrote:


> All operations on integers addition, subtraction, multiplication and division assume base 10.
>

There have been machines where that was true, but I haven't worked on 
such for about 30 years.  On any machines I've programmed lately, the 
arithmetic is done in binary by default, and only converted to decimal 
for printing.

Not that the internal base is usually relevant, of course.

-- 
DaveA

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

#88590

On Tue, Apr 7, 2015 at 8:36 AM,  <jonas.thornvall@gmail.com> wrote:
> Den tisdag 7 april 2015 kl. 16:30:15 UTC+2 skrev Denis McMahon:
>> On Tue, 07 Apr 2015 09:29:59 -0400, Dave Angel wrote:
>>
>> > On 04/07/2015 05:44 AM, jonas.thornvall@gmail.com wrote:
>>
>> >> I want todo faster baseconversion for very big bases like base 1 000
>> >> 000, so instead of adding up digits i search it.
>>
>> > How do you know the baseconversion is the bottleneck, if you haven't
>> > written any Python code yet?
>>
>> He doesn't. He doesn't comprehend that as far as a computer is concerned
>> an integer has no specific 'base', it's only when presented in a form for
>> humans to read that it gets base information added in the representation.
>>
>> He's making these and other similar errors in the javascript groups too.
>>
>> I suspect he's one of those people that spends his time thinking up
>> elaborate solutions that he has no idea how to implement as a response to
>> dreamt up non existent problems.
>>
>> --
>> Denis McMahon, denismfmcmahon@gmail.com
>
> Bullshit declare two integers in any language one 7 and one 4 and then write x=7+4; if you find a programming language where that does not yield 11 tell me.
>
> Integers are internally assumed to be base 10 otherwise you could not calculate without giving the base.
>
> All operations on integers addition, subtraction, multiplication and division assume base 10.

You're conflating the internal representation of the integer with the
formatting that is done to display the integer. When you do
"print(x)", the computer doesn't just dump the internal representation
of x onto the display. It formats x as character data and displays
*that*. For integers, the vast majority of programming languages will
do the formatting as base 10 by default, since that is the format
preferred by most humans.

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

#88599

Den tisdag 7 april 2015 kl. 17:07:36 UTC+2 skrev Ian:
> On Tue, Apr 7, 2015 at 8:36 AM,  <jonas.thornvall@gmail.com> wrote:
> > Den tisdag 7 april 2015 kl. 16:30:15 UTC+2 skrev Denis McMahon:
> >> On Tue, 07 Apr 2015 09:29:59 -0400, Dave Angel wrote:
> >>
> >> > On 04/07/2015 05:44 AM, jonas.thornvall@gmail.com wrote:
> >>
> >> >> I want todo faster baseconversion for very big bases like base 1 000
> >> >> 000, so instead of adding up digits i search it.
> >>
> >> > How do you know the baseconversion is the bottleneck, if you haven't
> >> > written any Python code yet?
> >>
> >> He doesn't. He doesn't comprehend that as far as a computer is concerned
> >> an integer has no specific 'base', it's only when presented in a form for
> >> humans to read that it gets base information added in the representation.
> >>
> >> He's making these and other similar errors in the javascript groups too.
> >>
> >> I suspect he's one of those people that spends his time thinking up
> >> elaborate solutions that he has no idea how to implement as a response to
> >> dreamt up non existent problems.
> >>
> >> --
> >> Denis McMahon, denismfmcmahon@gmail.com
> >
> > Bullshit declare two integers in any language one 7 and one 4 and then write x=7+4; if you find a programming language where that does not yield 11 tell me.
> >
> > Integers are internally assumed to be base 10 otherwise you could not calculate without giving the base.
> >
> > All operations on integers addition, subtraction, multiplication and division assume base 10.
> 
> You're conflating the internal representation of the integer with the
> formatting that is done to display the integer. When you do
> "print(x)", the computer doesn't just dump the internal representation
> of x onto the display. It formats x as character data and displays
> *that*. For integers, the vast majority of programming languages will
> do the formatting as base 10 by default, since that is the format
> preferred by most humans.

No i don't i say the operations assume base ten other wise INT A=7,B=4 Calculate C=A+B would not yield 11 as an answer. The programming languages assume integer operations are done in base 10, at least the one where you can not specify in what base the integer arithmetic is done. And there probably is such languages, Python maybe?

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

#88634

On Tue, 7 Apr 2015 08:47:38 -0700 (PDT), jonas.thornvall@gmail.com
declaimed the following:

>No i don't i say the operations assume base ten other wise INT A=7,B=4 Calculate C=A+B would not yield 11 as an answer. The programming languages assume integer operations are done in base 10, at least the one where you can not specify in what base the integer arithmetic is done. And there probably is such languages, Python maybe?

	Unless you are using COBOL, where the default for integers is BCD, the
"integer operations" are done in binary... The language
compiler/interpreter merely assumes that /literals/ found in the /source/
are decimal by default; and output conversion is from binary to decimal
representation.

-- 
	Wulfraed                 Dennis Lee Bieber         AF6VN
    wlfraed@ix.netcom.com    HTTP://wlfraed.home.netcom.com/

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

Page 1 of 7  [1] 2 3 4 5 6 7  Next page →

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

csiph-web