Best search algorithm to find condition within a range

classic Classic list List threaded Threaded
119 messages Options
1234 ... 6
Reply | Threaded
Open this post in threaded view
|

Best search algorithm to find condition within a range

jonas.thornvall@gmail.com


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>

 












 


Reply | Threaded
Open this post in threaded view
|

Best search algorithm to find condition within a range

Dave Angel-4
On 04/07/2015 05:44 AM, jonas.thornvall at 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


Reply | Threaded
Open this post in threaded view
|

Best search algorithm to find condition within a range

jonas.thornvall@gmail.com
In reply to this post by jonas.thornvall@gmail.com
Den tisdag 7 april 2015 kl. 15:30:36 UTC+2 skrev Dave Angel:

> On 04/07/2015 05:44 AM, jonas.thornvall at 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.


Reply | Threaded
Open this post in threaded view
|

Best search algorithm to find condition within a range

Dave Angel-4
On 04/07/2015 10:10 AM, jonas.thornvall at 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


Reply | Threaded
Open this post in threaded view
|

Best search algorithm to find condition within a range

Denis McMahon
In reply to this post by jonas.thornvall@gmail.com
On Tue, 07 Apr 2015 09:29:59 -0400, Dave Angel wrote:

> On 04/07/2015 05:44 AM, jonas.thornvall at 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 at gmail.com


Reply | Threaded
Open this post in threaded view
|

Best search algorithm to find condition within a range

Ian Kelly-2
In reply to this post by jonas.thornvall@gmail.com
On Tue, Apr 7, 2015 at 3:44 AM,  <jonas.thornvall at 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.
>
> 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;

I'm not sure that I understand what it is that you're trying to
accomplish. Are you trying to find the digits without using division
because "division is slow"? If that's the case, then let me show you
something.

$ python -m timeit -s "n = 1523837293" "n // 1000000"
1000000 loops, best of 3: 0.286 usec per loop

$ python -m timeit -s "n = 1523" "n * 1000000; (n+1) * 1000000"
1000000 loops, best of 3: 0.455 usec per loop

In Python, one addition and two multiplications are already slower
than a single division. The only way you're going to beat division by
using trial multiplication is if the first digit that you try is
always correct. To do that, you would need an oracle feeding your
search algorithm, and then you might as well just use the oracle.

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

Do you mean binary search? That would be an improvement over the
linear search algorithm you've shown. Whether a trinary search might
be faster would depend on the distribution of the numbers you expect.
If they're evenly distributed, it will be slower.

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

On average, a random Oracle with a search space of 1000000 will need
1000000 guesses.


Reply | Threaded
Open this post in threaded view
|

Best search algorithm to find condition within a range

Chris Angelico
In reply to this post by Dave Angel-4
On Wed, Apr 8, 2015 at 12:26 AM, Dave Angel <davea at 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


Reply | Threaded
Open this post in threaded view
|

Best search algorithm to find condition within a range

jonas.thornvall@gmail.com
In reply to this post by Denis McMahon
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 at 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 at 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.


Reply | Threaded
Open this post in threaded view
|

Best search algorithm to find condition within a range

Chris Angelico
On Wed, Apr 8, 2015 at 12:36 AM,  <jonas.thornvall at 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


Reply | Threaded
Open this post in threaded view
|

Best search algorithm to find condition within a range

MRAB-2
In reply to this post by jonas.thornvall@gmail.com
On 2015-04-07 15:36, jonas.thornvall at 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 at 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.


Reply | Threaded
Open this post in threaded view
|

Best search algorithm to find condition within a range

Dave Angel-4
In reply to this post by jonas.thornvall@gmail.com
On 04/07/2015 10:36 AM, jonas.thornvall at 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


Reply | Threaded
Open this post in threaded view
|

Best search algorithm to find condition within a range

Grant Edwards-7
In reply to this post by jonas.thornvall@gmail.com
On 2015-04-07, Chris Angelico <rosuav at gmail.com> wrote:

> On Wed, Apr 8, 2015 at 12:36 AM,  <jonas.thornvall at 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            


Reply | Threaded
Open this post in threaded view
|

Best search algorithm to find condition within a range

Ian Kelly-2
In reply to this post by jonas.thornvall@gmail.com
On Tue, Apr 7, 2015 at 8:36 AM,  <jonas.thornvall at 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 at 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 at 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.


Reply | Threaded
Open this post in threaded view
|

Best search algorithm to find condition within a range

Dave Angel-4
In reply to this post by Grant Edwards-7
On 04/07/2015 11:05 AM, Grant Edwards wrote:

> On 2015-04-07, Chris Angelico <rosuav at gmail.com> wrote:
>> On Wed, Apr 8, 2015 at 12:36 AM,  <jonas.thornvall at 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


Reply | Threaded
Open this post in threaded view
|

Best search algorithm to find condition within a range

Chris Angelico
On Wed, Apr 8, 2015 at 1:23 AM, Dave Angel <davea at 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


Reply | Threaded
Open this post in threaded view
|

Best search algorithm to find condition within a range

jonas.thornvall@gmail.com
In reply to this post by jonas.thornvall@gmail.com
Den tisdag 7 april 2015 kl. 16:32:56 UTC+2 skrev Ian:

> On Tue, Apr 7, 2015 at 3:44 AM,  <jonas.thornvall at 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.
> >
> > 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;
>
> I'm not sure that I understand what it is that you're trying to
> accomplish. Are you trying to find the digits without using division
> because "division is slow"? If that's the case, then let me show you
> something.
>
> $ python -m timeit -s "n = 1523837293" "n // 1000000"
> 1000000 loops, best of 3: 0.286 usec per loop
>
> $ python -m timeit -s "n = 1523" "n * 1000000; (n+1) * 1000000"
> 1000000 loops, best of 3: 0.455 usec per loop
>
> In Python, one addition and two multiplications are already slower
> than a single division. The only way you're going to beat division by
> using trial multiplication is if the first digit that you try is
> always correct. To do that, you would need an oracle feeding your
> search algorithm, and then you might as well just use the oracle.
>
> > One could start at half base searching, but then i Think i've read that using 1/3 closing in faster?
>
> Do you mean binary search? That would be an improvement over the
> linear search algorithm you've shown. Whether a trinary search might
> be faster would depend on the distribution of the numbers you expect.
> If they're evenly distributed, it will be slower.
>
> > 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?
>
> On average, a random Oracle with a search space of 1000000 will need
> 1000000 guesses.

Well of course you use same principles like a binary search setting min and max, closing in on the digit. In this case the searched numbers  > base^exp  and number< base^exp+1.

But since the search is within large bases upto 32-bit space, so base 4294967295 is the biggest allowed. I need to find the nearest less exp in base for each (lets call them pseudo digits). But as you see there it will take time to add them up. So better doing a binary search, you know min-max half (iteration). You can do the same for a random oracle min max within range, and if the number of tries in general over 22 i think a random oracle do it better than a binary search.

It was a long time since i did this, but i do know there is a threshold where searching min max with the oracle will be faster than the binary search.


Reply | Threaded
Open this post in threaded view
|

Best search algorithm to find condition within a range

jonas.thornvall@gmail.com
In reply to this post by jonas.thornvall@gmail.com
Den tisdag 7 april 2015 kl. 17:00:53 UTC+2 skrev MRAB:

> On 2015-04-07 15:36, jonas.thornvall at 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 at 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.


Reply | Threaded
Open this post in threaded view
|

Best search algorithm to find condition within a range

jonas.thornvall@gmail.com
In reply to this post by jonas.thornvall@gmail.com
Den tisdag 7 april 2015 kl. 17:07:36 UTC+2 skrev Ian:

> On Tue, Apr 7, 2015 at 8:36 AM,  <jonas.thornvall at 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 at 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 at 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?


Reply | Threaded
Open this post in threaded view
|

Best search algorithm to find condition within a range

MRAB-2
In reply to this post by Grant Edwards-7
On 2015-04-07 16:05, Grant Edwards wrote:

> On 2015-04-07, Chris Angelico <rosuav at gmail.com> wrote:
>> On Wed, Apr 8, 2015 at 12:36 AM,  <jonas.thornvall at 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.


Reply | Threaded
Open this post in threaded view
|

Best search algorithm to find condition within a range

jonas.thornvall@gmail.com
In reply to this post by Denis McMahon
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 at 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 at gmail.com

Well Denis if it hasn't a base then how can you add integers, the integer operations assume base 10.


1234 ... 6