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

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

Time complexity and division

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

Contents

  Time complexity and division jonas.thornvall@gmail.com - 2015-06-20 04:21 -0700
    Re: Time complexity and division Scott Sauyet <scott.sauyet@gmail.com> - 2015-06-20 18:08 -0700
      Re: Time complexity and division jonas.thornvall@gmail.com - 2015-06-21 00:23 -0700
      Re: Time complexity and division jonas.thornvall@gmail.com - 2015-06-21 01:01 -0700
        Re: Time complexity and division "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2015-06-21 10:09 +0200
          Re: Time complexity and division jonas.thornvall@gmail.com - 2015-06-21 02:48 -0700
            Re: Time complexity and division jonas.thornvall@gmail.com - 2015-06-21 03:02 -0700
            Re: Time complexity and division "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2015-06-21 21:43 +0200
    Re: Time complexity and division Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-06-21 12:35 +0100
      Re: Time complexity and division "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2015-06-21 22:01 +0200
        Re: Time complexity and division Richard Damon <Richard@Damon-Family.org> - 2015-08-15 11:02 -0400

#28119 — Time complexity and division

Does anyone know the time complexity of my suggested min max search operation vs a schoolbook long division, sieve of Erathostenes or Karatsuba?

Is there any other name for it than min max search? 

[toc] | [next] | [standalone]

#28120

jonas.thornvall@gmail.com wrote:
> Does anyone know the time complexity of my suggested min max search operation
> vs a schoolbook long division, sieve of Erathostenes or Karatsuba?

Yes.
 
> Is there any other name for it than min max search?

Yes.


  -- Scott

P.S. Have you learned yet how USENET works?

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

#28121

Den söndag 21 juni 2015 kl. 03:08:43 UTC+2 skrev Scott Sauyet:
> jonas.thornvall@gmail.com wrote:
> > Does anyone know the time complexity of my suggested min max search operation
> > vs a schoolbook long division, sieve of Erathostenes or Karatsuba?
> 
> Yes.
>  
> > Is there any other name for it than min max search?
> 
> Yes.
> 
> 
>   -- Scott
> 
> P.S. Have you learned yet how USENET works?

No

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

#28122

Den söndag 21 juni 2015 kl. 03:08:43 UTC+2 skrev Scott Sauyet:
> jonas.thornvall@gmail.com wrote:
> > Does anyone know the time complexity of my suggested min max search operation
> > vs a schoolbook long division, sieve of Erathostenes or Karatsuba?
> 
> Yes.
>  
> > Is there any other name for it than min max search?
> 
> Yes.
> 
> 
>   -- Scott
> 
> P.S. Have you learned yet how USENET works?

Of course the best case for a min max search is that we find the digit multiple it first try so "1" comparisson, and the worst must be that we need sqrt(n) comparissons.

And within the average case the multiple would be found after sqrt(n)/2 comparissons?

Since it can be used not only as a base changin algorithm, but easily can be modified into doing division. One wonder how it compairs doing division.
So it seem the time complexity is dependent upon the base used in this algorithm.

But i guess the time complexity also must take into account not only the min and max comparissons but also the multipliations and digit comparissons needed,
to really find min and max?

So can one state that a comparissons in itself is one operation, that does not seem fair it is easier to find and set min and max for small numbers than for real big ones.

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

#28123

jonas.thornvall@gmail.com wrote on 21 Jun 2015 in comp.lang.javascript:

>> P.S. Have you learned yet how USENET works?
> 
> Of course the best case for ......

As Usenet is a platform of discussion-lists, 
you should bring in argumentation for your statements.

Your 'of course' just means:
'I trust you fall for my unforgivable lack of argumentation'.

And please stop responding to yourself and answering yourself, 
Usenet is not a platform for monologues.

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

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

#28124

Den söndag 21 juni 2015 kl. 10:09:55 UTC+2 skrev Evertjan.:
> jonas.thornvall@gmail.com wrote on 21 Jun 2015 in comp.lang.javascript:
> 
> >> P.S. Have you learned yet how USENET works?
> > 
> > Of course the best case for ......
> 
> As Usenet is a platform of discussion-lists, 
> you should bring in argumentation for your statements.
> 
> Your 'of course' just means:
> 'I trust you fall for my unforgivable lack of argumentation'.
> 
> And please stop responding to yourself and answering yourself, 
> Usenet is not a platform for monologues.
> 
> -- 
> Evertjan.
> The Netherlands.
> (Please change the x'es to dots in my emailaddress)
Well i must say i find it hard to calculate the time complexity, especially since the base used seem to matter.

The weight of the operands seem to be vital, and really should be taken into account when doing comparissons. 

If i have an algorithm performing division by a min max search, i am a bit lost about what really is the timecomplexity. Because there is numerous different operations performed. If one take the actual min max search for a digit, it follows naturally that the weight of digit is dependent upon the base.

So the higher the base the less total operations is performed doing the divisions. There is a number of operations performed to do the division, but which one is the actual time complexity.

1. Search and store the multiples for base x  -> x^1,x^2,x^3... and so on.
Loop until number exhausted or specified precision reached.
Loop until multiple found
2. Use the min max search and find the polynomial multiplier for digit y*x^z
3. Compare the result of the multiplication with the number.
End.
4. Subtract the product from the number.
End.

I have a hard time to conclude what the actual time complexity is when using this algorithm doing division and it also seem dependent upon the size of base x.

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

#28125

Den söndag 21 juni 2015 kl. 11:48:38 UTC+2 skrev jonas.t...@gmail.com:
> Den söndag 21 juni 2015 kl. 10:09:55 UTC+2 skrev Evertjan.:
> > jonas.thornvall@gmail.com wrote on 21 Jun 2015 in comp.lang.javascript:
> > 
> > >> P.S. Have you learned yet how USENET works?
> > > 
> > > Of course the best case for ......
> > 
> > As Usenet is a platform of discussion-lists, 
> > you should bring in argumentation for your statements.
> > 
> > Your 'of course' just means:
> > 'I trust you fall for my unforgivable lack of argumentation'.
> > 
> > And please stop responding to yourself and answering yourself, 
> > Usenet is not a platform for monologues.
> > 
> > -- 
> > Evertjan.
> > The Netherlands.
> > (Please change the x'es to dots in my emailaddress)
> Well i must say i find it hard to calculate the time complexity, especially since the base used seem to matter.
> 
> The weight of the operands seem to be vital, and really should be taken into account when doing comparissons. 
> 
> If i have an algorithm performing division by a min max search, i am a bit lost about what really is the timecomplexity. Because there is numerous different operations performed. If one take the actual min max search for a digit, it follows naturally that the weight of digit is dependent upon the base.
> 
> So the higher the base the less total operations is performed doing the divisions. There is a number of operations performed to do the division, but which one is the actual time complexity.
> 
> 1. Search and store the multiples for base x  -> x^1,x^2,x^3... and so on.
> Loop until number exhausted or specified precision reached.
> Loop until multiple found
> 2. Use the min max search and find the polynomial multiplier for digit y*x^z
> 3. Compare the result of the multiplication with the number.
> End.
> 4. Subtract the product from the number.
> End.
> 
> I have a hard time to conclude what the actual time complexity is when using this algorithm doing division and it also seem dependent upon the size of base x.

I have a hard time to imagine that the actual time complexity is only the actual min max search finding the digits. 

Because they will be miles apart if you chose to do it in base 2 or if you chose to use the sqrt(divisor) as base.

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

#28132

jonas.thornvall@gmail.com wrote on 21 Jun 2015 in comp.lang.javascript:

> Den s”ndag 21 juni 2015 kl. 10:09:55 UTC+2 skrev Evertjan.:
>> jonas.thornvall@gmail.com wrote on 21 Jun 2015 in comp.lang.javascript:
>> 
>> >> P.S. Have you learned yet how USENET works?
>> > 
>> > Of course the best case for ......
>> 
>> As Usenet is a platform of discussion-lists, 
>> you should bring in argumentation for your statements.
>> 
>> Your 'of course' just means:
>> 'I trust you fall for my unforgivable lack of argumentation'.
>> 
>> And please stop responding to yourself and answering yourself, 
>> Usenet is not a platform for monologues.

> Well i must say i find it hard to calculate the time complexity,
> especially since the base used seem to matter. 

And here again you do not respond to the posting, 
but just go on doing monologues.

Do you do that in real life too?

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

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

#28126

jonas.thornvall@gmail.com writes:

> Does anyone know the time complexity of my suggested min max search
> operation vs a schoolbook long division, sieve of Erathostenes or
> Karatsuba?

I don't know what your "min max search operation" is and I'm puzzled by
the fact you want to compare is with three apparently different things
(a division algorithm, a mother of finding primes and a multiplication
algorithm).

> Is there any other name for it than min max search?

I *think* it's what everyone else calls a binary search, but you don't
show it so that's just guessing.

-- 
Ben.

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

#28133

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

> jonas.thornvall@gmail.com writes:
> 
>> Does anyone know the time complexity of my suggested min max search
>> operation vs a schoolbook long division, sieve of Erathostenes or
>> Karatsuba?
> 
> I don't know what your "min max search operation" is and I'm puzzled by
> the fact you want to compare is with three apparently different things
> (a division algorithm, a mother of finding primes and a multiplication
> algorithm).
> 
>> Is there any other name for it than min max search?
> 
> I *think* it's what everyone else calls a binary search, but you don't
> show it so that's just guessing.

I remember this had to do with "alpha-beta pruning" in chess-programming.

Ah yes, here it is:

"Alpha–beta pruning is a search algorithm that seeks to decrease the number 
of nodes that are evaluated by the minimax algorithm in its search tree."
[Allen Newell and Herbert A. Simon, 1958]. 
<https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning>

"A minimax approximation algorithm [..] is a method to find an approximation 
of a mathematical function that minimizes maximum error."
<https://en.wikipedia.org/wiki/Minimax_approximation_algorithm>

Deep Alpha-Beta Pruning: An alpha or beta cut-off value may be used to prune 
trees at any node which is an even number of levels below it 
[Alpha-beta Pruning Algorithm, Fuller, Gaschnig and Gillogly, 1973]

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

Odd that an odd number of levels was even disregarded, 
perhaps as it would give a unacceptable bias?

Indeed this may have been decisive in combatting the time complexity 
of the primitive calculating machines used during that computer stone-age.

Perhaps Jonas was still inside the whale at that time? 

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

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

#28532

On 6/21/15 4:01 PM, Evertjan. wrote:
> Ah yes, here it is:
>
> "Alpha–beta pruning is a search algorithm that seeks to decrease the number
> of nodes that are evaluated by the minimax algorithm in its search tree."
> [Allen Newell and Herbert A. Simon, 1958].
> <https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning>
>
> "A minimax approximation algorithm [..] is a method to find an approximation
> of a mathematical function that minimizes maximum error."
> <https://en.wikipedia.org/wiki/Minimax_approximation_algorithm>
>
> Deep Alpha-Beta Pruning: An alpha or beta cut-off value may be used to prune
> trees at any node which is an even number of levels below it
> [Alpha-beta Pruning Algorithm, Fuller, Gaschnig and Gillogly, 1973]
>
> ========================
>
> Odd that an odd number of levels was even disregarded,
> perhaps as it would give a unacceptable bias?
>
> Indeed this may have been decisive in combatting the time complexity
> of the primitive calculating machines used during that computer stone-age.
>
> Perhaps Jonas was still inside the whale at that time?
>

I think the even number of layers is due to the fact that even layers 
and odd layers are acting different. For example, even layers may be 
maximizing, while the odd layers are minimizing, or even layers are my 
choices, odd layers are my opponents.

If I currently have a value of X and I am the maximizer, then if some 
odd layer below currently can say no higher than Y, less than X, then I 
can prune all the unevaluated even nodes just below that layer, as I 
know that I will chose a path that avoids this node, since I know I can 
do better. (I can't 'prune' the node that said Y, as I have already 
started to evaluate it, the best I can do is prune everything 
unevaluated just below it and thus finish the evaluation of that node. I 
don't get the real answer for that node, but I know that the even node 
above it either has a better option to take, or some higher even node 
has a better option and I won't get to here).

An alternative description would be that we can prune off (and abort the 
calculation of) any odd branch that we know we won't enter as we have 
better choices. In that model WE can't prune even branches as those are 
based on our opponents move, those will get pruned when we flip our 
brain and start to think of what they should do for each of the 
positions we are thinking of giving them. THEY will prune off the even 
branches. Mathematically, it seems preferred to described the nodes 
pruned as those never evaluated, as opposed to those whose evaluations 
are not completed.

Similar logic to prune out an odd layer would look at the value of the 
even layer above it and compare that to some odd layer above it. But, we 
do the pruning based on a node, and that node it the base, which is 
called level 0 (or even), so an pruning can't occur there (it might 
happen when we recurse, and effectively swap the definition of even and 
odd layers are reverse the value function).

[toc] | [prev] | [standalone]

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

csiph-web